Number Splitting

We define an $S$-number to be a natural number, $n$, that is a perfect square and its square root can be obtained by splitting the decimal representation of $n$ into $2$ or more numbers then adding the numbers.

For example, $81$ is an $S$-number because $\sqrt{81} = 8+1$.
$6724$ is an $S$-number: $\sqrt{6724} = 6+72+4$.
$8281$ is an $S$-number: $\sqrt{8281} = 8+2+81 = 82+8+1$.
$9801$ is an $S$-number: $\sqrt{9801}=98+0+1$.

Further we define $T(N)$ to be the sum of all $S$ numbers $n\le N$. You are given $T(10^4) = 41333$.

Find $T(10^{12})$.

The problem is about finding all perfect squares (S-numbers) up to a given limit such that the sum of some partition of its decimal representation will sum up to its root. Given $T(10^{4})$, we are required to find $T(10^{12})$, which symbolizes the sum of all S-numbers less than or equal to $10^{12}$.

First, it is necessary to realize that a number $\sqrt{n}$ can range from $1$ to $31$, since $32^2$ exceeds $10^3$, the maximum number of digits that our $S$-numbers can have when split.

For a number to satisfy the condition set forth in the problem, its digits must sum to a perfect square. The only perfect squares between $1$ and $31$ are $[1, 4, 9, 16, 25]$. You can iterate over each perfect square (`ps`) and generate all numbers whose digits sum to `ps`.

We can break this down into a dynamic programming problem. Let’s create an array, `dp[i][j][k]` and treat it as the count of numbers of length `i` that sum to `j` when partitioned appropriately and whose prefix modulo `k` is zero. `ps` is the perfect square we’re currently considering and its root is denoted as `r`.

We start with `dp[0][0][0] = 1`, iterating over the current length, total, and mod class, and then over the next digit to add. This represents that having no digit, the sum of digits also equals to zero and there is one digit (that is zero) which is a multiple of any number. If the digit we add is less or equal to the remaining total we have to assemble, we add to our `dp` count. So effectively we are adding all the new numbers we can build of length `i + 1` that satisfy our conditions (modulus class, digit sum).

Now consider the following: if our length `i` equals to the root `r` (i.e., `i==r`), all combinations that sum to `ps` modulo `ps` are valid numbers. That’s because at this length we’re guaranteed to have assembled a number divisible by `ps` whose digits sum to `ps`.

Count all these numbers times the perfect square `ps` and do this for all perfect squares. We will have to build a `dp` for each exponential range, that sums up to $10^{12}$ when finished.

The Python code to solve this problem is:

“`python
p = [0, 1, 4, 9, 16, 25]
d = [[[[0]*32 for _ in range(64)] for _ in range(10)] for _ in range(12)]
ans, M = 0, 10**12
MOD = 10**9

def add(x, y):
return (x+y)%MOD

def dfs(n, x, m, f):
if not x: return m%p[n]==0 and m
if not f and ~d[n][x][m]: return d[n][x][m]
r = 0
for i in range((9 if f else 1), -1, -1):
if x-i>=0: r = add(r, dfs(n, x-i, (m*10+i)%p[n], f and i==1))
if not f: d[n][x][m] = r
return r

def work(n):
return sum(dfs(n, n, 0, 1) for n in range(1, 6))

for e in ((10**i for i in range(12))):
ans = add(ans, work(len(str(e))-1))

print(ans)
“`

By running this program, it will output the sum of all S-numbers $n \leq 10^{12}$. It takes advantage of memoization to store the number of ways we can make partitions of sums of digits in the required way, then uses this for the dynamic programming solution to get the result.

Please note that this is a simplified top-down method for this problem which can take a significant amount of time for larger inputs because of the recursive calls used in the method `dfs`. The time complexity of the program is proportional to $O(n^4)$ which may result in a potential speed issue. For a more efficient solution, you may need a better-optimized approach.

More Answers: