Solution

Answer: 5a411d7b

A steady square in base $14$ is a number $x$ satisfying

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

for some digit length $n$. Equivalently,

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

Because $14=2\cdot 7$, the Chinese Remainder Theorem is the key idea.

1. Mathematical analysis

We must solve

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

This factors as

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

Since $\gcd(x,x-1)=1$, one of $x,x-1$ must absorb all powers of $2$, and the other all powers of $7$.

Thus modulo $14^n$, there are exactly four idempotents:

$x\equiv 0$
$x\equiv 1$
$x\equiv 0\pmod{2^n},\ x\equiv 1\pmod{7^n}$
$x\equiv 1\pmod{2^n},\ x\equiv 0\pmod{7^n}$

The first two are trivial.

The last two generate the nontrivial steady squares.

Lifting a solution from $14^n$ to $14^{n+1}$

Suppose $x_n$ satisfies

$$x_n^2-x_n = k,14^n.$$

We seek

$$x_{n+1}=x_n+c14^n$$

with $c\in{0,\dots,13}$.

Substitute:

$$(x_n+c14^n)^2-(x_n+c14^n).$$

Expanding:

$$x_n^2-x_n + c14^n(2x_n-1)+c^2 14^{2n}.$$

Since $x_n^2-x_n=k14^n$,

$$=14^n\left(k+c(2x_n-1)+c^2 14^n\right).$$

For divisibility by $14^{n+1}$, we need

$$k+c(2x_n-1)\equiv 0 \pmod{14}.$$

Because $2x_n-1$ is invertible modulo $14$, the digit $c$ is uniquely determined.

So every solution lifts uniquely digit-by-digit.

Tracking digit sums

If the new digit added is $c$, then

$$s(x_{n+1}) = s(x_n)+c.$$

We therefore only need to maintain:

the current solution $x_n$,
the carry term $k$,
the running digit sum.

This makes the computation feasible even for $n=10000$.

2. Python implementation

def solve(limit=10000):
    # Two nontrivial solutions modulo 14:
    # 7 and 8
    roots = [7, 8]

    # Digit sums
    digit_sums = [7, 8]

    # k values where:
    # x^2 - x = k * 14^n
    # for n = 1 initially
    k_values = [3, 4]

    # Include the trivial 1-digit steady square "1"
    total = 1 + 7 + 8

    power14 = 14

    # Build solutions up to length = limit
    for n in range(1, limit):

        new_roots = []
        new_digit_sums = []
        new_k_values = []

        for x, ds, k in zip(roots, digit_sums, k_values):

            # Solve:
            # k + c(2x-1) == 0 (mod 14)
            inv = pow((2 * x - 1) % 14, -1, 14)
            c = (-k * inv) % 14

            # Lift solution
            y = x + c * power14

            # New carry term
            new_k = (
                k + c * (2 * x - 1) + c * c * power14
            ) // 14

            new_roots.append(y)
            new_digit_sums.append(ds + c)
            new_k_values.append(new_k)

        roots = new_roots
        digit_sums = new_digit_sums
        k_values = new_k_values

        # Count only genuine (n+1)-digit numbers
        lower_bound = power14

        for x, ds in zip(roots, digit_sums):
            if x >= lower_bound:
                total += ds

        power14 *= 14

    return total

def to_base14(n):
    digits = "0123456789abcd"

    if n == 0:
        return "0"

    out = []

    while n:
        out.append(digits[n % 14])
        n //= 14

    return "".join(reversed(out))

ans = solve(10000)
print(ans)
print(to_base14(ans))

3. Code walkthrough

Initialization

roots = [7, 8]

The two nontrivial steady squares modulo $14$.

digit_sums = [7, 8]

Their digit sums.

k_values = [3, 4]

Because:

$$7^2-7=42=3\cdot 14,$$

$$8^2-8=56=4\cdot 14.$$

Lifting step

For each current root $x$, solve:

c = (-k * inv) % 14

which enforces:

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

Then append digit $c$:

y = x + c * power14

Updating the carry

new_k = (
    k + c * (2 * x - 1) + c * c * power14
) // 14

This comes directly from the expansion of

$$(x+c14^n)^2-(x+c14^n).$$

4. Verification

The problem statement says that for $1\le n\le 9$, the answer should be

$$2d8_{14}.$$

Running the program for $9$ gives exactly:

$$582_{10}=2d8_{14},$$

so the implementation matches the example.

The final computation for $n\le 10000$ gives:

$$604557993_{10}.$$

Converting to base $14$:

$$604557993_{10}=5a411d7b_{14}.$$

Everything is consistent.

Answer: 5a411d7b

Project Euler Problem 284