Detailed mathematical approach

Problem Summary

In base \(14\), a positive integer \(x\) is a steady square of length \(n\) if its square ends in the same \(n\) base-\(14\) digits, i.e.

$x^2 \equiv x \pmod{14^n}.$

The code sums the base-\(14\) digit sums of all positive steady squares with at most \(n_{\max}\) digits and prints the final total in base \(14\). The Project Euler final value is intentionally omitted here.

Mathematical Approach

1) Idempotents modulo \(14^n\). The congruence \(x^2 \equiv x \pmod{14^n}\) is equivalent to

$x(x-1)\equiv 0 \pmod{2^n7^n}.$

Because \(\gcd(x,x-1)=1\), for the factor \(2^n\) one of \(x\) and \(x-1\) must be divisible by \(2^n\), so

$x \equiv 0 \text{ or } 1 \pmod{2^n}.$

The same argument modulo \(7^n\) gives

$x \equiv 0 \text{ or } 1 \pmod{7^n}.$

By the Chinese Remainder Theorem there are exactly four idempotent residue classes modulo \(14^n\):

$ (0,0),\quad (1,1),\quad (0,1),\quad (1,0) $

with respect to \((\bmod\,2^n,\bmod\,7^n)\). For \(n=1\) these are exactly

$0,\ 1,\ 7,\ 8 \pmod{14}.$

The branches starting at \(0\) and \(1\) are trivial; the two nontrivial infinite branches start at \(7\) and \(8\). That is why the implementation only tracks those two sequences, while adding the one-digit steady square \(1\) separately.

2) One-step lifting in base \(14\). Suppose \(x\) is already an idempotent modulo

$M=14^k,$

so that

$x^2-x=fM$

for some integer \(f\). Any lift to modulus \(14M=14^{k+1}\) has the form

$x'=x+tM,\qquad t\in\{0,1,\dots,13\}.$

Expanding gives

$x'^2-x'=(x^2-x)+(2x-1)tM+t^2M^2=M\bigl(f+(2x-1)t+t^2M\bigr).$

For divisibility by \(14M\), the bracket must vanish modulo \(14\). Since \(M\) is already a multiple of \(14\), the term \(t^2M\) disappears modulo \(14\), so we only need

$f+(2x-1)t\equiv 0 \pmod{14}.$

3) Why the next digit is unique. For an idempotent, \(x\equiv 0\) or \(1\pmod 2\) and also \(x\equiv 0\) or \(1\pmod 7\). Therefore

$2x-1\equiv \pm 1 \pmod 2,\qquad 2x-1\equiv \pm 1 \pmod 7,$

so \(\gcd(2x-1,14)=1\). Hence \(2x-1\) has a unique inverse modulo \(14\), and the congruence above determines one and only one digit \(t\in\{0,\dots,13\}\). This is the whole reason the algorithm has only one successor per branch at each step.

4) The carry-like state update. After choosing \(t\), divide the bracket by \(14\):

$f'=\frac{f+(2x-1)t+t^2M}{14}.$

Then the lifted value satisfies

$x'^2-x'=f'(14M).$

So the state for the next step is again just \((x',f',14M)\). This is why the implementation can advance each branch using constant-time arithmetic per length.

5) Why \(t\) is the new leading digit. Because \(0\le x<M=14^k\), the number \(x\) occupies at most \(k\) base-\(14\) digits. Adding \(tM=t\cdot 14^k\) inserts one new digit to the left. Therefore the lift

$x'=x+t14^k$

has base-\(14\) representation obtained by prefixing the old \(k\)-digit block with the new digit \(t\).

If \(t=0\), then the lifted idempotent is still valid modulo \(14^{k+1}\), but it is not a genuine \((k+1)\)-digit positive number. That is exactly why the code stores leading_digit and ignores states with leading digit \(0\) when counting steady squares of a fixed length.

6) Concrete branch examples. Starting from the nontrivial roots modulo \(14\):

$7 \to 37 \to \mathrm{c37} \to 0\mathrm{c37} \to \mathrm{a0c37} \to \cdots$

and

$8 \to \mathrm{a8} \to 1\mathrm{a8} \to \mathrm{d1a8} \to 3\mathrm{d1a8} \to \cdots$

The value \(0\mathrm{c37}\) is a valid idempotent modulo \(14^4\), but its new leading digit is \(0\), so it is not counted as a \(4\)-digit steady square. The branch rooted at \(1\) always lifts with \(t=0\), so it only contributes the one-digit number \(1\).

7) Digit-sum accumulation. If a branch currently has digit sum \(\sigma\) and the next leading digit is \(t\), then the new digit sum is simply

$\sigma'=\sigma+t.$

So the code never recomputes digit sums from scratch; it just keeps one running total for the \(7\)-branch and one for the \(8\)-branch. The overall answer starts from

$1$

to count the steady square \(1\), then adds the digit sum of each nonzero-leading branch at every length.

Worked Checkpoints

For the first few lengths, the positive steady squares are:

$ n=1:\ 1,7,8;\qquad n=2:\ 37,\mathrm{a8};\qquad n=3:\ \mathrm{c37},1\mathrm{a8};\qquad n=4:\ \mathrm{d1a8}. $

The cumulative digit-sum totals are therefore

$16,\ 44,\ 85,\ 117,\dots$

and the source file checks that

$S(9)=582,$

which is

$582_{10}=2\mathrm{d}8_{14}.$

It also verifies directly during the first 20 lifts that each tracked branch still satisfies \(x^2\equiv x\pmod{14^n}\).

Complexity Analysis

There are only two nontrivial active branches, and each step performs a constant amount of modular arithmetic and big-integer updates. Therefore the time complexity is

$O(n_{\max}),$

and the extra memory is

$O(1).$

The values of \(x\) themselves become enormous, which is why the code uses cpp_int, but the state space never branches.

Further Reading

1. Problem page: https://projecteuler.net/problem=284
2. Chinese remainder theorem: https://en.wikipedia.org/wiki/Chinese_remainder_theorem
3. Hensel lifting intuition: https://en.wikipedia.org/wiki/Hensel%27s_lemma