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