Project Euler Problem 35: Circular Primes

The source code for this problem can be found here.

Problem 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 Discussion

Simply iterate over the primes below one million and count how many satisfy the conditions for a circular prime.

Solution Implementation

from typing import Iterator

from lib.digital import num_digits
from lib.sequence import Primes


def rotated(p: int) -> Iterator[int]:
    """ Generate all rotations of the decimal digits of `p`

    :param p: the initial value of `p`
    :return: a generator of all decimal digit rotations of `p`
    """

    def rotl(x: int, n: int) -> int:
        """ Helper function to rotate the decimal digits of `x` left by one position

        :param x: the integer to rotate
        :param n: the number of decimal digits in `x`
        :return: x left rotated by one digit
        """

        return ((x * 10) + int(x // (10 ** (n - 1)))) % (10 ** n)

    n_digits = num_digits(p, base=10)
    q = rotl(p, n_digits)
    while q != p:
        yield q
        q = rotl(q, n_digits)


def solve():
    """ Compute the answer to Project Euler's problem #35 """

    upper_bound = 1000000

    # Get all primes lower than one million, build a set to make membership tests cheap, i.e. O(1)
    primes = set(Primes(upper_bound=upper_bound))

    # Iterate over the primes, checking for those that are circular
    answer = 0
    for prime in primes:
        for q in rotated(prime):
            if q not in primes:
                break
        else:
            answer += 1

    return answer


expected_answer = 55

solutions.problem35.rotated(p)

Generate all rotations of the decimal digits of p

Parameters:p (int) – the initial value of p Return type:Iterator[int] Returns:a generator of all decimal digit rotations of p

solutions.problem35.solve()

Compute the answer to Project Euler’s problem #35