Circular primes below 10^1025

Question

The problem

Project Euler: 35 is stated in the following way

Circular primes

Problem 35

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?

My attempt

I solved this question some time ago, and have now come back to it because I saw it pop up a few times here on CR. I wanted to over-engineer the problem and instead of finding the circular primes under a million I wanted to find them under some crazy big number.

It is not terribly quick, but uses that all circular primes above a million are repunit primes with a prime number of digits.

I included two different ways of checking whether a number (or in this case a list of numbers) is a circular prime. I use the following

def is_circular_2(p):
    for i in range(len(p)):
        if not isprime(int(''.join(map(str, p[i:]+p[:i])))):
            return False
    return True

However after some quick googling, the following seem to be the "preferred" way

def lst_2_int(lst):
    return int(''.join(map(str, lst)))

def is_circular(p):
    return all(isprime(lst_2_int(p[i:]+p[:i])) for i in range(len(p)))

However after some light speedtests using timeit, this version is a tad slower. As many other answers do I cycle through the products of the odd integers [1, 3, 7, 9] since no prime can end in an even integer, or 5.

I do not bother saving the primes or non primes already found. Is it "worth" it? isprime from the primefac libary already seems quite fast. To find the really big circular primes I iterate over the repunit primes. Eg primes only consisting of 1`s. No need to check if it is circular. I also used the small increase that a repunit number is prime if and only if it contains a prime number of digits.

Looking for any sort of general comments on my code. Not sure if my code can be improved speedwise, but comments there are appreciated as well.

The code

from primefac import isprime, primes
from itertools import product  # cartesian product

'''
Circular primes
Project Euler: Problem 35

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?
'''


def lst_2_int(lst):
    return int(''.join(map(str, lst)))


def is_circular(p):
    return all(isprime(lst_2_int(p[i:]+p[:i])) for i in range(len(p)))


def is_circular_2(p):
    for i in range(len(p)):
        if not isprime(lst_2_int(p[i:]+p[:i])):
            return False
    return True


def repunit(k):
    return (10**k-1)//9


def find_circular_primes_under(digits):

    if type(digits) != int or digits <= 0:
        raise ValueError(
            "Error: power needs to be a positive integer, 10^input")

    circular_lst = []
    # Circular primes under 10
    total = 0
    for k in xrange(10):
        if isprime(k):
            circular_lst.append(k)

    # Circular primes under 10^6
    for k in xrange(2, min(digits+1, 7)):
        for combo in product([1, 3, 7, 9], repeat=k):
            if is_circular_2(list(combo)):
                circular_lst.append(lst_2_int(combo))

    # All circular primes over 10^6 are repunit primes (1...1 where ... =
    # index)
    if digits > 6:
        prime_lst = primes(digits+1)
        # All repunit primes have a prime number of digits
        for prim in prime_lst[3::]:
            if isprime(repunit(prim)):
                circular_lst.append('1 ... 1 ['+str(prim)+']')
    return circular_lst

if __name__ == '__main__':

    circular_primes = find_circular_primes_under(400)
    for prim in circular_primes:
        print prim
    print "Found a total of", len(circular_primes), 'circular primes.'

Answer 1

An optimisation for values under 10^6 (or if you want to ignore the conjecture)

Primality tests can be expensive, especially for big values. At the moment, you often perform the same primality check on the same value multiple times. For instance, with the same "base number" 199933, you'll:

• consider 199933 and check the primality of its rotations (199933, 319993, 331999, 933199, 993319, 999331)
• consider 319993 and check the primality of its rotations (319993, 331999, 933199, 993319, 999331, 199933).
• etc.

It may be a better option when considering a new permutation to handle all the rotations in one go. For instance, you could decide that a given permutation is interesting only if it corresponds to the smallest of its roations.

Then you'd have something like (a set is used to get rid of duplicated rotations):

# Circular primes
for k in xrange(2, digits+1):
    for p in product(['1', '3', '7', '9'], repeat=k):
        p_int = int(''.join(p))
        perm = {int(''.join(p[i:] + p[:i])) for i in range(len(p))}
        if p_int == min(perm) and all(isprime(n) for n in perm):
            circular_sets.append(perm)

Now the primality is never checked more than once for a given number.

Answer 2

It's hard to review this kind of code unless there's a clear idea of what your self-imposed constraints are. What I mean by this is that the code makes use of an assumption (all permutable primes over \$10^6\$ are repunits) that it does not check. But if it is legitimate to make use of assumptions that the program itself does not check, then it would be much faster to avoid all those calls to isprime and write:

# https://oeis.org/A004023
A004023 = 19, 23, 317, 1031, 49081, 86453, 109297, 270343
circular_lst.extend((10**p - 1) // 9 for p in A004023 if p <= digits)