Detailed mathematical approach

Problem Summary

A positive integer \(n\) is called an S-number if \(n\) is a perfect square and the decimal digits of \(n\) can be cut into at least two contiguous blocks whose integer values add up to \(\sqrt{n}\). The problem asks for

$T(L)=\sum_{\substack{n\le L\\ n\text{ is an S-number}}} n.$

Since every contributing term is a square, it is more convenient to search over roots \(r\) and test whether the decimal expansion of \(r^2\) admits such a partition.

If \(\mathcal{S}\) denotes the set of valid roots, then equivalently

$T(L)=\sum_{\substack{1\le r\le \lfloor\sqrt{L}\rfloor\\ r\in\mathcal{S}}} r^2.$

Mathematical Approach

The implementation combines a necessary congruence filter with a depth-first search over decimal cut positions. The search is made efficient by strong lower and upper bounds for every unfinished suffix.

Step 1: Rewrite the Condition in Terms of the Root

Let \(r\) be a candidate root and let \(n=r^2\). Write the decimal expansion of \(n\) and split it into contiguous blocks with values \(b_1,b_2,\dots,b_k\), where \(k\ge2\). Then \(r\) is valid exactly when

$b_1+b_2+\cdots+b_k=r.$

No operators are inserted and no digits are rearranged; only cut positions are chosen. If \(n\) has \(d\) digits, then each gap between adjacent digits is either cut or not cut, so the raw search space contains \(2^{d-1}-1\) nontrivial partitions.

Step 2: Use the Necessary Modulo 9 Condition

Any successful split must satisfy a strong congruence. Every power of ten obeys \(10^m\equiv1\pmod 9\), so cutting a decimal string into blocks does not change its value modulo \(9\). Therefore the sum of the blocks is congruent to the original square:

$r\equiv r^2\pmod 9.$

This simplifies to

$r(r-1)\equiv0\pmod 9,$

which forces

$r\bmod 9\in\{0,1\}.$

This test is only necessary, not sufficient, but it removes \(7/9\) of all roots before the search starts.

Step 3: Bound Every Unfinished Suffix

Suppose some initial blocks have already been chosen and their sum is \(s\). Choose one more block, so the new partial sum becomes \(s'\). Let the remaining suffix be \(R\). Define \(D(R)\) as the sum of the digits of \(R\), and \(V(R)\) as the integer represented by the whole suffix.

Any continuation of the partition must then finish inside the interval

$[\,s'+D(R),\,s'+V(R)\,].$

The lower bound comes from cutting between every remaining digit. The upper bound comes from making no further cut and taking the entire suffix as one block. Therefore a branch can be discarded immediately whenever

$s'+D(R)\gt r$

or

$s'+V(R)\lt r.$

Step 4: Recurse on Cut Positions and Enforce at Least Two Parts

After a candidate block is chosen, the same reasoning is applied to the rest of the digits. If the running sum already exceeds \(r\), the branch stops because all block values are nonnegative. When the end of the digit string is reached, the split succeeds exactly if the accumulated sum equals \(r\).

The one-block partition \(r^2\) itself must be excluded, because the definition requires at least two parts. The implementations enforce this by ensuring that the first block ends before the last digit, so at least one cut is guaranteed.

Worked Example

Take \(r=45\), so \(n=r^2=2025\). The modular filter passes because \(45\equiv0\pmod 9\).

If the first block is \(2\), the remaining suffix is \(025\). Then

$2+(0+2+5)=9,\qquad 2+25=27.$

So every completion lies between \(9\) and \(27\), which can never reach \(45\). That entire branch is pruned immediately.

If the first block is \(20\), the suffix is \(25\). Now the feasible interval becomes

$[27,45].$

The target lies inside the interval, and choosing the last block as \(25\) gives

$20+25=45.$

Hence \(2025\) is an S-number and contributes \(2025\) to \(T(L)\).

How the Code Works

The C++, Python, and Java implementations all follow the same structure. They iterate candidate roots \(r\) from \(2\) upward, stop once \(r^2\) exceeds the limit, and reject any root whose residue modulo \(9\) is neither \(0\) nor \(1\).

For each surviving root, the square \(r^2\) is converted to a digit sequence. Two suffix tables are prepared: one stores the value of every remaining suffix as a whole number, and the other stores the sum of the digits in that suffix. These tables let the search evaluate the interval test in constant time at every recursive node.

The search then tries each possible next block, updates the partial sum, applies the lower and upper bound checks, and recurses only when the target is still reachable. The first step is restricted so that the entire square cannot be taken as a single block. As soon as one valid partition is found, the square is added to the running total.

Complexity Analysis

Let \(R=\lfloor\sqrt{L}\rfloor\), and let \(d\) be the digit count of the square currently being tested. Without pruning, a single test can inspect up to \(2^{d-1}-1\) nontrivial partitions. The modulo \(9\) filter reduces the number of tested roots to about \(2R/9\), and the suffix bounds cut off many branches well before the leaves of the search tree.

Thus the worst-case time per tested root is still exponential in \(d\), but the practical runtime is much smaller because \(d\) is small and the pruning is strong. Memory usage is \(O(d)\): the digit list, the two suffix tables, and the recursion stack are all linear in the digit count.

Footnotes and References

1. Project Euler Problem 719: https://projecteuler.net/problem=719
2. Backtracking: Wikipedia — Backtracking
3. Depth-first search: Wikipedia — Depth-first search
4. Casting out nines: Wikipedia — Casting out nines
5. Digit sum: Wikipedia — Digit sum