Detailed mathematical approach

Problem Summary

A positive integer is balanced when the sum of its first half digits equals the sum of its last half digits. For odd length, the two halves overlap at the center, so a number with digits \(a_1a_2\cdots a_hma_{h+2}\cdots a_{2h+1}\) is balanced when \(a_1+\cdots+a_h+m=m+a_{h+2}+\cdots+a_{2h+1}\). The middle digit appears on both sides and cancels.

Let \(T(n)\) be the sum of all balanced positive integers below \(10^n\). The original problem asks for \(T(47)\bmod 3^{15}\), but the derivation used by the implementations works for general \(n\) and general modulus \(M\). Brute force is hopeless at this scale, so the solution groups numbers by length and digit sum instead of examining them one by one.

Mathematical Approach

Write \(\sigma(X)\) for the sum of the digits of a block \(X\). For each exact length \(L\), let \(U_L\) denote the sum of all balanced \(L\)-digit numbers. Then

$T(n)=\sum_{L=1}^{n}U_L.$

The whole problem is therefore to compute \(U_L\) efficiently for every length.

Split the number into outer blocks

If \(L=2h\) is even, every \(L\)-digit number can be written as

$x=A\cdot 10^h+B,$

where \(A\) is an \(h\)-digit block whose first digit is nonzero, and \(B\) is an \(h\)-digit block in which leading zeros are allowed. The number is balanced exactly when \(\sigma(A)=\sigma(B)\).

If \(L=2h+1\) is odd, every number has the form

$x=A\cdot 10^{h+1}+m\cdot 10^h+B,\qquad m\in\{0,1,\dots,9\}.$

Now the balance condition is

$\sigma(A)+m=m+\sigma(B),$

so once again the real condition is just \(\sigma(A)=\sigma(B)\). The center digit is free.

Two DP tables: count blocks and add their values

For every block length \(\ell\) and digit sum \(s\), the implementations keep two aggregated quantities:

$C_L(\ell,s),\ V_L(\ell,s),\qquad C_R(\ell,s),\ V_R(\ell,s).$

\(C_L(\ell,s)\) counts left blocks of length \(\ell\) with digit sum \(s\), and \(V_L(\ell,s)\) is the sum of their numeric values. The corresponding right-table quantities allow leading zeros, because numbers such as \(1203\) really do have a right block equal to \(03\). The base state is the empty block: length \(0\), digit sum \(0\), count \(1\), total value \(0\).

Appending one digit gives the recurrence

Suppose a state already contains all blocks of length \(\ell\) and digit sum \(s\). Appending a digit \(d\) on the right creates blocks of length \(\ell+1\) and digit sum \(s+d\), so the count update is

$C(\ell+1,s+d)\leftarrow C(\ell+1,s+d)+C(\ell,s).$

If a previous block has value \(x\), the new block has value \(10x+d\). Summing that identity over the whole state gives

$V(\ell+1,s+d)\leftarrow V(\ell+1,s+d)+10\,V(\ell,s)+d\,C(\ell,s).$

For left blocks, the very first appended digit must lie in \(\{1,\dots,9\}\); afterwards digits \(0\) through \(9\) are all allowed. For right blocks, digits \(0\) through \(9\) are allowed from the beginning. This recurrence is the core of the solution, because it tracks not only how many compatible blocks exist but also the sum of all their decimal values.

Even lengths: pair equal digit sums

Fix \(L=2h\) and a digit sum \(s\). Every balanced number with that outer sum is formed by choosing a left block \(A\) from the left table and a right block \(B\) from the right table, both with digit sum \(s\). Summing

$A\cdot 10^h+B$

over all such pairs yields

$U_{2h}(s)=10^h\,V_L(h,s)\,C_R(h,s)+V_R(h,s)\,C_L(h,s).$

Therefore

$U_{2h}=\sum_{s=0}^{9h}\left(10^h\,V_L(h,s)\,C_R(h,s)+V_R(h,s)\,C_L(h,s)\right).$

Odd lengths: the middle digit contributes independently

For \(L=2h+1\), the outer blocks are still matched only by digit sum. Once \(A\) and \(B\) satisfy \(\sigma(A)=\sigma(B)\), every middle digit \(m\) from \(0\) to \(9\) produces a balanced number. Summing

$A\cdot 10^{h+1}+m\cdot 10^h+B$

over all \(A\), \(B\), and \(m\) gives

$U_{2h+1}=\sum_{s=0}^{9h}\left(10^{h+1}V_L(h,s)\cdot 10\,C_R(h,s)+45\cdot 10^h\,C_L(h,s)C_R(h,s)+10\,V_R(h,s)C_L(h,s)\right).$

The factor \(10\) comes from the ten middle-digit choices, and the factor \(45\) is \(0+1+\cdots+9\). No modular division is needed anywhere, which is important because the target modulus \(3^{15}\) is not prime.

Worked example: the family \(52m25\)

Take \(h=2\), left block \(A=52\), and right block \(B=25\). Both blocks have digit sum \(7\), so every number of the form \(52m25\) is balanced. The ten members of the family are \(52025,52125,\dots,52925\).

Their total is

$10\cdot 52\cdot 10^3+45\cdot 10^2+10\cdot 25=524750.$

This tiny example is exactly the odd-length formula in miniature: one term for the repeated left block, one for the changing middle digit, and one for the repeated right block.

How the Code Works

Precomputation

The C++, Python, and Java implementations first build the four DP tables up to half-length \(\lceil n/2\rceil\). At the same time they precompute the powers \(10^k\bmod M\), because each block sum must later be shifted into its proper decimal position.

Length-by-length accumulation

After precomputation, the implementation loops through the exact lengths \(1,2,\dots,n\). For each length it sets \(h=\lfloor L/2\rfloor\), reads the row for that half-length from the left and right tables, and accumulates the matching digit-sum contributions. Even lengths use the two-term formula for \(A\cdot 10^h+B\); odd lengths use the three-term formula that also contains the middle-digit contribution \(45\cdot 10^h\).

Why the modular arithmetic is simple

Every recurrence and every final contribution uses only addition and multiplication, so intermediate values can be reduced modulo \(M\) immediately without changing the final residue. One implementation also checks small cases such as \(T(1)=45\), \(T(2)=540\), and a brute-force comparison for a small input size before running the full computation.

Complexity Analysis

Let \(m=\lceil n/2\rceil\). The largest possible digit sum is \(9m\). Building one DP table visits states \((\ell,s)\) with \(0\le \ell\le m\) and \(0\le s\le 9\ell\), and from each state it tries at most 10 next digits. Hence the preprocessing cost is \(O(m\cdot 9m\cdot 10)=O(n^2)\).

The final sweep over all lengths and feasible digit sums is also \(O(n^2)\). Memory usage is \(O(n^2)\) for the count and value-sum tables. For the actual target \(n=47\), the maximum half-length is only \(24\) and the largest digit sum is \(216\), so the DP is tiny compared with the original search space below \(10^{47}\).

Footnotes and References

1. Project Euler problem page: Problem 217
2. Digit sum: Wikipedia - Digit sum
3. Dynamic programming: Wikipedia - Dynamic programming
4. Positional notation: Wikipedia - Positional notation
5. Modular arithmetic: Wikipedia - Modular arithmetic