Detailed mathematical approach

Problem Summary

A circular prime is a prime number whose every cyclic digit rotation is also prime. If \(n=197\), the rotations are \(197\), \(971\), and \(719\), so 197 is circular. The task is to count all circular primes below \(10^6\).

The important counting detail is that the problem asks for individual primes, not rotation classes. Thus the orbit \(\{197,971,719\}\) contributes 3, while 11 contributes 1 because its two rotations coincide numerically.

Mathematical Approach

Write a \(k\)-digit number as \(n=d_0d_1\cdots d_{k-1}\). Circular primes are naturally described by the orbit generated by cyclically moving the leftmost digit to the end.

The rotation orbit

Define the one-step left rotation by

$R(d_0d_1\cdots d_{k-1})=d_1d_2\cdots d_{k-1}d_0.$

Then \(n\) is circular exactly when every member of the finite orbit

$\{n,R(n),R^2(n),\dots,R^{k-1}(n)\}$

is prime. After \(k\) rotations we return to the starting arrangement, so \(R^k(n)=n\).

The same rotation can be written arithmetically. If \(n\) has \(k\) digits and \(P=10^{k-1}\), then

$R(n)=10\left(n \bmod P\right)+\left\lfloor \frac{n}{P} \right\rfloor.$

Most orbits have size \(k\), but repeated digits can shorten the orbit. For example, \(11\) is fixed by rotation, so its orbit has size 1 even though it has two digits.

Necessary digit constraints

Suppose a circular prime has at least two digits. If one of its digits were in \(\{0,2,4,5,6,8\}\), some rotation would place that digit in the units position. The rotated number would then be divisible by 2 or 5, so it could not be prime. Therefore every multi-digit circular prime must use only digits from

$\{1,3,7,9\}.$

There is a second useful invariant: rotations preserve the sum of the digits. Hence they also preserve the residue modulo 3. If the digit sum were divisible by 3, then every rotation would be divisible by 3, so the only possible circular prime of that kind would be the single-digit prime 3 itself. This explains why circular primes are extremely sparse.

The provided implementations do not explicitly apply these filters, because a direct scan below one million is already fast enough. Still, these facts give the correct mathematical picture of why the brute-force search works so well.

Why the count is over primes, not over orbits

If one element of a rotation orbit is circular, then every element of the same orbit is circular, because they all have exactly the same set of rotations. The problem, however, does not ask for the number of distinct orbits. It asks for the number of circular primes themselves.

So the orbit \(\{197,971,719\}\) contributes 3 to the answer, while the orbit \(\{11\}\) contributes 1. This is precisely why the direct strategy of scanning every prime below the limit and testing it independently gives the right total.

Worked examples

For \(197\), the orbit is

$197 \to 971 \to 719 \to 197.$

All three distinct values are prime, so each of them is a circular prime.

For \(101\), the rotations are \(101\), \(011\), and \(110\). Interpreted numerically, these are \(101\), \(11\), and \(110\). Since \(110\) is composite, 101 is not circular. This example shows both why a zero digit is fatal and why converting a rotated digit string back to an integer causes no ambiguity in the primality test.

Completing the full search below \(10^6\) yields 55 circular primes.

How the Code Works

Precomputing primality

The C++, Python, and Java implementations begin by building a Sieve of Eratosthenes slightly beyond the requested search bound. That table lets the main loop answer most primality queries in constant time.

Checking the entire rotation orbit

Each implementation then scans upward through the integers below the limit and immediately skips any value that the sieve already marks as composite. For every remaining prime, it generates all cyclic rotations of the decimal representation and tests every rotated value for primality.

The three languages use different syntax for the rotation step, but mathematically they are doing the same thing: computing \(n,R(n),\dots,R^{k-1}(n)\) and requiring all of them to be prime. When a rotated value lies inside the sieve table, the implementation reads the answer directly from the table.

If a user reuses the same programs with a smaller custom bound, a rotation can land beyond the sieve range even though the original number is below the limit. In that case the implementations fall back to ordinary trial division, which preserves correctness for general bounds. For the Project Euler target \(10^6\), every rotation still has at most six digits, so the sieve usually handles the whole job.

Sanity checks

Before reporting the final total, the programs verify two small checkpoints: 197 must be recognized as circular, and the number of circular primes below 100 must be 13. Those checks match the mathematics exactly and guard against mistakes in the rotation logic.

Complexity Analysis

If the search limit is \(L\), building the sieve costs \(O(L \log\log L)\) time and \(O(L)\) space. After that, only prime candidates survive the first filter, so the outer scan effectively visits \(\pi(L)\) numbers.

For a \(k\)-digit prime, the literal implementations construct \(k\) rotated strings and convert them back to integers, so the orbit check is \(O(k^2)\) character-level work in the straightforward string model. Under the Project Euler bound \(L=10^6\), we always have \(k \le 6\), so this is a tiny constant. In practice the runtime is dominated by the sieve and a short scan over the roughly \(78{,}498\) primes below one million.

Footnotes and References

1. Problem page: Project Euler 35
2. Circular primes: Wikipedia - Circular prime
3. Prime numbers: Wikipedia - Prime number
4. Sieve of Eratosthenes: Wikipedia - Sieve of Eratosthenes
5. Cyclic permutation: Wikipedia - Cyclic permutation