Detailed mathematical approach

Problem Summary

For the repunit \(R(k)=\underbrace{11\ldots1}_{k}\), let \(A(n)\) be the smallest positive integer \(k\) such that \(R(k)\) is divisible by \(n\). Problem 129 asks for the least \(n>10^6\) for which \(A(n)\) exceeds \(10^6\). The implementations therefore solve the threshold form of the problem: given \(L\), find the smallest \(n>L\) with \(A(n)>L\).

The important restriction is \(\gcd(n,10)=1\). If \(n\) is divisible by 2 or 5, no repunit can be a multiple of \(n\), because every repunit ends in the digit 1. That observation removes many candidates before any serious work starts.

Mathematical Approach

The key idea is to avoid ever constructing the enormous integer \(R(k)\). Instead, the implementations follow only its remainder modulo \(n\), which turns the problem into a simple recurrence on a finite set of states.

Repunits as a remainder process

The repunits satisfy

$R(1)=1,\qquad R(k+1)=10R(k)+1.$

For a fixed candidate \(n\), define

$r_k \equiv R(k)\pmod n,\qquad 0\le r_k<n.$

Reducing the repunit recurrence modulo \(n\) gives

$r_1\equiv 1\pmod n,\qquad r_{k+1}\equiv 10r_k+1\pmod n.$

By induction, \(r_k\) is always exactly the remainder of \(R(k)\) modulo \(n\). Therefore the quantity we want is

$A(n)=\min\{k\ge 1:r_k=0\}.$

This is the invariant used by all three implementations: after \(k\) steps, the stored remainder corresponds to the \(k\)-digit repunit. No big integers are required, because the state never leaves \(\{0,1,\ldots,n-1\}\).

Why \(\gcd(n,10)=1\) is the right condition

If \(n\) has a factor 2 or 5, divisibility is impossible immediately. The more interesting statement is that when \(\gcd(n,10)=1\), a suitable repunit length is guaranteed to exist. Consider the \(n\) residues \(R(1),R(2),\ldots,R(n)\) modulo \(n\).

If one of them is already 0, then \(A(n)\) exists. Otherwise two residues are equal, say \(R(i)\equiv R(j)\pmod n\) with \(1\le i<j\le n\). Subtracting gives

$R(j)-R(i)=10^iR(j-i)\equiv 0\pmod n.$

Because \(\gcd(n,10)=1\), the factor \(10^i\) is invertible modulo \(n\). Hence \(R(j-i)\equiv 0\pmod n\). So for every \(n\) coprime to 10 there is at least one repunit divisible by \(n\), and in fact \(A(n)\le n-1\).

This proof explains why the search can safely ignore every candidate divisible by 2 or 5 and treat every remaining candidate as having a well-defined first zero remainder.

Worked example: \(n=7\)

The recurrence is easiest to see on a small example. Start with \(r_1=1\). Then

$r_2\equiv 10\cdot 1+1\equiv 4\pmod 7,$

$r_3\equiv 10\cdot 4+1\equiv 6\pmod 7,$

$r_4\equiv 10\cdot 6+1\equiv 5\pmod 7,$

$r_5\equiv 10\cdot 5+1\equiv 2\pmod 7,$

$r_6\equiv 10\cdot 2+1\equiv 0\pmod 7.$

So \(A(7)=6\), which matches the identity \(111111=7\cdot 15873\). The example shows exactly what the code is doing for much larger values: it advances one repunit digit at a time and watches when the remainder first reaches zero.

Turning \(A(n)>L\) into an early-stop test

For a threshold \(L\), the search condition is

$A(n)>L\iff r_k\ne 0\text{ for every }1\le k\le L.$

This equivalence is what makes the implementation efficient. To decide whether a candidate \(n\) qualifies, there is no need to compute the exact value of \(A(n)\) after it passes the threshold. One simply runs the recurrence for at most \(L\) steps.

If a zero remainder appears during those steps, then \(A(n)\le L\) and the candidate is rejected immediately. If the first \(L\) remainders are all nonzero, then automatically \(A(n)>L\), so the candidate qualifies. Because candidates are examined in increasing order starting from \(L+1\), the first successful one is the required answer.

How the Code Works

The C++, Python, and Java implementations all follow the same structure. They begin at \(n=L+1\) with \(L=10^6\), increase \(n\) one by one, and skip every value divisible by 2 or 5 before entering the inner loop. That exactly enforces the necessary condition \(\gcd(n,10)=1\).

For each remaining candidate, the implementation stores only two pieces of information: the current remainder and the current repunit length. Starting from remainder 1, it repeatedly applies the modular update \(r\leftarrow (10r+1)\bmod n\). The loop stops as soon as either the remainder becomes 0 or the length passes the threshold.

If the remainder hits 0 within the first million steps, the candidate is discarded. If the loop survives past the threshold, the current \(n\) is printed and the program terminates. One implementation also includes lightweight sanity checks on smaller cases, such as \(A(7)=6\) and the reduced-threshold result \(L=10\mapsto n=17\), but the mathematical core is identical in all three languages.

Complexity Analysis

Let \(L\) be the threshold and let \(C\) be the number of candidates tested before the first successful one appears. Each candidate is filtered in \(O(1)\) time for divisibility by 2 or 5, and every surviving candidate performs at most \(L\) modular updates. The worst-case running time is therefore \(O(CL)\).

The practical running time is usually smaller than that bound because many candidates reach remainder 0 well before step \(L\), so their inner loops terminate early. Memory usage is \(O(1)\): the algorithm keeps only the current candidate, the current remainder, and a counter.

Footnotes and References

1. Problem page: Project Euler 129 - Repunit Divisibility
2. Repunit: Wikipedia - Repunit
3. Modular arithmetic: Wikipedia - Modular arithmetic
4. Pigeonhole principle: Wikipedia - Pigeonhole principle