Archive for February, 2010

Problem 39 – Perimeters of Right Triangles

February 17, 2010

In problem 39 we’re supposed to look at right triangles with integral sides and perimeter no bigger than 100. Specifically, among such perimeters, which has the most representing right triangles?

The given bound seemed small enough that I figure brute force was a good place to start. Loop through lengths for the legs, calculate what the hypotenuse would be, keep track of solutions you find, organized by perimeter, and see who wins. The first (correct) program I wrote ran in 5 seconds. With 5 minutes tweaking the code without much thought, I had the runtime down to half a second. 1000 really isn’t a difficult bound (fwiw though, 10000 takes nearly a minute on my computer). Here’s my code:

def solve(bound):
    solns = [0 for n in range(0,bound+1)] # storage
    ret = 0 # the winning perimeter
    for smleg in xrange(1,bound//2 + 1):
        # the larger leg will still be shorter than the hypotenuse
        for lgleg in xrange(smleg+1, (bound-smleg)//2 + 1):
            hyp = int((smleg**2 + lgleg**2)**.5)
            peri = smleg + lgleg + hyp
            if peri <= bound and smleg**2 + lgleg**2 == hyp**2:
                solns[peri] += 1
                if solns[peri] > solns[ret]:
                    ret = peri
    return ret

I have a hard time letting such ugly code go, but I’m pretty sure I’m supposed to be spending my time doing other things anyway, so perhaps I should… move on to problem 40 🙂 Nearing a level-up on Project Euler…

Advertisements

Problem 38 – Pandigital Products

February 14, 2010

In problem 38 we’re supposed to find the biggest 9 digit pandigital number that is obtained by concatenating consecutive multiples of a fixed number, starting with the number itself. Sorta a mouthful, but the examples in the problem text make it pretty clear, I think.

10 minutes thought, or so, might convince you that (if the answer isn’t the example given in the problem text) the number you’ll be taking multiples of must be a four digit number, bigger than 9182. So you really don’t have too much to loop through, which is nice. Here’s what I came up with:

def solve():
    biglhs = 9182
    digits = map(str, xrange(1,10))
    for lhs in xrange(9183,10000):
        need = digits[:] # make a copy
        # get rid of digits in the lhs
        for d in str(lhs):
            if need.count(d): need.remove(d)
            else: break # quit early, MASSIVE speed improvement
        # if lhs is unique digits, and rhs is the remaining digits
        if len(need) == 5 and need == sorted(map(str, str(2*lhs))):
            biglhs = lhs
    biggest = "%s%s"%(biglhs,2*biglhs)
    return biggest

Quick problems are fun.

Problem 37 – Truncatable Primes

February 14, 2010

In problem 37 we are supposed to find the eleven primes whose decimal representations can be continuously truncated from the left, or continuously truncated from the right, producing primes the whole time. And the single digit primes don’t count. I’ll call these numbers truncatable primes. The truncation means the the right-most digit must always be a single digit prime, and the same for the left. Furthermore, 2s and 5s can only show up as the left-most digit. So, in fact, the right-most digit must be either 3 or 7.

So, with an oracle telling you about primes, you could just loop until you’ve found eleven truncatable primes. This ran in under 10 seconds on my computer, which is probably fine. But then I spent a while (much longer than I had hoped) writing a faster version. It’s better than real work.

Here’s what I’ll do. Keep track of a list of left-trunctable (can remove digits from the left) primes (I’ll call them LTs), beginning with the list [3, 7]. Loop through this list, looking for ways to add digits to the left and still have a LTs. When I find a new LT, add it to the list, and if it is also right-truncatable, keep it in a list of truncatable (both sides) primes.

Organizing the search for new LTs seems to be the interesting part of this setup. You can get more LTs, from a LT, by adding a single digit prime to the left, separated by a (possibly empty) string of 1s and 9s. However, you don’t want to go looking for all of the extensions to a given seed all at once (essentially a depth-first approach), because there might be infinitely many.

I decided to do my search for more LTs based on the length of their decimal representation. Begin by looking for 2 digit LTs, then 3 digits, and so on, keeping track of all the LTs you’ve found so far. When you want to look for LTs with the next number of digits, go through the list you’ve made so far and then only look for LTs that extend a given LT and also only have the correct number of digits. Since you’ve already got an LT, and will be adding a single digit prime to the very right, you’re essentially looking at how many 1s and 9s to throw in the middle.

In my code, I’ve got two functions “isltrunc” and “isrtrunc” that return True or False, if the input is a left-truncatable, or right-truncatable, prime (well, more correctly: a string containing the decimal representation of the prime). I’ve got another method that looks for LT extensions of a given LT, based on how may 1s and 9s to put in the middle. It looks like:

def ltruncs(p, midlen, oracle=PrimeOracle(100)):
    # first build all of the possible strings of 1s and 9s of length midlen
    intstrs = [""]
    while len(intstrs[0]) < midlen:
        intstrs = map(lambda s:"1"+s,intstrs) + map(lambda s:"9"+s,intstrs)

    growth = ["%s%s%s"%(d,i,p) for d in [2,3,5,7] for i in intstrs]
    return filter(lambda s:isltrunc(s,oracle), growth)

(By the way, my “isltrunc” and “isrtrunc” functions also take an oracle parameter)

Finally, my main code goes like this:

def solve():
    isprime = PrimeOracle(1000000)
    ret = set([]) # the truncatables
    seeds = ["3","7"] # the LTs
    strlen = 2
    while len(ret) < 11:
        # look for LTs of length strlen
        fringe = [] # new LTs we find
        for pstr in seeds:
            midlen = strlen - len(pstr) - 1
            if midlen >= 0:
                growth = ltruncs(pstr, midlen, isprime)
                fringe += growth

                # if we find new truncatables, add 'em to our store
                ret = ret.union([int(g) for g in growth if isrtrunc(g,isprime)])
                if len(ret) >= 11:
                    break
        strlen += 1
        seeds += fringe
    return sum(ret)

After building the PrimeOracle, this takes very little time to run.

I think I should be getting in the habit of using ’ to delineate strings, instead of “. And perhaps throwing appropriate unicode handling where it belongs. I have to get straight where that is though. Of course, none of this affects any of this work.

Problem 36 – Simultaneous Palindromes

February 10, 2010

In problem 36 we are asked to find all the numbers below a bound that are simultaneously palindromic in both base 10 and base 2. Not the most interesting problem, but for something like completeness sake (and probably to delay doing other things) I thought I’d post about it. I probably learned things, so it was probably worthwhile.

The problem text points out that the leading digit can’t be 0, in either base, so we know that all of the numbers to consider are odd. That’ll likely cut down list iteration by a factor of two. No matter how we set things up, we’ll likely want to reverse a string. Here’s what I rigged up:

def reverse(str):
    return "".join([str[len(str)-1-n] for n in xrange(0, len(str))])

Then I got curious if there was something built-in. There is a built-in way to reverse a list, but not a string. There’s also a “reversed” method that’ll reverse an iterator. And strings have iterators, so you could also do

def reverse(str):
    return "".join(reversed(str))

which seems to have the same affect as

def reverse(str):
    return "".join([i for i in reversed(str)])

It’d probably be fun to compare all of these for speed, but the strings we’re doing are only so big, so it seems to not matter a whole lot for this problem.

We’ll also likely need to test if a string is a palindrome. Here’s what I did:

def ispali(str):
    idx = 0
    while 2*idx <= len(str):
        if not str[idx] == str[len(str)-1-idx]:
            return False
        idx += 1
    return True

The idea being that you only need to go half-way in to see if a string is palindromic. I realized you could also just return “str == reverse(str)”. Mine looks to be slightly faster 🙂

Ok, so, the final bit is converting an integer to binary. It’s built-in (who would have guessed). “bin(n)” converts an integer to a string containing the binary representation of n. It also tacks a ’0b’ at the beginning, so we’ll drop that with “[2:]”.

I think all the bits are in place now. It’s easy enough to write the stupid loop that checks every single thing number up to the bound. In fact, you can do it in a line, if you’ve got an upper bound variable called “bound”:

sum([n for n in xrange(1,bound) if ispali(str(n)) and ispali(bin(n)[2:])])

Surely there’s more efficient code.

I decided to go about it by building up strings I already knew were palindromic decimal numbers. That is, make the right half, and flip it to get the left half. Of course, all of the strings will have even length, and so you’ll never get, for example, a 3 digit number. So I also toss in a pivot digit, which can either be empty or any single digit.

After a while I realized this had a slight glitch. Namely, if your right half is a valid decimal, it won’t have 0s as leading digits, so your palindromes will never have 0s in the middle (or more than one 1, if you set up 0 as a pivot digit), when clearly they should. So in addition to flipping the right side to make the left side, I also allow for middle pivots that are larger strings of 0s.

Here’s what I have:

def solve(digits):
    """ Sum of decimal and binary palindromes up to a bound

    The bound is given by a number of decimal digits.
    E.g., digits = 6 is a bound of 1000000

    Simulatenously palindromic, e.g. 585=1001001001_2
    """
    vals = [1, 3, 5, 7, 9] # all valid answers
    pivots = [''] + [str(n) for n in xrange(0,10)]
    pivots += ['0'*n for n in xrange(2,digits-1)]
    for rhs in xrange(1,10**(digits//2),2): # 2 because only odds
        rhsstr = str(rhs)
        lhs = reverse(rhsstr)
        for p in pivots:
            palstr = lhs+p+rhsstr
            if len(palstr) <= digits and ispali(bin(int(palstr))[2:]):
                vals.append(int(palstr))
    return sum(vals)

Good times. Also good times: writing this post in emacs, and using Eric Finster’s wplatex python package to post it. Well, once I got plastex working in my Ubuntu install. Something strange was going on with an import statement, but I hacked around it a little.