Detailed mathematical approach

Problem Summary

We seek decimal integers \(N\) with at least two digits, no trailing zero, and at most 100 digits, such that moving the last digit of \(N\) to the front produces an integer multiple of \(N\). The required output is the sum of all such numbers modulo \(10^5\).

If \(N\) has digits \(x_{d-1}x_{d-2}\dots x_1x_0\), then the rotated number is \(x_0x_{d-1}x_{d-2}\dots x_1\). This rotation preserves the number of digits, so the quotient \(m=\frac{R}{N}\) must satisfy \(1\le m\le 9\). That observation already compresses the search to a small set of multipliers.

Mathematical Approach

Let \(d\) be the number of digits, let \(r=x_0\) be the last digit, and write

$N=10q+r,\qquad 1\le r\le 9.$

The rotation of \(N\) is

$R=r\cdot 10^{d-1}+q,$

and the condition in the problem is

$R=mN,\qquad m\in\{1,2,\dots,9\}.$

The implementations use two equivalent viewpoints: a closed-form identity that shows there is at most one candidate for each triple \((d,m,r)\), and a carry recurrence that constructs that candidate digit by digit without ever forming a huge integer.

One Candidate for Each Length, Multiplier, and Last Digit

Starting from \(R=mN\), multiply by 10 and eliminate \(q\):

$10R=r\cdot 10^d+10q=r\cdot 10^d+N-r=10mN.$

So every solution must satisfy

$\boxed{(10m-1)N=r(10^d-1).}$

Therefore

$\boxed{N=\frac{r(10^d-1)}{10m-1}.}$

This is a crucial simplification. Once \(d\), \(m\), and \(r\) are fixed, the number \(N\) is either uniquely determined or impossible. The search is no longer “all \(d\)-digit numbers”; it is only 81 triples for each digit length.

The formula also explains familiar special cases. When \(m=1\), we get

$N=\frac{r(10^d-1)}{9},$

so every solution is a repdigit \(rr\dots r\), which rotation leaves unchanged.

Carry Propagation from Right to Left

The code does not test divisibility by building the fraction above. Instead it reads the multiplication \(mN=R\) exactly as schoolbook arithmetic. Write

$N=x_{d-1}x_{d-2}\dots x_1x_0$

with \(x_0=r\). Since \(R=x_0x_{d-1}\dots x_1\), the units digit of \(mN\) must be \(x_1\), the tens digit must be \(x_2\), and so on. If \(c_i\) is the carry entering step \(i\) and \(c_0=0\), then for \(0\le i\le d-2\),

$m x_i+c_i=x_{i+1}+10c_{i+1}.$

After the last ordinary digit has been generated, the multiplication must close perfectly:

$m x_{d-1}+c_{d-1}=x_0=r.$

This final equality is stronger than a congruence. It says the most significant output digit is exactly \(r\) and there is no extra carry beyond it. If the generated top digit \(x_{d-1}\) were 0, the candidate would really have fewer than \(d\) digits, so it must also be rejected.

Why the Recurrence Solves the Whole Problem

The recurrence is not an approximation; it is exactly the decimal multiplication rule for \(mN\). If it starts from \(x_0=r\), produces digits \(x_1,x_2,\dots,x_{d-1}\), and then closes back to \(r\), the resulting number satisfies \(mN=R\). Conversely, any valid rotated multiple must obey those same carry equations. So the problem is equivalent to iterating this finite-state process over all \((d,m,r)\).

That viewpoint is especially useful because the Project Euler task asks only for the sum modulo \(10^5\), not for the full decimal expansion of each solution. The implementations can therefore keep a running value of

$N\bmod M=\sum_{i=0}^{d-1} x_i 10^i \bmod M,\qquad M=10^5,$

while the digits are being generated, instead of storing \(N\) itself.

Worked Example: \(142857\)

The classical example comes from \(d=6\), \(m=5\), and \(r=7\). The closed form gives

$N=\frac{7(10^6-1)}{49}=142857.$

The carry recurrence reveals the same number digit by digit:

$5\cdot 7=5+10\cdot 3,$

$5\cdot 5+3=8+10\cdot 2,$

$5\cdot 8+2=2+10\cdot 4,$

$5\cdot 2+4=4+10\cdot 1,$

$5\cdot 4+1=1+10\cdot 2.$

Reading the produced digits from most significant to least significant gives \(142857\), and the closure step is

$5\cdot 1+2=7,$

which matches the original last digit. Therefore

$142857\longrightarrow 714285=5\cdot 142857.$

This is exactly the mechanism the code applies to every permitted length, multiplier, and final digit.

How the Code Works

Enumerating the Compressed Search Space

The C++, Python, and Java implementations loop over digit lengths \(d=2,3,\dots,100\), multipliers \(m=1,2,\dots,9\), and last digits \(r=1,2,\dots,9\). Because the derivation above shows there is at most one candidate for each triple, nothing larger needs to be searched.

Generating Digits and Accumulating \(N \bmod 10^5\)

For each triple, the implementation starts with the known last digit \(r\), then repeatedly applies the carry rule

$m x_i+c_i=x_{i+1}+10c_{i+1}.$

Each new digit \(x_{i+1}\) is immediately added into the running residue

$v\leftarrow v+x_{i+1}\cdot 10^{i+1}\pmod{10^5},$

while the current power of 10 is also maintained modulo \(10^5\). This keeps the memory footprint constant even when the actual number has 100 digits.

Accepting or Rejecting a Triple

After \(d-1\) recurrence steps, the generated current digit is the would-be leading digit. The implementations reject the triple if that digit is 0, because then the number would not truly have \(d\) digits. They also reject it unless the final closure value \(m x_{d-1}+c_{d-1}\) is exactly \(r\). When both tests succeed, the accumulated residue is the contribution of that valid rotated multiple, and it is added to the global sum modulo \(10^5\).

Complexity Analysis

For a fixed triple \((d,m,r)\), the recurrence runs for \(d-1\) steps, so the work is \(O(d)\). Summing over all digit lengths up to \(D\) gives

$\sum_{d=2}^{D} 9\cdot 9\cdot O(d)=O(D^2).$

For the actual problem \(D=100\), this is tiny compared with any brute-force scan over all integers below \(10^{100}\). The memory usage is \(O(1)\), because the implementation stores only the current digit, the carry, a running residue modulo \(10^5\), the current power of 10 modulo \(10^5\), and the total sum.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=168
2. Cyclic number: Wikipedia - Cyclic number
3. Repeating decimal: Wikipedia - Repeating decimal
4. Modular arithmetic: Wikipedia - Modular arithmetic
5. Long multiplication: Wikipedia - Multiplication algorithm