# 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 11111 … 11111 = 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:

• 1 ↔ 00
• 3 ↔ 01
• 7 ↔ 10
• 9 ↔ 11

Thus, for two-digit numbers,

• 0   ↔ 0000 ↔ 11
• 1   ↔ 0001 ↔ 13
• 2   ↔ 0010 ↔ 17
• 3   ↔ 0011 ↔ 19
• 4   ↔ 0100 ↔ 31
• 5   ↔ 0101 ↔ 33
• 6   ↔ 0110 ↔ 37
• 7   ↔ 0111 ↔ 39
• 8   ↔ 1000 ↔ 71
• 9   ↔ 1001 ↔ 73
• 10 ↔ 1010 ↔ 77
• 11 ↔ 1011 ↔ 79
• 12 ↔ 1100 ↔ 91
• 13 ↔ 1101 ↔ 93
• 14 ↔ 1110 ↔ 97
• 15 ↔ 1111 ↔ 99

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.

 0 000000 16 010000 32 100000 48 110000 1 000001 17 010001 33 100001 49 110001 2 000010 18 010010 34 100010 50 110010 3 000011 19 010011 35 100011 51 110011 4 000100 20 010100 36 100100 52 110100 5 000101 21 010101 37 100101 53 110101 6 000110 22 010110 38 100110 54 110110 7 000111 23 010111 39 100111 55 110111 8 001000 24 011000 40 101000 56 111000 9 001001 25 011001 41 101001 57 111001 10 001010 26 011010 42 101010 58 111010 11 001011 27 011011 43 101011 59 111011 12 001100 28 011100 44 101100 60 111100 13 001101 29 011101 45 101101 61 111101 14 001110 30 011110 46 101110 62 111110 15 001111 31 011111 47 101111 63 111111
#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: