Solutions for Problem 35

How many prime numbers n are there below 1 million where all lexicographical rotations of n are also prime?

Runtime: 5.324 seconds (on aglaope)

```{- Generate the prime numbers lazily -}
primes :: [Integer]
primes = 2:3:primes'
where
1:p:candidates  = [6*k+r | k <- [0..], r <- [1,5]]
primes'        = p : filter isPrime candidates
isPrime n       = all (not . divides n) \$ takeWhile (\p -> p*p <= n) primes'
divides n p     = n `mod` p == 0

{- Determine how many digits there are for arbitrarily large integers -}
digs :: Integer -> Integer
digs n | n < 10 = 1
digs n = 1 + (digs (div n 10))

{- Return the first digit of an arbitrarily large number -}
firstDig :: Integer -> Integer
firstDig n | n < 10 = n
firstDig n = firstDig (div n 10)

{- Raise a number to a power for arbitrarily large integers -}
pow :: Integer -> Integer -> Integer
pow n 0 = 1
pow n 1 = n
pow n p = n * (pow n (p - 1))

{- Return the rotations of a number, not including the first one -}
rots :: Integer -> [Integer]
rots n = inner dn (pow 10 (dn -1)) n
where
dn = digs n
inner :: Integer -> Integer -> Integer -> [Integer]
inner 1 md n = []
inner acc md n = [ 10 * (mod n md) + firstDig n] ++
(inner (acc - 1) md ( 10 * (mod n md) + firstDig n))

{- Return true if all the digits of the arbitrarily large integer are odd -}
oddDigs :: Integer -> Bool
oddDigs n | n < 10 = mod n 2 == 1
oddDigs n = mod (mod n 10) 2 == 1 && (oddDigs (div n 10))

{- Return true if an integer is an element of a list of integers.
- Note: assumes the list is sorted! -}
elem' :: Integer -> [Integer] -> Bool
elem' n [] = False
elem' n (x:xs) | x == n = True
elem' n (x:xs) | x > n = False
elem' n (x:xs) = elem' n xs

{- The prime numbers less that 1 million that contain only odd digits.
- Note: Can filter for odd digits as lexicographical rotations will be even
-       and hence not prime. -}
p21m = filter oddDigs (takeWhile (< 1000000) primes)

{- Run through the potential primes and for each one see if the rotations are also
- primes. Add one to the result to account for "2". -}
main = print (1 + length (filter (\x -> foldl (\a b -> a && (elem' b p21m)) True (rots x)) p21m))
```

Python by Althalus

Runtime: 1.2 seconds

```import time
import math
start_time=time.time()

#Read in from a long list of Primes I generated for an earlier problem (Why re-generate primes every second problem?)
#Limit the primes list to those below 1000000, and with no even digits in them.
#(Sooner or later during the rotation, one of those digits will be on the end, creating something divisible by 2: IE
#NO prime with an even digit can have all rotations prime.)
file = open(r'primes.txt','r')
primes = [int(i) for i in file.readlines() if int(i) < 1000000 and len(set(i).intersection(set('24680'))) == 0]
file.close()

def isCircularPrime(n):
n = str(n)
for i in range(1,len(n)):
if int(n[i:]+n[0:i]) not in primes:
return False
return True

#The rule that limits my primes unfortunately rips the number 2 out of my list of primes. As 2 IS a prime,
#and is a circular prime, let's just startour count at 1, for the circular prime that got prematurely axed.
count=1
for p in primes:
if isCircularPrime(p):
print p
count+=1
print count
run_time = time.time() - start_time
print run_time
```