Problem 719: Number Splitting

Mathematical Foundation

Definition. For a string of digits $d_1 d_2 \cdots d_m$ and a target $s$, define $\operatorname{CanSplit}(i, r)$ to be true if the substring $d_i d_{i+1} \cdots d_m$ can be partitioned into one or more groups whose numerical values sum to $r$.

Lemma 1 (Modular Filter). If $n = k^2$ is an S-number, then $k \equiv 0 \pmod{9}$ or $k \equiv 1 \pmod{9}$.

Proof. The digit sum of any integer is congruent to that integer modulo 9. When we split $n$ into parts and sum them, the result is congruent to $n$ modulo 9 (since concatenation followed by digit-sum-preserving splitting preserves the total digit sum). Therefore $k \equiv k^2 \pmod{9}$, which gives $k(k-1) \equiv 0 \pmod{9}$. Since $\gcd(k, k-1) = 1$, either $9 \mid k$ or $9 \mid (k-1)$. $\square$

Theorem 1 (Recursive Characterization). The number $n = k^2$ with decimal digits $d_1 \cdots d_m$ is an S-number if and only if $\operatorname{CanSplit}(1, k)$ returns true, where

with $v_{i \ldots j}$ denoting the numerical value of digits $d_i d_{i+1} \cdots d_j$, and the requirement that at least 2 parts are used (i.e., we cannot take the entire string as one part unless it is part of a larger partition).

Proof. The recursion enumerates all possible first segments $d_i \cdots d_j$ of the remaining string, subtracts the value from the target, and recurses on the rest. The base case $j = m$ with $v = r$ means the last segment exactly accounts for the remaining target. The disjunction over all valid $j$ ensures all possible splittings are considered. Correctness follows by structural induction on the length of the remaining string. $\square$

Lemma 2 (Pruning). The recursion can be pruned by:

1. Value bound: If $v_{i \ldots j} > r$, skip (the partial sum already exceeds the target).
2. Modular filter: Pre-filter candidates by Lemma 1, eliminating $\approx 77.8\%$ of all $k$.
3. Early termination: If $r < 0$, return false immediately.

Proof. (1) If any segment exceeds the remaining target, no valid completion exists since all segment values are non-negative. (2) The modular filter is proven in Lemma 1. (3) Non-negativity of digit values ensures the target can only decrease. $\square$

Editorial

We enumerate the admissible parameter range, discard candidates that violate the derived bounds or arithmetic constraints, and update the final set or total whenever a candidate passes the acceptance test.

Pseudocode

    limit = floor(sqrt(N))
    total = 0
    For k from 4 to limit:
        If k mod 9 != 0 and k mod 9 != 1 then
            continue
        n = k * k
        digits = decimal_digits(n)
        If can_split(digits, 0, k, 0) then
            total += n
    Return total

    If pos == len(digits) then
        Return remaining == 0 and num_parts >= 2
    For end from pos + 1 to len(digits):
        segment_value = to_integer(digits[pos..end])
        If segment_value > remaining then
            break
        If can_split(digits, end, remaining - segment_value, num_parts + 1) then
            Return true
    Return false

Complexity Analysis

• Time: The outer loop runs over $\lfloor \sqrt{N} \rfloor = 10^6$ values of $k$, reduced to approximately $2.2 \times 10^5$ by the mod-9 filter. For each candidate, the recursive splitting has worst-case $O(2^m)$ where $m$ is the number of digits of $k^2$ (at most 13 for $k \leq 10^6$). With pruning, the average case is much faster. Total practical runtime: a few seconds.
• Space: $O(m)$ for the recursion stack, where $m \leq 13$.

Answer

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

// Check if the string s[pos..end] can be split into parts summing to target
bool canSplit(const string& s, int pos, long long target, bool hasSplit) {
    if (pos == (int)s.size()) {
        return target == 0 && hasSplit;
    }
    if (target < 0) return false;

    long long val = 0;
    for (int i = pos; i < (int)s.size(); i++) {
        val = val * 10 + (s[i] - '0');
        if (val > target) break;
        // Don't use the entire string as one part (need at least 2 parts)
        if (i == (int)s.size() - 1 && !hasSplit) continue;
        if (canSplit(s, i + 1, target - val, true)) return true;
    }
    return false;
}

int main() {
    long long N = 1000000; // sqrt(10^12)
    long long total = 0;

    for (long long k = 2; k <= N; k++) {
        // Mod 9 pruning: k(k-1) must be divisible by 9
        int r = k % 9;
        if (r != 0 && r != 1) continue;

        long long n = k * k;
        string s = to_string(n);

        if (canSplit(s, 0, k, false)) {
            total += n;
        }
    }

    cout << total << endl;
    return 0;
}

def can_split(s, pos, target, has_split):
    """Check if s[pos:] can be split into parts summing to target."""
    if pos == len(s):
        return target == 0 and has_split
    if target < 0:
        return False

    val = 0
    for i in range(pos, len(s)):
        val = val * 10 + int(s[i])
        if val > target:
            break
        # Need at least 2 parts total
        if i == len(s) - 1 and not has_split:
            continue
        if can_split(s, i + 1, target - val, True):
            return True
    return False

def T(N):
    limit = int(N ** 0.5)
    total = 0
    for k in range(2, limit + 1):
        # Mod 9 pruning
        r = k % 9
        if r != 0 and r != 1:
            continue
        n = k * k
        s = str(n)
        if can_split(s, 0, k, False):
            total += n
    return total

# Verify with small case
assert T(10**4) == 41333, f"T(10^4) = {T(10**4)}, expected 41333"
print(f"T(10^4) = {T(10**4)}")

# Compute the answer
result = T(10**12)
print(f"T(10^12) = {result}")