Project Euler 35: How many circular primes are there below one million?

In problem 35 of Project Euler we are back to primes., this time it is circular primes that we are focusing on. Before looking more at circular primes lets look at the problem description which reads:

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?

At first I thought circular primes were any permutation of the prime, but then 791 would be in the example as well, so I realised that it is primes that you can rotate such that any rotation is also a prime. There is a long article on different groups of prime numbers at Wikipedia called List of prime numbers. That includes circular primes, so for the lazy reader, you can go there and count them instead of programming the solution.

I must admit that I don’t think I have found a very nice solution, but it runs fast enough to satisfy me. It is a brute force algorithm where we search every prime below 1.000.000 to see if it can be rotated.

Circular primes have two characteristics we will use to speed up the search for all the circular primes.  If it contains an even number or 5 then at some point in the cycle we will encounter a number which is not a prime and thus the number we are investigating is not a circular prime. There are two exceptions to this rule, the primes 2 and 5 are indeed primes even if they follow the rule of containing an even number or five.

The Algorithm

I assume that I have a list of all primes below 1.000.000 for this. This can rather easily be done with a Sieve of Eratosthenes which we built in Problem 10.

  1. Take the first number in the list.
  2. Check if it contains even numbers or five. If not continue to 3. Otherwise discard it and go to 1.
  3. Move the number to a temporary list.
  4. Rotate the number and check if it is a prime. If not discard the temporary list and go to 1.
  5. If the number is in the prime list move it to the temporary list.
  6. if the number is in the temporary list do nothing.
  7. if all rotations are not checked go to 4.
  8. return the length of the temporary list.

This is the algorithm I wrote in order to find the circular primes.

My main philosophy was to stop as soon as I found a number which was not a prime and then remove all the prime numbers already found in  that cycle. The reason I wanted to stop as soon as I encountered a non-prime is that I expect that there are far more candidates than actual circular primes, so I would do a lot more work checking all the cycles to full length.

In C# the implementation of the above looks like:

public int CheckCircularPrimes(int prime){
    int multiplier = 1;
    int number = prime;
    int count = 0;
    int d;

    //Count the digits and check for even numbers
    while (number > 0) {
        d = number % 10;
        if (d % 2 == 0 || d == 5) {
            primes.Remove(prime);
                return 0;
            }
            number /= 10;
            multiplier *= 10;
            count++;
    }
    multiplier /= 10;

    //Rotate the number and check if they are prime
    number = prime;
    List foundCircularPrimes = new List();

    for (int i = 0; i < count; i++) {
        if(primes.Contains(number)) {
            foundCircularPrimes.Add(number);
            primes.Remove(number);
        }else if(!foundCircularPrimes.Contains(number)) {
            return 0;
        }

        d = number % 10;
        number = d * multiplier + number / 10;
    }

    return foundCircularPrimes.Count;
}

The primes list is a SortedSet I have made as an object variable. The main loop of the algorithm looks like

int noCircularPrimes = 2;
primes = new SortedSet<int>(ESieve(1000000));
//Special cases
primes.Remove(2);
primes.Remove(5);

while (primes.Count > 0) {
    noCircularPrimes += CheckCircularPrimes(primes.Min);
}

Even though I don’t really think that it is a nice solution the result of running it is

The number of circular primes below 1.000.000 is 55
Solution took 80 ms

So it is indeed pretty fast. One of the largest speed ups I got was going from a List to a SortedSet for the main prime list.

Closing Remarks

As usual you can find the source code for you to dig into and get all the details if you don’t want to go back to find the Sieve of Eratosthenes as an example.

I don’t really like the solution, so if you have suggestions for better solutions or optimization of this one I would very much like to hear from you.

Posted by Kristian

8 comments

I really enjoyed solving this one. My solution runs slower than yours but still returns the result in only a fraction of a second. I can’t see any obvious ways to speed up my code as written. It would probably need a rewrite to use a new approach to go any quicker I would think.

		TreeSet<Integer> primes = new TreeSet<>();
		int circularPrimes = 0;

		MathHelper.sieveOfEratosthenes(primes, 1000000);

		for (Integer i : primes) {

			String rotation = i.toString();
			Integer[] rotationDigits = new Integer[rotation.length()];
			int primeRotationCount = 0;
			int numberOfRotations = 0;
			
			for (int j = 0; j < rotation.length(); j++) {
				rotationDigits[j] = (int) rotation.charAt(j) - 48;
			}
			
			int currentRotation;
			
			do {
				Collections.rotate(Arrays.asList(rotationDigits), -1);
				
				int toThePowerOf = rotation.length();
				currentRotation = 0;
				for (int k = 0; k < rotation.length(); k++) {
					toThePowerOf--;
					double runningTotal = java.lang.Math.pow(10, toThePowerOf);
					currentRotation += runningTotal * (rotationDigits[k]);
				}
				if ((currentRotation != 2 && currentRotation != 5) && (currentRotation %2 == 0 || currentRotation % 5 == 0)) break;
				if (primes.contains(currentRotation)) primeRotationCount++;
				else break;
				numberOfRotations++;
				if (numberOfRotations == 1 && currentRotation == i) {
					primeRotationCount = rotation.length();
					break;
				}
			} while (currentRotation != i);
			if (primeRotationCount == rotation.length()) {
				circularPrimes++;
			}
		}

Well… actually there was quite an obvious little speed up. I moved the check for primes other than 2 or 5 that contained 2 or 5 to the rotationDigits loop higher up in my code. If I encounter such a prime I just go straight to checking the next prime. Now my implementation runs in the same time yours does. I would be very interested to know if there is a more elegant non brute force solution available. Time to look at some other published solutions I think. Thanks for sharing your insights. This is a really nice site. 🙂

I really don’t get this :/
“so I realised that it is primes that you can rotate such that any rotation is also a prime. ” Won’t any rotation of 197 include 791?
What is the criteria for rotating the numbers if we are not looking at all permutations?

Hi Akhil

By rotating, it means that you remove the first digit and append it to the back. And you can continue doing that until you are back at the first number. In the example you give here you have switched the 7 and 9, which cannot be done by rotation.

Jean-Marie Hachey

Hi Kristian,

The use of Legendre’s constant (1.08366) in your code does not seem to be determinant in the result obtained.
___

Legendre’s constant
http://en.wikipedia.org/wiki/Legendre's_constant

Jean-Marie Hachey

What is the 56th circular prime number which is not a repunit ?

Citations :

“Circular primes
A circular prime number is a number that remains prime on any cyclic rotation of its digits (in base 10).
http://en.wikipedia.org/wiki/List_of_prime_numbers#Circular_primes

Some sources only list the smallest prime in each cycle, for example listing 13 but omitting 31 (OEIS really calls this sequence circular primes, but not the above sequence):
2, 3, 5, 7, 11, 13, 17, 37, 79, 113, 197, 199, 337, 1193, 3779, 11939, 19937, 193939, 199933, 1111111111111111111, 11111111111111111111111 (  A016114)
All repunit primes are circular.”

___

999331 :
The largest known circular prime that is not a repunit prime.
http://primes.utm.edu/curios/page.php/999331.html

______

Using Kristian’s algo (1), here is a table showing the search for the 56th circular prime number

Table 1
Search for the 56th circular prime number
[Re: Project Euler 35: How many circular primes are there below one million? ]

http://img15.hostingpics.net/pics/380603pe35tab1.jpg

___

Sources:
1) Project Euler 35
Kristian’s algorithm
http://www.mathblog.dk/files/euler/Problem35.cs
2) Microsoft Visual C# 2010 Express
3) Microsoft Office Excel (2007)

I took a different approach to this one. As you pointed out, apart from the prime numbers 2 & 5, all other candidate primes must be composed of the digits 1,3,7 and 9. This means there are only 5000 or so candidate numbers (4 + 16 + 64 + 256 + 1024 + 4096). On the other hand, there are 80,000 primes less than 1 million.

It should be quicker to only generate primes to 1000, then generate every permutation (with repetition) of 1,3,7,9 up to 999,999 and check those to see if they are circular primes.

Whether or not it actually is quicker is difficult to tell; I get the answer in 150 milliseconds, which is about twice as long as it took you. However, experience tells me that your solutions tend to run somewhere in the order of 10-100 times faster than mine, even when we are using the same algorithm. For example, my solution to problem 28, which I have reduced to a single calculation, still takes 0.150 milliseconds to run on my computer.

Anyway, you say you’re interested in different solutions, so that’s mine. I like it.

Like Lou Weed, I first generated the candidates by using the digits 1,3,7,9. Since I was constructing with strings, it was also easy to use regex to skip numbers composed entirely of 3 and 9. I started with 3 digits since I know those numbers :-p

The list of my candidates was only 1052 primes (30, 63, 249, 710 for 3,4,5 and 6 digit numbers). It was then fairly quick to for circulars in each list. I’m not sure the times are comparable since I’m using different lang (Groovy) and CPU speed (i5). But i think it will be faster to check for fewer primes.

Leave a Reply