Posts Tagged ‘prob35’

Problem 35 – Circular Primes

November 1, 2009

In problem 35 we are asked to find the number of “circular primes” below a bound. A prime is circular if all of the numbers obtained by cyclic permutation of the original number are also prime.

In my first solution, I’ll use my PrimeOracle from a while ago:

from PrimeOracle import PrimeOracle

def iscircularprime(num, isprime):
    if not isprime[num]:
        return False
    numstr = str(num)
    cyclics = [ int(numstr[i:] + numstr[:i]) for i in range(0,len(numstr)) ]
    return reduce(lambda a,b:a and b, map(lambda n: isprime[n], cyclics))

def solve(bound):
    """ Find how many circular primes there are below bound """
    isprime = PrimeOracle(bound)
    return len(set([n for n in range(2,bound) if iscircularprime(n, isprime)]))

This is pretty straightforward. I like how we can make all of the cyclic permutations using that one line (line 7), using the slice notation. And testing if all elements in a list are “True”, using reduce, is nice. I had hoped that maybe instead of the lambda expression I wrote, I could just pass in “and” as the first argument to that reduce. No dice though. Anybody know a nice way? I’ve also wondered about passing in the identity function in that first spot (in a filter, not a reduce), but don’t know how (without a lambda function or so).

Anyway, I think it’s good to have a solution like this that is easy to write and easy to read (hopefully) and, therefore, easy to check for correctness. Then I like to try to make it faster. The code above checks each cyclic permutation of each number many times, which is pointless.

Here’s a slightly faster solution, which doesn’t invoke the PrimeOracle:

def solve(bound):
    """ Find how many circular primes there are below bound """
    # isprime[n] if 2n+3 is prime, eventually
    # so to test if m is prime, check isprime[(m-3)/2]
    isprime = [True for n in range(0, bound//2)]
    for val in xrange(3, bound, 2):
        if isprime[(val-3)//2]:
            for mul in xrange(val*val, bound, 2*val):
                isprime[(mul-3)//2] = False

    ret = 1 # 2 isn't included in isprime, but it is circular
            # we've assumed bound > 2

    # let isprime[n] mean 2n+3 is a prime we haven't checked for circular primality

    And = lambda a,b: a and b # since we'll use it twice

    for val in xrange(3, bound, 2):
        if isprime[(val-3)//2]:
            valstr = str(val)
            circs = [ int(valstr[i:] + valstr[:i])
                      for i in range(0,len(valstr))]
            if reduce(And, map(lambda d:d%2, map(int, valstr))): # no even digits
                if reduce(And, map(lambda n:isprime[(n-3)//2], circs)): # all circs are prime
                    ret += len(set(circs))
            for n in circs:
                isprime[(n-3)//2] = False

    return ret

In line 25, where we increment ret, my original thought was to add len(valstr), since that’s how many cyclic permutations there are. However, these cyclic permutations need not be distinct, so I switched to making a set and getting its length.

What do you think of lines 23 and 24, an if within an if, and not much else? Would it be better (more readable?) to have simply “if () and ()”, even though that’d look best on two lines anyway? I guess python wouldn’t have to make one more nested context for that inner if, if we used 1 instead of 2…

It has, after writing all of this, occured to me that there’s some issues if “bound” isn’t a power of 10. Should we consider only primes such that all cyclic permutations are also primes less than the bound? We’d also have to think about how big to make our isprime array. So it would probably be better to re-write the above code accepting the bound as a number of digits.

Advertisements