Detailed mathematical approach

Problem Summary

We seek square numbers \(n\) below \(10^{16}\) whose decimal expansion can be split into a nonempty left part and a nonempty right part so that the square root is the sum of those two parts. Writing \(n=s^2\), the split has the form

$n=a10^d+b,\qquad s=a+b,$

where \(b\) has exactly \(d\) digits. The title example is \(2025=20\mid 25\), because \(20+25=45=\sqrt{2025}\). The task is to add all such squares, not all successful splits, so duplicates must be counted only once.

This is closely related to base-10 Kaprekar numbers, but the efficient way to solve the Project Euler problem is to search over the root \(s\) and describe the allowed values of \(s\) by modular arithmetic.

Mathematical Approach

Fix a split length \(d\) and write

$M_d=10^d-1.$

For that fixed \(d\), the whole problem is to characterize the roots \(s\) for which the split exists.

Eliminating the two decimal pieces

From \(n=s^2=a10^d+b\) and \(s=a+b\), substitute \(b=s-a\):

$s^2=a10^d+(s-a)=s+a(10^d-1).$

Therefore

$a=\frac{s(s-1)}{M_d},\qquad b=s-a.$

This already gives the key divisibility condition

$M_d\mid s(s-1).$

Once \(a\) is an integer and the digit conditions hold, the reconstruction is automatic, because

$a10^d+b=a(10^d-1)+s=s(s-1)+s=s^2.$

So the search is not really over \((a,b)\); it is over roots \(s\) satisfying one congruence and a few digit inequalities.

Why every prime power allows only residue \(0\) or \(1\)

Factor \(M_d\) into pairwise coprime prime powers:

$M_d=\prod_{i=1}^{t} p_i^{e_i}.$

Consecutive integers are coprime, so \(\gcd(s,s-1)=1\). If \(p_i^{e_i}\) divides the product \(s(s-1)\), then the full prime power must divide exactly one of the two consecutive factors. Hence every valid root satisfies

$s\equiv 0,1 \pmod{p_i^{e_i}},\qquad 1\le i\le t.$

That is the crucial structural simplification. Instead of examining all roots below \(10^8\), we only have to choose, for every distinct prime-power factor of \(10^d-1\), whether \(s\) is congruent to \(0\) or to \(1\).

Combining the local choices with the Chinese remainder theorem

Each prime power contributes two local options, so a fixed \(d\) leads to a collection of global residue classes. The Chinese remainder theorem merges those local choices into unique congruences

$s\equiv r \pmod{M_d}.$

Every admissible root for that split length lies in one arithmetic progression

$s=r+kM_d,\qquad k\ge 0.$

The implementations therefore build all CRT residue classes first and only then test the corresponding candidate roots.

The digit bounds that finish the reduction

The modular condition is necessary, but not sufficient. We still need the split to be a genuine decimal split with both parts nonzero and with no leading zeros in the right block.

Because \(b=s-a\gt 0\), we need \(a\lt s\). Using the formula for \(a\),

$\frac{s(s-1)}{M_d}\lt s,$

which simplifies to

$s\lt 10^d.$

So every valid root must satisfy

$2\le s\le \min\!\bigl(\lfloor\sqrt{10^{16}-1}\rfloor,\;10^d-1\bigr).$

There is also an exact range for the right part:

$1\le b\lt 10 \quad(d=1),\qquad 10^{d-1}\le b\lt 10^d \quad(d\ge 2).$

The second condition is what rules out right parts such as \(01\) or \(0017\): they are numerically positive, but they do not occupy exactly \(d\) digits.

Worked example: the title number \(2025\)

Take \(d=2\). Then

$M_2=10^2-1=99=9\cdot 11.$

For the prime powers \(9\) and \(11\), the only local residues are \(0\) and \(1\). CRT therefore produces four global residue classes modulo \(99\):

$s\equiv 0,\ 1,\ 45,\ 55 \pmod{99}.$

Since \(s\lt 100\), only the representatives \(45\), \(55\), and \(99\) can matter.

For \(s=45\),

$a=\frac{45\cdot 44}{99}=20,\qquad b=45-20=25,$

so \(45^2=2025=20\mid 25\).

For \(s=55\),

$a=\frac{55\cdot 54}{99}=30,\qquad b=55-30=25,$

so \(55^2=3025=30\mid 25\).

For \(s=99\),

$a=\frac{99\cdot 98}{99}=98,\qquad b=1,$

but \(b=1\) is not a two-digit number, so the split \(98\mid 01\) is invalid. This example shows exactly why the algorithm needs both pieces: CRT generates the modular candidates, and the digit checks remove the false positives.

Why the final sum must be de-duplicated

The Project Euler question asks for the sum of the numbers \(n\), not the sum over all successful pairs \((n,d)\). A square can satisfy the defining property for more than one split length, so the accepted values \(n=s^2\) must be stored as distinct integers before the final addition is performed.

How the Code Works

Precomputation

The C++, Python, and Java implementations precompute powers of \(10\), the root bound \(\lfloor\sqrt{10^{16}-1}\rfloor\), and a prime table large enough to factor every repunit-like modulus \(10^d-1\) with \(1\le d\le 15\).

Per-split residue construction

For each split length \(d\), the implementation factors \(10^d-1\) into prime powers. It starts from the trivial congruence modulo \(1\) and repeatedly merges the two local possibilities \(s\equiv0\) and \(s\equiv1\) modulo each prime power. After all merges, the result is the complete CRT list of admissible residues \(r\) modulo \(10^d-1\).

Candidate testing and unique accumulation

Each residue class produces a candidate root \(s\) in the allowed range. From that root, the implementation computes \(a=\frac{s(s-1)}{10^d-1}\), then \(b=s-a\), checks positivity, checks the exact digit range of \(b\), reconstructs \(n=s^2\), and inserts \(n\) into a hash set. The C++ implementation also includes small direct-search self-checks for shorter digit limits before producing the final \(10^{16}\) answer.

Complexity Analysis

Let \(\omega(M_d)\) be the number of distinct prime divisors of \(M_d=10^d-1\). For a fixed \(d\), the CRT stage creates exactly \(2^{\omega(M_d)}\) residue classes, because each prime power contributes the binary choice \(0\) or \(1\).

For this particular problem size, the bound \(s\lt 10^d\) means that each residue class contributes at most one relevant root candidate. As a result, after factorization the remaining work is essentially one constant-time arithmetic check per CRT residue. Memory usage is small: a prime list, a temporary residue list, and the set of accepted squares. This is far smaller than a naive search over all roots up to \(10^8\) and all possible split positions.

Footnotes and References

1. Problem page: Project Euler 932
2. Chinese remainder theorem: Wikipedia - Chinese remainder theorem
3. Kaprekar number: Wikipedia - Kaprekar number
4. Modular arithmetic: Wikipedia - Modular arithmetic
5. Repunit: Wikipedia - Repunit