# Euler Solution 35

### From ProgSoc Wiki

# Solutions for Problem 35

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

## Haskell by SanguineV

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