Posts Tagged ‘prob37’

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.

Advertisements