Detailed mathematical approach

Problem Summary

For a positive integer \(k\), let \(R(k)\) be the base-10 repunit with \(k\) ones: $R(k)=\underbrace{11\ldots1}_{k}=\frac{10^k-1}{9}.$ For every \(n\) with \(\gcd(n,10)=1\), define \(A(n)\) as the least \(k\ge 1\) such that \(R(k)\equiv 0 \pmod{n}\). The problem asks for the sum of the first 25 composite integers \(n\) for which \(A(n)\mid(n-1)\).

The reason this is interesting is that primes already behave this way: every prime \(p>5\) satisfies \(A(p)\mid(p-1)\). Problem 130 asks for composite numbers that imitate that prime-style repunit divisibility property.

Mathematical Approach

The implementations do not factor numbers, build giant repunits, or use heavy algebraic machinery. They rely on the definition of \(A(n)\), a simple remainder recurrence, and a direct search over composite candidates.

Repunits and the meaning of \(A(n)\)

The quantity \(A(n)\) is the first length for which a repunit becomes divisible by \(n\). The condition \(\gcd(n,10)=1\) is essential: if \(n\) shared a factor with 2 or 5, no number ending in digit 1 could be divisible by \(n\).

Existence of \(A(n)\) follows from a pigeonhole argument. Consider the residues of \(R(1),R(2),\ldots,R(n)\) modulo \(n\). If one of them is already 0, we are done. Otherwise two of them are equal, say \(R(i)\equiv R(j)\pmod n\) with \(i>j\). Then

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

Because \(\gcd(10,n)=1\), the factor \(10^j\) is invertible modulo \(n\), so \(R(i-j)\equiv 0\pmod n\). Thus \(A(n)\) always exists, and in fact \(A(n)\le n\).

When \(3\nmid n\), this is equivalent to saying that \(A(n)\) is the multiplicative order of 10 modulo \(n\). The implementations do not need that reformulation; they work directly with repunit remainders, which also handles multiples of 3 uniformly.

Why primes automatically satisfy the condition

For a prime \(p>5\), Fermat's little theorem gives

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

Since \(p\neq 3\), the number 9 is invertible modulo \(p\), so

$R(p-1)=\frac{10^{p-1}-1}{9}\equiv 0 \pmod p.$

By definition, \(A(p)\) is the smallest repunit length divisible by \(p\), so \(A(p)\mid(p-1)\). The target numbers in this problem are composites for which the same divisibility pattern still happens.

Rewriting \(A(n)\mid(n-1)\) in repunit form

Suppose \(A(n)=a\). Then \(n\mid R(a)\), and the desired condition is \(a\mid(n-1)\). If we write \(n-1=qa\), then the standard factorization of repunits gives

$R(qa)=R(a)\left(1+10^a+10^{2a}+\cdots+10^{(q-1)a}\right).$

Therefore \(n\mid R(a)\) immediately implies \(n\mid R(n-1)\) whenever \(A(n)\mid(n-1)\). Conversely, if \(n\mid R(n-1)\), then the minimality of \(A(n)\) forces \(A(n)\mid(n-1)\). So the problem is exactly about composite \(n\) for which the repunit \(R(n-1)\) is divisible by \(n\).

The remainder recurrence used by the implementations

The core invariant in the code is the remainder of the current repunit modulo \(n\). If we define

$r_k\equiv R(k)\pmod n,$

then appending one more digit 1 turns \(R(k)\) into \(10R(k)+1\), so the remainders satisfy

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

That gives a tiny loop: start from the remainder of 1, keep appending another 1 in modular arithmetic, and stop when the remainder becomes 0. The first index where this happens is exactly \(A(n)\). No repunit is ever stored as a large integer; only one remainder and one length counter are maintained.

Worked Example: \(n=91\)

The composite number 91 is coprime to 10, so \(A(91)\) exists. Using the recurrence:

$\begin{aligned} r_1&=1,\\ r_2&\equiv 11,\\ r_3&\equiv 111\equiv 20\pmod{91},\\ r_4&\equiv 10\cdot 20+1=201\equiv 19\pmod{91},\\ r_5&\equiv 10\cdot 19+1=191\equiv 9\pmod{91},\\ r_6&\equiv 10\cdot 9+1=91\equiv 0\pmod{91}. \end{aligned}$

So \(A(91)=6\). Since \(6\mid 90=91-1\), the number 91 is one of the composites counted by the problem.

How the Code Works

Scanning candidate values

The C++, Python, and Java implementations scan odd integers \(n=3,5,7,\ldots\) upward. Multiples of 5 are skipped immediately, primes are rejected, and an explicit \(\gcd(n,10)=1\) check keeps the search aligned with the definition of \(A(n)\).

Computing \(A(n)\) by modular updates

For each remaining composite candidate, the implementation runs the recurrence for repunit remainders. Each loop iteration corresponds to appending one more digit 1, reducing modulo \(n\), and increasing the current length by 1. The moment the remainder becomes 0, that length is \(A(n)\).

Testing the prime repunit property

Once \(A(n)\) has been found, the acceptance test is just

$ (n-1)\bmod A(n)=0. $

If the divisibility holds, the implementation counts \(n\), adds it to the running sum, and continues until 25 such composites have been found.

Complexity Analysis

For one candidate \(n\), the hand-written primality tests in the C++ and Java versions take \(O(\sqrt n)\) time in the worst case, while the repunit loop takes \(O(A(n))\) steps and \(O(1)\) extra memory. Because \(A(n)\le n\), a coarse upper bound for scanning all candidates up to some limit \(N\) is \(O(N^2)\) time and \(O(1)\) auxiliary space.

That bound is deliberately conservative. In practice the search is much faster because only odd numbers not divisible by 5 are examined, and the computation stops as soon as 25 valid composites have been accumulated.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=130
2. Repunit: Wikipedia - Repunit
3. Multiplicative order: Wikipedia - Multiplicative order
4. Fermat's little theorem: Wikipedia - Fermat's little theorem
5. Modular arithmetic: Wikipedia - Modular arithmetic