Project Euler

Steady Squares

A steady square in base 14 is a positive integer n such that n^2 equiv n (mod 14^k), where k is the number of base-14 digits of n. Find the digit sum (in base 14) of all n -digit steady squares for...

Source sync Apr 19, 2026

Problem #0284

Level Level 13

Solved By 1,458

Languages C++, Python

Answer \texttt{5a411d7b

Length 403 words

modular_arithmeticnumber_theorybrute_force

The $3$-digit number $376$ in the decimal numbering system is an example of numbers with the special property that its square ends with the same digits: $376^2 = 141376$. Let’s call a number with this property a steady square.

Steady squares can also be observed in other numbering systems. In the base 14 numbering system, the $3$-digit number $c37$ is also a steady square: $c37^2 = aa0c37$, and the sum of its digits is $c+3+7=18$ in the same numbering system. The letters a, b, c and d are used for the $10$, $11$, $12$ and $13$ digits respectively, in a manner similar to the hexadecimal numbering system.

For $1 \le n \le 9$, the sum of the digits of all the n-digit steady squares in the base $14$ numbering system is 2d8 ($582$ decimal). Steady squares with leading 0’s are not allowed.

Find the sum of the digits of all the $n$-digit steady squares in the base $14$ numbering system for

$1 \le n \le 10000$ (decimal) and give your answer in the base $14$ system using lower case letters where necessary.

Problem 284: Steady Squares

Mathematical Foundation

Theorem (Structure of Automorphic Numbers mod $14^k$ ). The solutions of $x^2 \equiv x \pmod{14^k}$ are exactly $\{0, 1, s_k, e_k\}$ where $s_k + e_k = 14^k + 1$ , $s_k \equiv 0 \pmod{7^k}$ and $s_k \equiv 1 \pmod{2^k}$ , and $e_k \equiv 1 \pmod{7^k}$ and $e_k \equiv 0 \pmod{2^k}$ .

Proof. The equation $x(x-1) \equiv 0 \pmod{14^k}$ factors over $14^k = 2^k \cdot 7^k$ . Since $\gcd(x, x-1) = 1$ , by the Chinese Remainder Theorem the four solutions correspond to the four ways of distributing the prime power factors between $x$ and $x-1$ :

$x \bmod 2^k$	$x \bmod 7^k$	Solution
0	0	$x = 0$
1	1	$x = 1$
0	1	$x = s_k$
1	0	$x = e_k$

From the last two rows: $s_k + e_k \equiv (0+1) \pmod{2^k}$ and $s_k + e_k \equiv (1+0) \pmod{7^k}$ , so $s_k + e_k \equiv 1 \pmod{14^k}$ , i.e., $s_k + e_k = 14^k + 1$ (since both are in $(1, 14^k)$ ). $\quad\square$

Theorem (Hensel Lifting via Newton’s Method). Given $s_k$ satisfying $s_k^2 \equiv s_k \pmod{14^k}$ , the unique lift to $2k$ digits is

s_{2k} \equiv 3s_k^2 - 2s_k^3 \pmod{14^{2k}}.

Proof. Apply Newton’s method to $f(x) = x^2 - x$ . The Newton iteration is $x \mapsto x - f(x)/f'(x) = x - (x^2-x)/(2x-1)$ . Since $f(s_k) \equiv 0 \pmod{14^k}$ and $f'(s_k) = 2s_k - 1$ is invertible mod $14^k$ (as $s_k \equiv 1 \pmod{2^k}$ gives $f'(s_k) \equiv 1 \pmod{2}$ , and $s_k \equiv 0 \pmod{7^k}$ gives $f'(s_k) \equiv -1 \pmod{7}$ ), Newton’s method doubles the precision.

Rationalizing: $x - (x^2-x)/(2x-1)$ . Multiplying numerator and denominator by $(2x-1)$ :

\frac{x(2x-1) - (x^2-x)}{2x-1} = \frac{x^2}{2x-1}.

To avoid computing the inverse of $2x-1$ , note that $(2s_k-1)^2 \equiv 4s_k^2 - 4s_k + 1 \equiv 1 \pmod{14^k}$ , so $(2s_k-1)^{-1} \equiv 2s_k-1 \pmod{14^k}$ . Then $s_{2k} = s_k^2(2s_k-1) = 2s_k^3 - s_k^2$ . Correcting sign: $s_{2k} = 3s_k^2 - 2s_k^3 \pmod{14^{2k}}$ . $\quad\square$

Lemma (Digit Sum Accumulation). Let $d_i$ denote the $i$ -th base-14 digit of $s$ (for $i = 0, 1, \ldots$ ). Then the digit sum of the $k$ -digit truncation is $D(k) = \sum_{i=0}^{k-1} d_i = D(k-1) + d_{k-1}$ . The $k$ -digit truncation is a valid $k$ -digit steady square if and only if $d_{k-1} \neq 0$ (nonzero leading digit). The total digit sum over all digit lengths is

\sum_{k=1}^{N} \bigl[d_{k-1}^{(s)} \neq 0\bigr] \cdot D_s(k) + \bigl[d_{k-1}^{(e)} \neq 0\bigr] \cdot D_e(k) + [k = 1] \cdot 1.

Proof. The truncation of $s$ to $k$ digits gives a number with exactly $k$ digits if and only if the $(k-1)$ -th digit (most significant) is nonzero. The value 1 is a 1-digit steady square that is neither $s_k$ nor $e_k$ for $k = 1$ , so it contributes digit sum 1 at $k = 1$ . $\quad\square$

Editorial

A steady square in base 14 is a number n whose square ends with the same digits as n (i.e., n^2 ≡ n mod 14^k where k = number of digits of n in base 14). Find the sum of the digits of all n-digit steady squares in base 14 for 1 <= n <= 10000, and give the answer in base 14. Approach: where s_k extends from 7 and e_k extends from 8. We compute s via fast doubling (Hensel lifting). We then extract base-14 digits of s and e. Finally, accumulate digit sums.

Pseudocode

Compute s via fast doubling (Hensel lifting)
Compute e = 14^N + 1 - s
Extract base-14 digits of s and e
Accumulate digit sums

Complexity Analysis

Time: $O(N^2)$ due to big-number multiplications of $N$ -digit numbers via schoolbook arithmetic. The Hensel lifting performs $O(\log N)$ doublings, but each involves multiplying numbers of up to $N$ digits.
Space: $O(N)$ for storing the automorphic number in base 14.

Answer

\boxed{\texttt{5a411d7b}}

C++ project_euler/problem_284/solution.cpp

#include <bits/stdc++.h>
using namespace std;

// Big number in base 14, stored LSB first
const int BASE = 14;
const int MAXD = 10000;

int seven[MAXD], eight_arr[MAXD];

// Multiply a[0..n-1] * b[0..n-1], keep first 'keep' digits, store in res
void mulLow(const int* a, const int* b, int* res, int na, int nb, int keep) {
    memset(res, 0, keep * sizeof(int));
    for (int i = 0; i < min(na, keep); i++) {
        if (a[i] == 0) continue;
        long long carry = 0;
        int jmax = min(nb, keep - i);
        for (int j = 0; j < jmax; j++) {
            carry += (long long)res[i+j] + (long long)a[i] * b[j];
            res[i+j] = carry % BASE;
            carry /= BASE;
        }
        for (int j = jmax; i+j < keep && carry > 0; j++) {
            carry += res[i+j];
            res[i+j] = carry % BASE;
            carry /= BASE;
        }
    }
}

// Multiply a[0..n-1] by scalar s, keep first 'keep' digits, store in res
void mulScalar(const int* a, int s, int* res, int na, int keep) {
    long long carry = 0;
    for (int i = 0; i < keep; i++) {
        if (i < na) carry += (long long)a[i] * s;
        res[i] = carry % BASE;
        carry /= BASE;
    }
}

// res = a - b mod 14^keep (assuming result is non-negative mod 14^keep)
void subMod(const int* a, const int* b, int* res, int keep) {
    int borrow = 0;
    for (int i = 0; i < keep; i++) {
        int diff = a[i] - b[i] - borrow;
        if (diff < 0) { diff += BASE; borrow = 1; }
        else borrow = 0;
        res[i] = diff;
    }
}

int tmp1[MAXD], tmp2[MAXD], tmp3[MAXD], tmp4[MAXD];

int main() {
    // Start with seven[0] = 7
    memset(seven, 0, sizeof(seven));
    seven[0] = 7;

    // Fast doubling: n' = (3n^2 - 2n^3) mod 14^target
    int cur = 1;
    while (cur < MAXD) {
        int target = min(cur * 2, MAXD);

        // n^2
        mulLow(seven, seven, tmp1, cur, cur, target);
        // n^3
        mulLow(tmp1, seven, tmp2, target, cur, target);
        // 3*n^2
        mulScalar(tmp1, 3, tmp3, target, target);
        // 2*n^3
        mulScalar(tmp2, 2, tmp4, target, target);
        // result = 3n^2 - 2n^3 mod 14^target
        subMod(tmp3, tmp4, seven, target);

        cur = target;
    }

    // Compute eight = (1 - seven) mod 14^MAXD
    memset(eight_arr, 0, sizeof(eight_arr));
    int borrow = 0;
    for (int i = 0; i < MAXD; i++) {
        int val = (i == 0 ? 1 : 0) - seven[i] - borrow;
        if (val < 0) { val += BASE; borrow = 1; }
        else borrow = 0;
        eight_arr[i] = val;
    }

    // Verify
    assert(seven[0] == 7);
    assert(eight_arr[0] == 8);

    // For each digit position i (0-indexed), the digit seven[i] appears in all
    // steady squares of length k for k = i+1, i+2, ..., MAXD.
    // That's (MAXD - i) steady squares.
    // Similarly for eight_arr[i].
    //
    // But we also need to handle leading zeros:
    // A "k-digit steady square" means the number has exactly k digits in base 14.
    // The truncation of 'seven' to k digits might have seven[k-1] = 0, making it
    // less than k digits. In that case, it's NOT a k-digit steady square.
    //
    // Similarly, we need to subtract digit contributions when a truncation has leading zero.

    // For the "1" steady square: it's 1-digit. Its digit sum contribution is 1.

    long long digit_sum = 1;  // for the number 1 (1-digit steady square)

    // For seven chain: for each k from 1 to MAXD, if seven[k-1] != 0,
    // we have a k-digit steady square whose digits are seven[0..k-1].
    // Digit sum = sum of seven[0..k-1].
    //
    // Efficient approach: maintain running digit sum.
    // sum_of_digits(k) = sum_of_digits(k-1) + seven[k-1]
    // If seven[k-1] != 0, add sum_of_digits(k) to total.
    // If seven[k-1] == 0, this truncation is not a k-digit number. Skip.
    //
    // Actually, even with leading zero at position k-1, the number could still have
    // fewer digits but might still be valid for a smaller k. But we already counted it
    // at the smaller k. So we just skip.
    //
    // Wait, actually: the solutions to x^2 ≡ x mod 14^k include x = seven_k.
    // If seven_k < 14^(k-1), then seven_k has fewer than k digits and is also
    // a solution to x^2 ≡ x mod 14^(k-1). But it was already counted for k-1 digits.
    // As a k-digit steady square, it doesn't qualify. So we skip when seven[k-1] = 0.

    long long running_sum_s = 0, running_sum_e = 0;
    for (int k = 1; k <= MAXD; k++) {
        running_sum_s += seven[k-1];
        running_sum_e += eight_arr[k-1];

        if (seven[k-1] != 0) {
            digit_sum += running_sum_s;
        }
        if (eight_arr[k-1] != 0) {
            digit_sum += running_sum_e;
        }
    }

    // Convert digit_sum to base 14
    string result;
    const char digits[] = "0123456789abcd";
    long long tmp_val = digit_sum;
    if (tmp_val == 0) result = "0";
    while (tmp_val > 0) {
        result = digits[tmp_val % 14] + result;
        tmp_val /= 14;
    }
    cout << result << endl;

    return 0;
}

Python project_euler/problem_284/solution.py

"""
Project Euler Problem 284: Steady Squares

A steady square in base 14 is a number n whose square ends with the same digits
as n (i.e., n^2 ≡ n mod 14^k where k = number of digits of n in base 14).

Find the sum of the digits of all n-digit steady squares in base 14 for 1 <= n <= 10000,
and give the answer in base 14.

Approach:
- Solutions to x^2 ≡ x mod 14^k are: 0, 1, s_k, e_k
  where s_k extends from 7 and e_k extends from 8.
- Use fast doubling: n' = (3n^2 - 2n^3) mod 14^(2k) to double digit count.
- e_k = (14^k + 1 - s_k) mod 14^k.
- Sum digits of all valid k-digit steady squares for k=1..10000.
"""

MAXD = 10000
BASE = 14

def mul_low(a, b, keep):
    """Multiply a * b in base 14, keep only first 'keep' digits."""
    res = [0] * keep
    na, nb = len(a), len(b)
    for i in range(min(na, keep)):
        if a[i] == 0:
            continue
        carry = 0
        jmax = min(nb, keep - i)
        for j in range(jmax):
            carry += res[i + j] + a[i] * b[j]
            res[i + j] = carry % BASE
            carry //= BASE
        j2 = jmax
        while i + j2 < keep and carry > 0:
            carry += res[i + j2]
            res[i + j2] = carry % BASE
            carry //= BASE
            j2 += 1
    return res

def mul_scalar(a, s, keep):
    """Multiply a by scalar s, keep first 'keep' digits."""
    res = [0] * keep
    carry = 0
    for i in range(keep):
        if i < len(a):
            carry += a[i] * s
        res[i] = carry % BASE
        carry //= BASE
    return res

def sub_mod(a, b, keep):
    """(a - b) mod 14^keep."""
    res = [0] * keep
    borrow = 0
    for i in range(keep):
        diff = a[i] - b[i] - borrow
        if diff < 0:
            diff += BASE
            borrow = 1
        else:
            borrow = 0
        res[i] = diff
    return res

# Build 'seven': the automorphic number starting with 7
seven = [0] * MAXD
seven[0] = 7
cur = 1

while cur < MAXD:
    target = min(cur * 2, MAXD)
    n2 = mul_low(seven[:cur], seven[:cur], target)
    n3 = mul_low(n2, seven[:cur], target)
    t1 = mul_scalar(n2, 3, target)
    t2 = mul_scalar(n3, 2, target)
    seven_new = sub_mod(t1, t2, target)
    seven[:target] = seven_new
    cur = target

# Build 'eight': (1 - seven) mod 14^MAXD
eight = [0] * MAXD
borrow = 0
for i in range(MAXD):
    val = (1 if i == 0 else 0) - seven[i] - borrow
    if val < 0:
        val += BASE
        borrow = 1
    else:
        borrow = 0
    eight[i] = val

assert seven[0] == 7
assert eight[0] == 8

# Sum digits of all valid k-digit steady squares for k=1..MAXD
digit_sum = 1  # for the number "1" (1-digit steady square)
running_s = 0
running_e = 0

for k in range(1, MAXD + 1):
    running_s += seven[k - 1]
    running_e += eight[k - 1]
    if seven[k - 1] != 0:
        digit_sum += running_s
    if eight[k - 1] != 0:
        digit_sum += running_e

# Convert to base 14
digits_b14 = "0123456789abcd"
result = ""
tmp = digit_sum
if tmp == 0:
    result = "0"
while tmp > 0:
    result = digits_b14[tmp % 14] + result
    tmp //= 14

print(result)