Project Euler Problem 35 Solution: Circular primes

Project Euler Problem 35 Statement

The number 197 is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?

Solution

While researching circular primes (not to be confused with permutable primes) it became clear that the only interesting ones are below one million. After one million the only circular primes are repunits.

Repunits are numbers composed of only 1s and are described in the form R_n = 111...1 (with n ones). Some of these circular-repunit primes include R₁₉, R₂₃, R₃₁₇, R₁₀₃₁, R₄₉₀₈₁, and so on.

To solve this problem, we generate prime numbers under 1 million that contain only the digits {1, 3, 7, 9} (since any prime containing 0, 2, 4, 5, 6, or 8, except 2 and 5, would automatically fail the criteria). For each generated candidate, we rotate it through all possible cyclic permutations and check if each rotation is also a prime. This approach is efficient and straightforward.

The `rotate` function

rotate = lambda s: [s[n:] + s[:n] for n in range(1, len(s))]

The rotate() function takes a string, s, as input and returns a list of all possible rotations of the string. This involves moving some number of characters from the beginning of the string to the end, effectively "rotating" the order of characters.

It uses list comprehension to generate rotations by slicing the string into two parts:

s[n:]: The substring starting from index n to the end.
s[:n]: The substring from the beginning up to (but not including) index n.

These two substrings are then concatenated, resulting in a rotated version of the string where characters from the beginning are moved to the end.

For example, rotate('abcd') returns three strings: 'bcda', 'cdab', and 'dabc' The original string "abcd" is not included.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 35

HackerRank Project Euler 35 wants us to find the sum of the circular primes below 10 ≤ N ≤ 10⁶ instead of a count.

Python Source Code

from Euler import prime_sieve
rotate = lambda s: [s[n:] + s[:n] for n in range(1, len(s))]
s = set('024568')
N = int(input())
primes = set(['2','5']+[str(p) for p in prime_sieve(N) if not set(str(p))&s])

print(sum(int(p)for p in primes if all(y in primes for y in rotate(p))))

Last Word

Reference: The On-Line Encyclopedia of Integer Sequences (OEIS) A068652: Numbers such that every cyclic permutation is a prime.