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