Circular Primes

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) << (n - 2)) = 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.

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

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 R_n. 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 (R_n), 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.