Solution

Answer: 6273134

Let

$$t(n)=2n^2-1$$

Oops — wrong problem context.

We instead need the Project Euler 217 quantity:

$$T(n)=\sum_{\substack{0\le x<10^n\ x\text{ balanced}}} x$$

where a number is balanced if the sum of its first $\lceil k/2\rceil$ digits equals the sum of its last $\lceil k/2\rceil$ digits.

We seek

$$T(47)\bmod 3^{15}.$$

1. Mathematical analysis

1.1 Understanding the balance condition

Suppose a number has $k$ digits.

Even length: $k=2m$

Write the number as

$$N = L\cdot 10^m + R$$

where:

$L$ is the first $m$ digits,
$R$ is the last $m$ digits.

The balance condition is:

$$\text{digitSum}(L)=\text{digitSum}(R).$$

Odd length: $k=2m+1$

Write the number as

$$N = L\cdot 10^{m+1} + c\cdot 10^m + R$$

where $c$ is the middle digit.

The definition compares the first $m+1$ digits and the last $m+1$ digits:

$$\text{digitSum}(L)+c = c+\text{digitSum}(R).$$

The middle digit cancels, so again:

$$\text{digitSum}(L)=\text{digitSum}(R).$$

Thus both even and odd lengths reduce to the same core condition.

1.2 DP for digit sums

Define:

$$A(m,s)=#{\text{length-}m\text{ digit strings with digit sum }s}$$

allowing leading zeros.

Also define:

$$B(m,s)=\sum (\text{all such }m\text{-digit numbers}).$$

These satisfy the transitions:

$$A(m+1,s+d) += A(m,s)$$

and

$$B(m+1,s+d) += 10B(m,s)+dA(m,s).$$

Why?

Appending digit $d$ transforms every old number $x$ into

$$10x+d.$$

Summing over all such $x$:

$$\sum (10x+d) = 10\sum x + d\cdot(#\text{numbers}).$$

1.3 Even-length contribution

For $2m$-digit balanced numbers:

left half $L$ must have no leading zero,
right half $R$ may have leading zeros,
both must have equal digit sum $s$.

Let:

$C_L(s)$ = count of valid left halves,
$S_L(s)$ = sum of valid left halves.

Then the total contribution is

$$\sum_s \left( S_L(s)\cdot 10^m \cdot A(m,s) + C_L(s)\cdot B(m,s) \right).$$

The first term accounts for left halves placed in the high digits; the second accounts for right halves.

1.4 Odd-length contribution

For $2m+1$-digit balanced numbers:

$$N=L\cdot10^{m+1}+c\cdot10^m+R.$$

For fixed $(L,R)$, summing over $c=0,\dots,9$:

$$\sum_c N = 10(L\cdot10^{m+1}+R) + 45\cdot10^m.$$

Therefore:

$$\sum_s \left[ 10\left( S_L(s)\cdot10^{m+1}\cdot A(m,s) + C_L(s)\cdot B(m,s) \right) + 45\cdot10^m\cdot C_L(s)\cdot A(m,s) \right].$$

2. Python implementation

MOD = 3**15
N = 47

# Maximum half-length needed:
# floor(47/2) = 23, but we use 24 safely.
MAXM = 24
MAXS = 9 * MAXM

# A[m][s] = count of m-digit strings with digit sum s
# B[m][s] = sum of all such m-digit numbers
A = [[0] * (MAXS + 1) for _ in range(MAXM + 1)]
B = [[0] * (MAXS + 1) for _ in range(MAXM + 1)]

A[0][0] = 1

# Precompute powers of 10
pow10 = [1]
for _ in range(60):
    pow10.append(pow10[-1] * 10)

# Build DP tables
for m in range(MAXM):
    for s in range(9 * m + 1):

        count = A[m][s]
        total = B[m][s]

        if count == 0 and total == 0:
            continue

        for d in range(10):

            A[m + 1][s + d] += count

            # Appending digit d:
            # new_number = old_number * 10 + d
            B[m + 1][s + d] += total * 10 + count * d

def left_tables(m, s):
    """
    Count/sum of m-digit numbers with no leading zero
    and digit sum s.
    """

    count = 0
    total = 0

    for first in range(1, 10):

        if s - first < 0 or s - first > 9 * (m - 1):
            continue

        cnt = A[m - 1][s - first]

        # Numbers formed as:
        # first * 10^(m-1) + tail
        sm = B[m - 1][s - first] + cnt * first * pow10[m - 1]

        count += cnt
        total += sm

    return count, total

def balanced_sum_length(length):

    # One-digit case
    if length == 1:
        return 45

    # -------------------------------------------------
    # EVEN LENGTH = 2m
    # -------------------------------------------------
    if length % 2 == 0:

        m = length // 2
        ans = 0

        for s in range(9 * m + 1):

            left_count, left_sum = left_tables(m, s)

            ans += (
                left_sum * pow10[m] * A[m][s]
                + left_count * B[m][s]
            )

        return ans

    # -------------------------------------------------
    # ODD LENGTH = 2m+1
    # -------------------------------------------------
    else:

        m = length // 2
        ans = 0

        for s in range(9 * m + 1):

            left_count, left_sum = left_tables(m, s)

            pair_count = left_count * A[m][s]

            ans += (
                10 * (
                    left_sum * pow10[m + 1] * A[m][s]
                    + left_count * B[m][s]
                )
                + 45 * pow10[m] * pair_count
            )

        return ans

# Compute T(47)
answer = sum(
    balanced_sum_length(k)
    for k in range(1, N + 1)
) % MOD

print(answer)

3. Code walkthrough

DP construction

We build all digit strings by appending digits $0\ldots9$.

A[m][s]

stores how many strings of length m have digit sum s.

B[m][s]

stores the sum of all such strings interpreted as integers.

`left_tables(m, s)`

This computes:

count of valid left halves,
sum of valid left halves,

with the restriction that the first digit is nonzero.

We explicitly choose the leading digit $1\ldots9$.

`balanced_sum_length(length)`

Handles separately:

even lengths,
odd lengths.

Using the formulas derived above.

4. Verification on small cases

The program reproduces the values from the statement:

$$T(1)=45$$

$$T(2)=540$$

$$T(5)=334795890$$

which confirms the derivation.

5. Final verification

We finally compute:

$$T(47)\bmod 3^{15}$$

with

$$3^{15}=14348907.$$

The computed residue is:

$$6273134.$$

Answer: 6273134

Project Euler Problem 217