Detailed mathematical approach

Problem Summary

Let \(R(k)=\frac{10^k-1}{9}=11\ldots1\) be the repunit with \(k\) digits. The problem asks for the sum of all primes \(p<10^5\) such that there is no exponent \(n\ge 1\) with \(p\mid R(10^n)\).

The key point is that one never has to build the enormous numbers \(R(10^n)\) themselves. For each prime, the question can be decided entirely from the multiplicative behavior of \(10\) modulo that prime.

Mathematical Approach

The implementations reduce the whole problem to a yes-or-no test on the multiplicative order of \(10\) modulo \(p\). Once that order is known, the classification is immediate.

From repunits to a congruence

For every integer \(k\ge 1\),

$R(k)=1+10+10^2+\cdots+10^{k-1}=\frac{10^k-1}{9}.$

If \(p\notin\{2,3,5\}\), then \(9\) is invertible modulo \(p\), so multiplying by \(9\) does not change divisibility by \(p\). Therefore

$p\mid R(k)\iff 10^k\equiv 1 \pmod p.$

In this problem the length is not an arbitrary \(k\), but specifically \(k=10^n\). So for primes other than \(2\), \(3\), and \(5\), we are asking whether

$10^{10^n}\equiv 1 \pmod p$

holds for at least one \(n\ge 1\).

Orders built only from \(2\) and \(5\)

Let

$t=\operatorname{ord}_p(10),$

the smallest positive integer such that \(10^t\equiv 1\pmod p\). By definition, \(10^m\equiv 1\pmod p\) happens exactly when \(t\mid m\). Hence

$p\mid R(10^n)\iff t\mid 10^n.$

Now \(10^n=2^n5^n\), so its only prime divisors are \(2\) and \(5\). Therefore \(t\mid 10^n\) for some \(n\) if and only if every prime divisor of \(t\) is either \(2\) or \(5\). Equivalently, after removing all factors \(2\) and \(5\) from \(t\), nothing remains.

So for every prime \(p\notin\{2,3,5\}\),

$p\text{ divides some }R(10^n)\iff \operatorname{ord}_p(10)=2^a5^b\text{ for some }a,b\ge 0.$

The converse is just as important as the forward implication: if \(t=2^a5^b\), then choosing \(n\ge \max(a,b)\) gives \(t\mid 10^n\), so such a prime really does divide one of the required repunits.

Special primes and worked examples

The primes \(2\) and \(5\) are immediate. Every repunit ends in the digit \(1\), so it is divisible by neither \(2\) nor \(5\). Both must therefore be included in the final sum.

The prime \(3\) is special for a different reason: \(9\) is not invertible modulo \(3\), so the previous equivalence must not be used. Instead,

$R(k)=1+10+\cdots+10^{k-1}\equiv 1+1+\cdots+1\equiv k \pmod 3.$

Since \(10^n\equiv 1\pmod 3\), we get \(R(10^n)\equiv 1\pmod 3\). Thus \(3\) never divides any \(R(10^n)\), even though it does divide other repunits such as \(R(3)\).

For a typical nontrivial example, \(p=17\) has \(\operatorname{ord}_{17}(10)=16=2^4\). Because \(16\mid 10^4\), the prime \(17\) divides \(R(10^4)\), so it is excluded from the sum.

By contrast, \(p=19\) has \(\operatorname{ord}_{19}(10)=18=2\cdot 3^2\). The extra factor \(3\) means \(18\nmid 10^n\) for every \(n\), so \(19\) never divides any \(R(10^n)\) and must be included.

A useful sanity check is \(p=7\). Its order is \(6=2\cdot 3\), so \(7\) divides \(R(6)\) but never divides \(R(10^n)\). That is exactly the distinction this problem is testing.

Why reducing divisors of \(p-1\) finds the exact order

For every prime \(p\notin\{2,5\}\), Fermat's little theorem gives \(10^{p-1}\equiv 1\pmod p\). Therefore \(\operatorname{ord}_p(10)\) is a divisor of \(p-1\). This is why the implementations start from the candidate value \(p-1\) instead of searching upward from \(1\).

Suppose the current candidate is \(d\), and \(q\) is a prime divisor of \(d\). If

$10^{d/q}\equiv 1 \pmod p,$

then the true order already divides \(d/q\), so the factor \(q\) can be removed. Repeating that test as long as it succeeds preserves the invariant that the true order divides the current candidate.

When no prime factor can be removed any further, the remaining candidate is the smallest positive exponent producing \(1\), hence it is exactly \(\operatorname{ord}_p(10)\). After that, the final classification is obtained by stripping powers of \(2\) and \(5\) from this order and checking whether the remainder is \(1\).

How the Code Works

The C++, Python, and Java implementations first generate all primes below the limit with a sieve. As each prime is processed, the primes \(2\), \(3\), and \(5\) are handled immediately as guaranteed nonfactors of every \(R(10^n)\).

For every other prime \(p\), the implementation starts from \(p-1\), factors that number into its distinct prime divisors, and repeatedly lowers the candidate order whenever a modular-exponentiation test shows that a smaller divisor still works. This produces the exact multiplicative order of \(10\) modulo \(p\).

Once the order has been found, the code removes factors of \(2\) and \(5\). If the reduced value is \(1\), then the prime can divide some \(R(10^n)\) and is skipped. Otherwise the prime is added to the running total. The C++ and Python versions perform modular exponentiation by repeated squaring; the Java version uses the standard big-integer modular power routine, but the mathematical test is the same in all three languages.

Complexity Analysis

If the search limit is \(L\), the sieve phase costs \(O(L\log\log L)\) time and \(O(L)\) space. Here \(L=10^5\), so this part is tiny.

For a prime \(p\), the order computation factors \(p-1\) by trial division up to \(\sqrt{p-1}\), and each successful or failed reduction test uses modular exponentiation in \(O(\log p)\) multiplications. Since there are only \(9592\) primes below \(10^5\), the total running time is comfortably small, and the memory usage is dominated by the sieve array.

Footnotes and References

1. Problem page: Project Euler 133
2. Repunit: Wikipedia - Repunit
3. Multiplicative order: Wikipedia - Multiplicative order
4. Fermat's little theorem: Wikipedia - Fermat's little theorem
5. Sieve of Eratosthenes: Wikipedia - Sieve of Eratosthenes