Detailed mathematical approach

Problem Summary

Let \(R_n\) denote the base-10 repunit with \(n\) digits, so

$R_n = 11\ldots1 = 1 + 10 + 10^2 + \cdots + 10^{n-1} = \frac{10^n - 1}{9}.$

The task is to find the sum of the first 40 prime numbers dividing \(R_{10^9}\). Since \(R_{10^9}\) has a billion decimal digits, direct construction or factorization is completely out of the question. The solution works by testing primes through modular arithmetic instead of touching the gigantic integer itself.

Mathematical Approach

The whole problem becomes manageable once divisibility of repunits is rewritten in terms of powers of 10 modulo a small number. After that, the only remaining job is to scan primes in increasing order and keep the first 40 that satisfy the derived condition.

Repunits as a geometric series

Because \(R_n\) is a finite geometric sum, multiplying by 9 gives

$10^n - 1 = 9R_n.$

If \(p\) is a prime different from \(2\) and \(5\), then \(10\) is invertible modulo \(9p\), and the divisibility test becomes

$p \mid R_n \iff 9p \mid (10^n - 1) \iff 10^n \equiv 1 \pmod{9p}.$

This is exactly the condition used by the Python and Java implementations. The primes \(2\) and \(5\) can be discarded immediately, because every repunit ends in the digit 1 and therefore is divisible by neither 2 nor 5.

The multiplicative-order viewpoint

For \(p \neq 2,5\), define

$a_p = \operatorname{ord}_{9p}(10),$

the smallest positive exponent for which \(10^{a_p} \equiv 1 \pmod{9p}\). Then the previous congruence is equivalent to

$p \mid R_n \iff a_p \mid n.$

Now specialize to \(n = 10^9 = 2^9 \cdot 5^9\). Any admissible order \(a_p\) must divide \(10^9\), so the prime factors of \(a_p\) can only be 2 or 5. That immediately removes many primes. For example, \(10^2 \equiv 1 \pmod{99}\), so \(a_{11} = 2\), which means \(11 \mid R_{10^9}\). In contrast, \(10^6 \equiv 1 \pmod{63}\) and no smaller positive exponent works, so \(a_7 = 6\). Since \(6 \nmid 10^9\), the prime 7 cannot divide the target repunit.

A divisibility ladder between repunits

Repunits also satisfy a composition identity:

$R_{m+n} = R_m 10^n + R_n.$

If \(n = qm\), repeated use of that formula gives

$R_n = R_m\left(1 + 10^m + 10^{2m} + \cdots + 10^{(q-1)m}\right),$

so \(R_m \mid R_n\) whenever \(m \mid n\). This is a convenient way to build examples. Since \(10 \mid 10^9\), every prime divisor of \(R_{10}\) is automatically a prime divisor of \(R_{10^9}\). The factorization

$R_{10} = 1111111111 = 11 \cdot 41 \cdot 271 \cdot 9091$

already provides four qualifying primes. The same idea explains why the small checkpoint \(R_6\) is useful: because \(R_6 = 3 \cdot 7 \cdot 11 \cdot 13 \cdot 37\), the first four prime factors sum to \(34\).

The special role of the prime 3

The prime 3 is not excluded for the same reason as 2 and 5, but it behaves differently from the generic order discussion because \(9\) already appears in the repunit formula. Here the simplest test is

$R_n = 1 + 10 + \cdots + 10^{n-1} \equiv 1 + 1 + \cdots + 1 \equiv n \pmod{3}.$

Therefore \(3 \mid R_n\) exactly when \(3 \mid n\). For \(n = 10^9\), we have \(10^9 \equiv 1 \pmod{3}\), so \(3\) is not a factor of \(R_{10^9}\). This matches the explicit checkpoint behavior in the C++ implementation: 3 divides \(R_3\), but it does not divide \(R_{10}\).

Fast modular evaluation by doubling

The C++ implementation checks divisibility in an equivalent way: instead of testing \(10^n \bmod 9p\), it computes \(R_n \bmod p\) directly. The key identities are

$R_{2m} = R_m(10^m + 1), \qquad R_{2m+1} = 10R_{2m} + 1.$

These come straight from the composition formula above. When reading the binary digits of \(n\), the algorithm maintains the invariant

$\text{repunit} \equiv R_m \pmod{q}, \qquad \text{power} \equiv 10^m \pmod{q},$

for the prefix length \(m\) processed so far. A doubling step moves from \(m\) to \(2m\); if the next bit is 1, one extra digit 1 is appended and the state moves from \(2m\) to \(2m+1\). That yields an \(O(\log n)\) test even though \(n = 10^9\) is enormous.

How the Code Works

Enumerating prime candidates

The implementations search upward through the primes in increasing order and stop as soon as 40 qualifying primes have been found. They all skip \(2\) and \(5\) immediately. The supplied C++, Python, and Java versions generate primes by trial division rather than by a sieve, which is perfectly adequate because the first 40 successful primes appear relatively early.

Testing one prime

The Python and Java implementations use the congruence

$10^{10^9} \equiv 1 \pmod{9p}.$

They evaluate it with modular exponentiation by repeated squaring, so the billion-sized exponent only costs about \(\log_2(10^9)\) bit steps. The C++ implementation uses the equivalent test \(R_{10^9} \equiv 0 \pmod p\) and obtains that remainder with the doubling recurrence for repunits. Mathematically the two tests are the same; they just package the modular arithmetic in different ways.

Accumulating the answer

Whenever a prime passes the divisibility test, it is added to the running sum and the counter of accepted primes is incremented. The C++ version also includes small checkpoint cases to validate the logic before running the full search: the first four prime factors of \(R_{10}\) sum to \(9414\), the first four prime factors of \(R_6\) sum to \(34\), and the prime 3 only divides repunits whose length is a multiple of 3.

Complexity Analysis

For one candidate prime \(p\), the arithmetic test costs \(O(\log n)\) modular multiplications with \(n = 10^9\). In practice that is only about 30 binary steps, whether one uses modular exponentiation or the doubling recurrence for \(R_n\).

If \(M\) is the largest number examined before the 40th valid prime is found, then the overall running time is dominated by prime generation plus 40-odd successful or unsuccessful modular tests along the way. Because the implementations use trial division, a simple upper-bound model is roughly \(O(M\sqrt{M})\) for the search phase, with very small memory usage. The C++ version stores a short list of previously found primes, while the Python and Java versions use essentially constant auxiliary space beyond ordinary integer arithmetic.

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=132
2. Repunit: Wikipedia - Repunit
3. Multiplicative order: Wikipedia - Multiplicative order
4. Modular exponentiation: Wikipedia - Modular exponentiation
5. Geometric series: Wikipedia - Geometric series