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

Written by on 9 April 2011

Topics: Project Euler

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.

8 Comments For This Post I'd Love to Hear Yours!

  1. pmc says:

    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++;
    			}
    		}
    
  2. pmcRetro says:

    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. 🙂

  3. Akhil says:

    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?

  4. Kristian says:

    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.

  5. Jean-Marie Hachey says:

    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

  6. Jean-Marie Hachey says:

    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)

  7. Lou Weed says:

    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.

  8. Ayman says:

    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 Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

This site uses cookies.