Circular Primes

Last updated on March 24, 2005.


Definition:
A circular prime number is a number that remains prime on any cyclic rotation of its digits. For our purposes, we're only interested in numbers of base 10 (i.e., decimal-based numbers).

Any one-digit prime is circular by default. Thus, the circular one-digit primes are: 2, 3, 5 and 7.

For multi-digit numbers, the digits can only consist of the numbers 1, 3, 7 and 9, since any even digit will eventually be rotated to the unit's place and make the number even, and any number ending with 5 is divisible by the circular prime number 5.

A number consisting entirely of 1s is called a RepUnit (i.e., repetitive unit - denoted as Rn) and is not discussed in detail here. These types of circular primes are easier to factor than the non-RepUnit ones due to Fermat's Little Theorem and other optimized algorithms. One requirement, however, is that the number of units has to be prime.

Rm*n = (10m*n - 1) /9
= ((10m - 1) / 9) * (10m*(n - 1) + 10m*(n - 2) + … + 10m + 1)

= Rm * (10m*(n - 1) + 10m*(n - 2) + … + 10m + 1)

Visually, n Rm's concatenated together would form an Rm*n, as would m Rn's.

11111 1111111111 = Rm*n
   Rm       Rm           Rm

Hence, Rn is prime only if n is prime.

The current list of circular primes are:

2, 3, 5, 7, 11 (R2), 13, 17, 37, 79, 113, 197, 199, 337, 1193, 3779, 11939, 19937, 193939, 199933, R19, R23, R317, and R1031.

A few more potential circular primes are:

R49081 and R86453.

Methodologies:

#1 - Numbers

This is probably the easiest method to implement.

With the exception of the numbers 2 and 5, the digits of any circular prime have to be 1, 3, 7, or 9.

Since we're trying to optimize the algorithm, let us assume the following decimal-to-binary, one-to-one mapping:

Thus, for two-digit numbers,

Let's look at 32-bit binary numbers.

Assume, n = 677643.

0FEDCBA9876543210FEDCBA987654321 = 32 bits

00000000000010100101011100001011 = 677643 ↔ 7733391179

00000000000011101001010111000010 = 955842 ↔ 9773339117

Thus, to rotate any integer with n digits, we just perform a couple of bitwise shifts on the current integer and compare the new one with the old.

Let number = 677643, then n = 6.
Then, rotated number = (number >> 2) + ((number & 0x3) << (2 * (n - 1))) = 955842.
Since, 955842 > 677643, we continue rotating. If all rotations are greater than the original number, then the number and all its rotations are tested for primality. If at any rotation the number is less than or equal to the original number, we break out of the rotation loop and move on to the next number.

This works well when testing 32 and 64-bit decimal numbers, or digits up to length 16 and 32.

#2 - Links

Method #1 can be combined with a linked list to speed up the search and remove method.

To search for 3-digit circular numbers, we first create a list of all 3-digit numbers that begin with 1.

Then, to find the 3-digit numbers that begin with 3, we start searching through the list of numbers beginning with 1 from 133.

Next, we find the 3-digit numbers that begin with 7 by searching through the list of numbers beginning with 3 found from 377.

Since 333 and 777 are divisible by 3 and 7, respectively, we can just as easily skip those numbers. If the number is 0, then no rotation is performed, and a special algorithm to check primality for RepUnits is used.

This method can easily be extended to search for circular primes of any size.

Note: There are no circular primes that begin with 9.

0000000160100003210000048110000
1000001170100013310000149110001
2000010180100103410001050110010
3000011190100113510001151110011
4000100200101003610010052110100
5000101210101013710010153110101
6000110220101103810011054110110
7000111230101113910011155110111
8001000240110004010100056111000
9001001250110014110100157111001
10001010260110104210101058111010
11001011270110114310101159111011
12001100280111004410110060111100
13001101290111014510110161111101
14001110300111104610111062111110
15001111310111114710111163111111
#3 - Strings

This is probably the most efficient method.

Let's assume we're checking all primes with a fixed number of digits (n), and we're starting at Rn. Without loss of generality, let's assume n = 6. Then our sequence is 111111 → 111113 → 111117 → 111119. From 111119, we go to 111133, since starting at 111131 would imply a rotation 111113 that is already covered. The unit digit can only be equal to the leading digit when all the digits are 1 (Rn), otherwise it is divisible by 3, 7, or 9.

To assure numbers that cannot be rotated into smaller numbers, whenever we're about to increment the last 9, from the unit's end, we add 2 to the digit before it (and skip over 5s) and concatenate the remaining digits from the beginning and increment the unit digit by 2. If the number before that is 9, we increment the first non-9 before that and concatenate the rest from the beginning (i.e., 191999 → 193999 → 193193 → 193197, with the two middle steps shown for comprehension).

Thus, we guarantee no smaller number on rotation.


Downloads:

Resources: