Problem 217: Balanced Numbers

Project Euler Problem 217 Solution

EulerSolve provides an optimized solution for Project Euler Problem 217, Balanced Numbers, with C++, Python, Java, and a step-by-step mathematical explanation.

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)$....

Detailed mathematical approach

Problem Summary

A positive integer with $k$ decimal digits is called balanced if the sum of its first $\lceil k/2\rceil$ digits equals the sum of its last $\lceil k/2\rceil$ digits, where the ceiling $\lceil x\rceil$ is the smallest integer $\ge x$. Every palindrome is balanced, and so is $13722$: its first three digits $1,3,7$ and its last three digits $7,2,2$ both add up to $11$. Let $T(n)$ be the sum of all balanced numbers below $10^n$, that is, of all balanced numbers with at most $n$ digits. The statement gives $T(1)=45$, $T(2)=540$ and $T(5)=334795890$, and asks for $T(47)\bmod 3^{15}$, the remainder of $T(47)$ after division by $3^{15}=14348907$. ^[1]

The whole solution in one sentence: a balanced number is a left half and a right half with equal digit sums, plus a free middle digit when its length is odd, so we tabulate, for every half length and digit sum, how many halves there are and what their values add up to, combine matching halves with a short sum over the digit sum, and do every step modulo $3^{15}$.

Mathematical Approach

We start with short numbers, then cut every number into halves and add up all balanced numbers of one length at once.

1. Short numbers by hand

For $k=1$ the first digit and the last digit are the same digit, so all of $1,\dots,9$ are balanced and $T(1)=45$. For $k=2$ the first digit must equal the last one: $11,22,\dots,99$, whose sum is $11\cdot45=495$, so $T(2)=45+495=540$. For $k=3$ the first two digits are compared with the last two: the number $\overline{abc}$ with digits $a,b,c$ is balanced when $a+b=b+c$, that is, when $a=c$. There are $9\cdot10=90$ such numbers, with $a$ from $1$ to $9$ and $b$ from $0$ to $9$, and their sum is

$$\begin{aligned}&\sum_{a=1}^{9}\sum_{b=0}^{9}(101a+10b)\\&\quad=45450+4050=49500,\end{aligned}$$

so $T(3)=50040$. A palindrome reads the same backwards, ^[2] so its last $\lceil k/2\rceil$ digits are its first $\lceil k/2\rceil$ digits in reverse order, with the same sum. The three-digit balanced numbers are exactly the $90$ three-digit palindromes, but $615$ four-digit numbers are balanced, among them $1322$, and only $90$ of them are palindromes.

2. The middle digit cancels

For an even length $k=2h$ we have $\lceil k/2\rceil=h$, and the two groups of digits are the two halves. For an odd length $k=2h+1$ we have $\lceil k/2\rceil=h+1$, so both groups contain the middle digit; it appears on both sides of the equation and cancels, and the number is balanced exactly when its first $h$ digits and its last $h$ digits have the same sum, whatever the middle digit is. In $13722$ we have $1+3=2+2$, and indeed all of $13022,13122,\dots,13922$ are balanced.

So we cut every number into a left block $A$ of $h$ digits, a middle digit $m$ when $k$ is odd, and a right block $B$ of $h$ digits. The first digit of $A$ is the leading digit of the number, so it is not $0$, while $B$ may start with zeros, as in $1304$, where $A=13$ and $B=04$. Writing $\sigma(X)$ for the digit sum of a block $X$, the sum of its digits, ^[3] the number is balanced exactly when $\sigma(A)=\sigma(B)$. Positional notation ^[4] gives its value, $x=A\cdot10^{h}+B$ for $k=2h$ and

$$x=A\cdot10^{h+1}+m\cdot10^{h}+B$$

for $k=2h+1$. For $k=1$ both blocks are empty and the single digit is the middle digit; Section 5 returns to this case.

3. Counting the halves by digit sum

The numbers below $10^n$ are the positive integers with at most $n$ digits. With $U_k$ the sum of the balanced numbers of exactly $k$ digits,

$$T(n)=\sum_{k=1}^{n}U_k,$$

and Section 1 gives $U_1=45$, $U_2=495$ and $U_3=49500$. To find $U_k$ without listing numbers, let $C_L(h,s)$ be the number of left blocks of $h$ digits with digit sum $s$, the blocks whose first digit is not $0$, and let $S_L(h,s)$ be the sum of their values. Let $C_R(h,s)$ and $S_R(h,s)$ be the same two numbers for right blocks, which are all strings of $h$ digits. For example, the left blocks with $h=2$ and $s=4$ are $13,22,31,40$, and the right blocks are $04,13,22,31,40$, so

$$\begin{aligned}C_L(2,4)&=4,&S_L(2,4)&=106,\\C_R(2,4)&=5,&S_R(2,4)&=110.\end{aligned}$$

For $h=0$ there is one block of each kind, the empty block, with value $0$ and digit sum $0$: $C_L(0,0)=C_R(0,0)=1$ and $S_L(0,0)=S_R(0,0)=0$.

4. Even lengths: adding over all pairs of halves

Claim. For $h\ge1$, with all four tables taken at $(h,s)$,

$$U_{2h}=\sum_{s=0}^{9h}\bigl(10^{h}S_L\,C_R+S_R\,C_L\bigr).$$

Proof. By Section 2 the balanced numbers with $2h$ digits correspond one to one to the pairs $(A,B)$ of a left block and a right block with $\sigma(A)=\sigma(B)$, and the number belonging to a pair is $10^hA+B$. Group the pairs by their common digit sum $s$, which lies between $0$ and $9h$. For a fixed $s$, every one of the $C_L(h,s)$ left blocks is paired with every one of the $C_R(h,s)$ right blocks, so each $A$ occurs $C_R(h,s)$ times and each $B$ occurs $C_L(h,s)$ times:

$$\begin{aligned}&\sum_{A}\sum_{B}\bigl(10^hA+B\bigr)\\&\quad=10^h\,C_R\sum_{A}A+C_L\sum_{B}B.\end{aligned}$$

The two inner sums are $S_L(h,s)$ and $S_R(h,s)$, and adding over $s$ proves the claim.

For the four-digit numbers whose halves both have digit sum $4$, the $4\cdot5=20$ numbers from $1304$ to $4040$, the term is $100\cdot106\cdot5+110\cdot4=53440$, and adding these $20$ numbers directly gives the same. The terms for $s=1,\dots,18$ add up to $U_4=3314850$; the term for $s=0$ is $0$, because no left block has digit sum $0$.

5. Odd lengths: the free middle digit

For $k=2h+1$ a balanced number is a pair $(A,B)$ as before together with any middle digit $m$ from $0$ to $9$, and its value is $10^{h+1}A+10^hm+B$. For a fixed $s$, each $A$ now occurs with $10\,C_R(h,s)$ choices of $m$ and $B$, each $B$ with $10\,C_L(h,s)$ choices of $A$ and $m$, and each of the $C_L(h,s)\,C_R(h,s)$ pairs with the ten middle digits, which add up to $0+1+\dots+9=45$. Hence

$$\begin{aligned}U_{2h+1}=\sum_{s=0}^{9h}\bigl(&10^{h+1}S_L\cdot10\,C_R\\&+45\cdot10^{h}\,C_LC_R\\&+10\,S_RC_L\bigr).\end{aligned}$$

For the five-digit numbers with outer digit sums $4$ the three parts are $5300000$, $90000$ and $4400$, and their total $5394400$ is the sum of these $200$ numbers. Adding over $s$ gives $U_5=331431000$, and with Sections 1 and 4

$$\begin{aligned}T(5)&=45+495+49500\\&\quad+3314850+331431000\\&=334795890,\end{aligned}$$

the value given in the statement. For $k=1$, that is $h=0$, both blocks are empty and the formula gives $45\cdot1\cdot1=45=U_1$: it lets the middle digit, now the leading digit, also be $0$, and so includes the number $0$, which is not positive but adds nothing to the sum.

6. Filling the tables digit by digit

Appending a digit $d$ to a block of value $x$ and digit sum $s$ gives a block of value $10x+d$ and digit sum $s+d$, and every block of length $\ell+1$ arises in exactly one way, from its first $\ell$ digits and its last digit. Adding $10x+d$ over all $C(\ell,s)$ blocks of length $\ell$ and digit sum $s$, whose values add up to $S(\ell,s)$, gives $10\,S(\ell,s)+d\,C(\ell,s)$. So, by induction on $\ell$ starting from the empty block, both kinds of tables obey

$$C(\ell+1,s)=\sum_{d}C(\ell,s-d),$$

$$\begin{aligned}S(\ell+1,s)=\sum_{d}\bigl(&10\,S(\ell,s-d)\\&+d\,C(\ell,s-d)\bigr),\end{aligned}$$

where $C(\ell,t)=S(\ell,t)=0$ whenever $t\lt0$ or $t\gt9\ell$. For right blocks the digit $d$ runs over $0,\dots,9$ at every step. For left blocks the first digit, appended to the empty block, runs over $1,\dots,9$, and every later digit over $0,\dots,9$. This is dynamic programming: ^[5] each entry is computed once, from the entries of the previous length, and then serves every length of balanced number that needs it.

For example $C_L(1,s)=1$ and $S_L(1,s)=s$ for $1\le s\le9$, and the step to $\ell=2$ gives $S_L(2,4)=40+31+22+13$${}=106$, from the digits $d=0,1,2,3$, with $C_L(2,4)=4$, as found in Section 3. Writing a digit $d$ as the power $x^d$ turns a string of $h$ digits into the product $x^s$, with $s$ its digit sum, so $C_R(h,s)$ is the coefficient of $x^s$ in $(1+x+\dots+x^9)^h$, the generating function of the counts; for $h=2$ the coefficient of $x^4$ is $5$, from $04,13,22,31,40$. The sum of the squares of the counts over $s$, the number of strings of $2h$ digits whose halves have equal digit sums, is the lucky-ticket number $1,10,670,55252,\dots$ for $h=0,1,2,3$. ^[6]

7. A closed form, and why the program avoids it

Two identities explain the tables and give an independent check. A right block that starts with $0$ is a right block of length $h-1$ with the same value, and the other right blocks are the left blocks, so for $h\ge1$

$$C_L(h,s)=C_R(h,s)-C_R(h-1,s),$$

$$S_L(h,s)=S_R(h,s)-S_R(h-1,s);$$

for example $106=110-4$. Moreover, swapping two digit positions maps the right blocks of digit sum $s$ one to one onto themselves, so every position carries the same total of digits over these blocks. The $h$ totals add up to $s\,C_R(h,s)$, so each of them is $s\,C_R(h,s)/h$, and with the repunit $R_h=(10^h-1)/9=11\dots1$ of $h$ ones ^[7]

$$S_R(h,s)=\frac{s\,R_h\,C_R(h,s)}{h};$$

for $h=2$ and $s=4$ this is $4\cdot11\cdot5/2=110$. The program uses neither identity. The second one divides by $h$, and the remainder of a quotient modulo $3^{15}$ is fixed by the remainder of the numerator only if $h$ has an inverse, a number $u$ with $hu\equiv1\pmod{3^{15}}$, which exists exactly when $3$ does not divide $h$. ^[8] For $h=3,6,9,\dots$ one would have to keep the numerator modulo $h\cdot3^{15}$ and divide exactly; the recurrence of Section 6 never divides and needs no such care.

8. Working modulo $3^{15}$

The exact numbers are large: the largest count $C_R(23,s)$, at $s=103$ and $s=104$, has $22$ digits and does not fit into $64$ bits, and $T(47)$ itself has $93$ digits. We only need the remainder modulo $M=3^{15}$, and remainders may be taken at every step: if $a\equiv a'$ and $b\equiv b'\pmod M$, then $a+b\equiv a'+b'$ and $ab\equiv a'b'\pmod M$. ^[8] The formulas of Sections 4 to 6 use only additions and multiplications by integers, so every table entry, every power of ten and every partial sum can be replaced by its remainder as soon as it is formed, and the final remainder is still that of $T(47)$.

How the Code Works

The C++ program ^[9] keeps its parameters in Options: $n=47$, the modulus $14348907=3^{15}$ and a flag for the checks; parse_arguments accepts --n=, --mod= and --skip-checkpoints. add_mod adds two remainders in 64 bits and subtracts the modulus once if needed, which is exact for every modulus up to $2^{63}$ but can wrap around for a larger --mod=; mul_mod multiplies two remainders in unsigned 128-bit arithmetic, a GCC and Clang extension, ^[10] before reducing, so no product can overflow.

build_dp(max_len, leading_nonzero, mod) returns a DigitDP with the tables count and sum, a row per length up to max_len and a column per digit sum. From count[0][0] $=1$, the empty block, it pushes every state forward: for each allowed digit $d$ it adds the count to count[len+1][s+d] and ten times the value sum plus $d$ times the count to sum[len+1][s+d], Section 6 read the other way round; with leading_nonzero set, the first digit starts at $1$. States with both entries $0$ modulo $M$ are skipped, which changes nothing.

solve_mod(n, mod) builds the left table and the right table up to max_half $=\lfloor(n+1)/2\rfloor$, which is $24$ for $n=47$, one row more than the longest half that is used, $\lfloor47/2\rfloor=23$. It stores $10^i\bmod M$ for $i\le n+1$ in pow10. Then, for each length len from $1$ to $n$, it sets half to $\lfloor$len$/2\rfloor$, reads the four rows for half and adds, for every digit sum, the two terms of Section 4 (part_left and part_right) or the three terms of Section 5 (part_left, part_mid and part_right) to total.

This loop skips a digit sum as soon as one of the two counts is $0$ modulo $M$. That is safe when the count itself is $0$, because its value sum is then $0$ too, and for the modulus $3^{15}$ we checked that no nonzero count $C_L(h,s)$ or $C_R(h,s)$ with $h\le23$ is divisible by $3^{15}$, so nothing is lost here. With another modulus given by --mod=, the shortcut can drop real terms: modulo $10$, the count $C_R(2,9)=10$ vanishes, the term $S_R(2,9)\,C_L(2,9)$${}=495\cdot9=4455$ is lost, and --n=4 --mod=10 prints $5$, although $T(4)=3364890$ ends in $0$.

run_checkpoints calls solve_mod with the modulus $10^{18}$, which for these small $n$ exceeds every number that occurs, so the remainders are exact values: it compares $T(1)$, $T(2)$ and $T(5)$ with the statement, and $T(6)$ with brute_small(6), which tests every $x\lt10^6$ through its decimal string, with the limit $10^6$ computed by pow10_mod. main runs these checks unless --skip-checkpoints is given, returns the exit code $2$ if one fails, and prints solve_mod(n, mod).

The Python and Java programs contain the same tables and the same loop, both shortcuts included, for the fixed values $n=47$ and $M=3^{15}$, without options or checks. Python's integers are unbounded, so its mul_mod is simply (a * b) % mod. Java uses long, whose largest value is $2^{63}-1$; every remainder is below $3^{15}\lt2^{24}$, so a product of two remainders is below $2^{48}$, and since the program reduces modulo MOD before it multiplies again, nothing overflows. ^[10]

Complexity and Verification

Let $H=\lfloor(n+1)/2\rfloor$. Filling a table visits, for each length $\ell\lt H$, the $9\ell+1$ digit sums and up to ten digits for each, about $45H^2$ steps: for $n=47$ these are $25080$ steps for the right table and $24849$ for the left one. The main loop visits $9\lfloor k/2\rfloor+1$ digit sums for each length $k\le n$, $5015$ in all for $n=47$. Time and memory therefore grow like $n^2$. The four tables hold $4\cdot25\cdot217=21700$ numbers, $173600$ bytes as 64-bit integers in C++ and Java, while a direct search would have to test almost $10^{47}$ numbers. In our tests all three programs, the C++ checks included, finished in a few hundredths of a second.

All three programs print the same remainder, and the C++ checkpoints pass. Further checks for this article, not part of the published programs:

a direct test of every number below $10^9$ gives $T(1),\dots,T(9)$, among them $T(3)=50040$, $T(4)=3364890$ and $T(6)=27671338200$, and these equal the exact values of the formulas of Sections 4 and 5, as well as the output of the C++ program with the modulus $10^{18}$;
the same formulas evaluated with Python's unbounded integers and reduced modulo $3^{15}$ only at the end agree with the C++ program for every $n\le47$, and with all three programs for $n=47$;
the identities of Section 7 hold for every $h\le30$, and the worked examples of Sections 4 and 5 agree with direct sums over their $20$ and $200$ numbers.

Footnotes and References

The references below supply the background facts used above; the cut into blocks, the formulas for $U_k$ and the closed form of Section 7 are derived in this article.

Project Euler 217 — Balanced Numbers. The official statement calls a positive integer with k decimal digits balanced if its first ⌈k/2⌉ digits sum to the same value as its last ⌈k/2⌉ digits, notes that all palindromes and 13722 are balanced, defines T(n) as the sum of all balanced numbers less than 10ⁿ, gives T(1) = 45, T(2) = 540 and T(5) = 334795890, and asks for T(47) mod 3¹⁵.
Wikipedia — Palindromic number. A palindromic number stays the same when its digits are reversed; in base 10 there are 90 palindromic numbers with three digits and 90 with four digits.
Wikipedia — Digit sum. The digit sum of a natural number in a given base is the sum of all its digits.
Wikipedia — Positional notation. The value of a numeral is the sum of its digits times the values of their places, powers of the base; Horner's method, used there for base conversion, multiplies by the base and adds the next digit.
Wikipedia — Dynamic programming. Developed by Richard Bellman in the 1950s, the method breaks a problem into simpler sub-problems and solves each of them only once, storing the results, here bottom-up in tables.
OEIS A174061 — The Lucky Tickets Problem. The number of tickets of 2n digits, leading zeros allowed, whose first n digits have the same sum as their last n digits: 1, 10, 670, 55252, 4816030, …; the entry's program adds the squares of the coefficients of (1 + x + ⋯ + x⁹)ⁿ.
Wikipedia — Repunit. A repunit is a number such as 11, 111 or 1111 that contains only the digit 1; in base 10, Rₙ = (10ⁿ − 1)/9.
Wikipedia — Modular arithmetic. Congruence modulo m is compatible with addition and multiplication: if a₁ ≡ b₁ and a₂ ≡ b₂ (mod m), then a₁ + a₂ ≡ b₁ + b₂ and a₁a₂ ≡ b₁b₂ (mod m). An integer a has an inverse modulo m if and only if a is coprime with m.
C++ — Euler217.cpp. The linked immutable C++ revision contains build_dp, solve_mod, brute_small and run_checkpoints. It is the implementation record for this article.
GCC manual — 128-bit Integers: unsigned __int128 is an unsigned 128-bit integer type. Python — numeric types: integers have unlimited precision. Java Language Specification, §4.2.1: a long lies between −2⁶³ and 2⁶³ − 1, and by §4.2.2 the integer operators do not indicate overflow.

Problem 217 source code

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

namespace {

using u64 = std::uint64_t;
using u128 = __uint128_t;

struct Options {
    int n = 47;
    u64 mod = 14348907ULL;  // 3^15
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_u64_after_prefix(const std::string& arg, const std::string& prefix, u64& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    u64 parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<u64>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--n=", options.n) ||
            parse_u64_after_prefix(arg, "--mod=", options.mod)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }

    return options.n >= 1 && options.mod >= 2;
}

u64 add_mod(const u64 a, const u64 b, const u64 mod) {
    u64 s = a + b;
    if (s >= mod) {
        s -= mod;
    }
    return s;
}

u64 mul_mod(const u64 a, const u64 b, const u64 mod) {
    return static_cast<u64>((static_cast<u128>(a) * b) % mod);
}

struct DigitDP {
    std::vector<std::vector<u64>> count;
    std::vector<std::vector<u64>> sum;
};

DigitDP build_dp(const int max_len, const bool leading_nonzero, const u64 mod) {
    const int max_sum = 9 * max_len;
    std::vector<std::vector<u64>> count(max_len + 1, std::vector<u64>(max_sum + 1, 0));
    std::vector<std::vector<u64>> sum(max_len + 1, std::vector<u64>(max_sum + 1, 0));

    count[0][0] = 1;

    for (int len = 0; len < max_len; ++len) {
        const int cur_max_sum = 9 * len;
        for (int s = 0; s <= cur_max_sum; ++s) {
            const u64 cnt = count[len][s];
            const u64 sm = sum[len][s];
            if (cnt == 0 && sm == 0) {
                continue;
            }

            int d_start = 0;
            int d_end = 9;
            if (leading_nonzero && len == 0) {
                d_start = 1;
            }

            for (int d = d_start; d <= d_end; ++d) {
                const int ns = s + d;
                count[len + 1][ns] = add_mod(count[len + 1][ns], cnt, mod);

                u64 val = mul_mod(sm, 10ULL, mod);
                val = add_mod(val, mul_mod(static_cast<u64>(d), cnt, mod), mod);
                sum[len + 1][ns] = add_mod(sum[len + 1][ns], val, mod);
            }
        }
    }

    return {std::move(count), std::move(sum)};
}

u64 pow10_mod(const int exp, const u64 mod) {
    u64 result = 1 % mod;
    u64 base = 10 % mod;
    int e = exp;
    while (e > 0) {
        if (e & 1) {
            result = mul_mod(result, base, mod);
        }
        base = mul_mod(base, base, mod);
        e >>= 1;
    }
    return result;
}

u64 solve_mod(const int n, const u64 mod) {
    const int max_half = (n + 1) / 2;
    const DigitDP left_dp = build_dp(max_half, true, mod);
    const DigitDP right_dp = build_dp(max_half, false, mod);

    std::vector<u64> pow10(static_cast<std::size_t>(n + 2), 1 % mod);
    for (int i = 1; i <= n + 1; ++i) {
        pow10[static_cast<std::size_t>(i)] = mul_mod(pow10[static_cast<std::size_t>(i - 1)], 10ULL, mod);
    }

    u64 total = 0;

    for (int len = 1; len <= n; ++len) {
        const int half = len / 2;
        const bool odd = (len % 2 == 1);
        const int max_sum = 9 * half;

        const auto& cnt_left = left_dp.count[half];
        const auto& sum_left = left_dp.sum[half];
        const auto& cnt_right = right_dp.count[half];
        const auto& sum_right = right_dp.sum[half];

        if (!odd) {
            const u64 shift = pow10[static_cast<std::size_t>(half)];
            for (int s = 0; s <= max_sum; ++s) {
                const u64 cl = cnt_left[static_cast<std::size_t>(s)];
                const u64 cr = cnt_right[static_cast<std::size_t>(s)];
                if (cl == 0 || cr == 0) {
                    continue;
                }

                const u64 part_left = mul_mod(mul_mod(sum_left[static_cast<std::size_t>(s)], shift, mod), cr, mod);
                const u64 part_right = mul_mod(sum_right[static_cast<std::size_t>(s)], cl, mod);
                total = add_mod(total, add_mod(part_left, part_right, mod), mod);
            }
        } else {
            const u64 shift_left = pow10[static_cast<std::size_t>(half + 1)];
            const u64 shift_mid = pow10[static_cast<std::size_t>(half)];
            for (int s = 0; s <= max_sum; ++s) {
                const u64 cl = cnt_left[static_cast<std::size_t>(s)];
                const u64 cr = cnt_right[static_cast<std::size_t>(s)];
                if (cl == 0 || cr == 0) {
                    continue;
                }

                const u64 part_left = mul_mod(mul_mod(sum_left[static_cast<std::size_t>(s)], shift_left, mod), mul_mod(cr, 10ULL, mod), mod);
                const u64 part_mid = mul_mod(mul_mod(45ULL, shift_mid, mod), mul_mod(cl, cr, mod), mod);
                const u64 part_right = mul_mod(mul_mod(sum_right[static_cast<std::size_t>(s)], cl, mod), 10ULL, mod);

                total = add_mod(total, add_mod(add_mod(part_left, part_mid, mod), part_right, mod), mod);
            }
        }
    }

    return total;
}

u64 brute_small(const int n) {
    const u64 limit = pow10_mod(n, 1000000000000000000ULL);

    auto balanced = [](u64 x) {
        std::string s = std::to_string(x);
        const int k = static_cast<int>(s.size());
        const int m = (k + 1) / 2;
        int left = 0;
        int right = 0;
        for (int i = 0; i < m; ++i) {
            left += s[static_cast<std::size_t>(i)] - '0';
            right += s[static_cast<std::size_t>(k - 1 - i)] - '0';
        }
        return left == right;
    };

    u64 sum = 0;
    for (u64 x = 1; x < limit; ++x) {
        if (balanced(x)) {
            sum += x;
        }
    }
    return sum;
}

bool run_checkpoints() {
    if (solve_mod(1, 1000000000000000000ULL) != 45ULL) {
        std::cerr << "Checkpoint failed for T(1)" << '\n';
        return false;
    }
    if (solve_mod(2, 1000000000000000000ULL) != 540ULL) {
        std::cerr << "Checkpoint failed for T(2)" << '\n';
        return false;
    }
    if (solve_mod(5, 1000000000000000000ULL) != 334795890ULL) {
        std::cerr << "Checkpoint failed for T(5)" << '\n';
        return false;
    }
    if (solve_mod(6, 1000000000000000000ULL) != brute_small(6)) {
        std::cerr << "Checkpoint failed for brute-force cross-check T(6)" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }

    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << solve_mod(options.n, options.mod) << '\n';
    return 0;
}

Python

# Problem 217: Balanced Numbers
# Sum of all balanced numbers < 10^47, mod 3^15.
# A number is balanced if sum of first half digits = sum of second half digits.

def solve():
    n = 47
    mod = 3**15  # 14348907

    def add_mod(a, b):
        s = a + b
        return s - mod if s >= mod else s

    def mul_mod(a, b):
        return (a * b) % mod

    # Build DP for left/right halves
    def build_dp(max_len, leading_nonzero):
        max_sum = 9 * max_len
        count = [[0] * (max_sum + 1) for _ in range(max_len + 1)]
        sumv = [[0] * (max_sum + 1) for _ in range(max_len + 1)]
        count[0][0] = 1
        for l in range(max_len):
            for s in range(9 * l + 1):
                cnt = count[l][s]
                sm = sumv[l][s]
                if cnt == 0 and sm == 0:
                    continue
                d_start = 1 if (leading_nonzero and l == 0) else 0
                for d in range(d_start, 10):
                    ns = s + d
                    count[l+1][ns] = add_mod(count[l+1][ns], cnt)
                    val = add_mod(mul_mod(sm, 10), mul_mod(d, cnt))
                    sumv[l+1][ns] = add_mod(sumv[l+1][ns], val)
        return count, sumv

    max_half = (n + 1) // 2
    cnt_left, sum_left = build_dp(max_half, True)
    cnt_right, sum_right = build_dp(max_half, False)

    pow10 = [1 % mod] * (n + 2)
    for i in range(1, n + 2):
        pow10[i] = mul_mod(pow10[i-1], 10)

    total = 0
    for length in range(1, n + 1):
        half = length // 2
        odd = length % 2 == 1
        max_sum = 9 * half

        cl = cnt_left[half]
        sl = sum_left[half]
        cr = cnt_right[half]
        sr = sum_right[half]

        if not odd:
            shift = pow10[half]
            for s in range(max_sum + 1):
                if cl[s] == 0 or cr[s] == 0:
                    continue
                part_l = mul_mod(mul_mod(sl[s], shift), cr[s])
                part_r = mul_mod(sr[s], cl[s])
                total = add_mod(total, add_mod(part_l, part_r))
        else:
            shift_l = pow10[half + 1]
            shift_m = pow10[half]
            for s in range(max_sum + 1):
                if cl[s] == 0 or cr[s] == 0:
                    continue
                part_l = mul_mod(mul_mod(sl[s], shift_l), mul_mod(cr[s], 10))
                part_m = mul_mod(mul_mod(45, shift_m), mul_mod(cl[s], cr[s]))
                part_r = mul_mod(mul_mod(sr[s], cl[s]), 10)
                total = add_mod(total, add_mod(add_mod(part_l, part_m), part_r))

    print(total)

solve()

Java

public class Euler217 {
    static final long MOD = 14348907L; // 3^15

    public static void main(String[] args) {
        int n = 47;
        int maxHalf = (n + 1) / 2;
        long[][] cntL = new long[maxHalf + 1][], sumL = new long[maxHalf + 1][];
        long[][] cntR = new long[maxHalf + 1][], sumR = new long[maxHalf + 1][];
        buildDP(cntL, sumL, maxHalf, true);
        buildDP(cntR, sumR, maxHalf, false);
        long[] pow10 = new long[n + 2];
        pow10[0] = 1 % MOD;
        for (int i = 1; i <= n + 1; i++)
            pow10[i] = pow10[i - 1] * 10 % MOD;
        long total = 0;
        for (int len = 1; len <= n; len++) {
            int half = len / 2;
            boolean odd = len % 2 == 1;
            int ms = 9 * half;
            if (!odd) {
                long shift = pow10[half];
                for (int s = 0; s <= ms; s++) {
                    if (cntL[half][s] == 0 || cntR[half][s] == 0)
                        continue;
                    long pl = sumL[half][s] * shift % MOD * cntR[half][s] % MOD;
                    long pr = sumR[half][s] * cntL[half][s] % MOD;
                    total = (total + pl + pr) % MOD;
                }
            } else {
                long shiftL = pow10[half + 1], shiftM = pow10[half];
                for (int s = 0; s <= ms; s++) {
                    if (cntL[half][s] == 0 || cntR[half][s] == 0)
                        continue;
                    long pl = sumL[half][s] * shiftL % MOD * (cntR[half][s] * 10 % MOD) % MOD;
                    long pm = 45L * shiftM % MOD * (cntL[half][s] * cntR[half][s] % MOD) % MOD;
                    long pr = sumR[half][s] * cntL[half][s] % MOD * 10 % MOD;
                    total = (total + pl + pm + pr) % MOD;
                }
            }
        }
        System.out.println(total);
    }

    static void buildDP(long[][] count, long[][] sum, int maxLen, boolean leadNonzero) {
        for (int l = 0; l <= maxLen; l++) {
            count[l] = new long[9 * maxLen + 1];
            sum[l] = new long[9 * maxLen + 1];
        }
        count[0][0] = 1;
        for (int l = 0; l < maxLen; l++) {
            for (int s = 0; s <= 9 * l; s++) {
                long c = count[l][s], sv = sum[l][s];
                if (c == 0 && sv == 0)
                    continue;
                int d0 = (leadNonzero && l == 0) ? 1 : 0;
                for (int d = d0; d <= 9; d++) {
                    int ns = s + d;
                    count[l + 1][ns] = (count[l + 1][ns] + c) % MOD;
                    long val = (sv * 10 + d * c) % MOD;
                    sum[l + 1][ns] = (sum[l + 1][ns] + val) % MOD;
                }
            }
        }
    }
}