Project Euler

Balanced Numbers

A positive integer with k digits (base 10) is balanced if the sum of the first floor(k/2) digits equals the sum of the last floor(k/2) digits. For odd k, the middle digit is ignored. All 1-digit nu...

Source sync Apr 19, 2026

Problem #0217

Level Level 11

Solved By 1,776

Languages C++, Python

Answer 6273134

Length 309 words

modular_arithmeticlinear_algebradynamic_programming

A positive integer with $k$ (decimal) digits is called balanced if its first $\lceil k/2 \rceil $ digits sum to the same value as its last $\lceil k/2 \rceil $ digits, where $\lceil x \rceil $, pronounced ceiling of $x$, is the smallest integer $\ge x$, thus $\lceil \pi \rceil = 4$ and $\lceil 5 \rceil = 5$.

So, for example, all palindromes are balanced, as is $13722$.

Let $T(n)$ be the sum of all balanced numbers less than $10^n$.

Thus: $T(1) = 45$, $T(2) = 540$ and $T(5) = 334795890$.

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

Problem 217: Balanced Numbers

Mathematical Foundation

Definition. For a $k$ -digit number, let $h = \lfloor k/2 \rfloor$ . Write the number as:

Even $k = 2h$ : $N = L \cdot 10^h + R$ , where $L$ is an $h$ -digit number ( $10^{h-1} \leq L < 10^h$ ) and $0 \leq R < 10^h$ .
Odd $k = 2h+1$ : $N = L \cdot 10^{h+1} + m \cdot 10^h + R$ , where $L$ is $h$ digits, $m \in \{0, \ldots, 9\}$ , $0 \leq R < 10^h$ .

Balanced means $\operatorname{digitsum}(L) = \operatorname{digitsum}(R)$ .

Theorem 1 (Decomposition of balanced number sum). Define for $h$ -digit strings (with possible leading zeros):

$C(h, s) = |\{x : 0 \leq x < 10^h,\; \operatorname{digitsum}(x) = s\}|$
$\Sigma(h, s) = \sum_{\substack{0 \leq x < 10^h \\ \operatorname{digitsum}(x) = s}} x$

For the left half (no leading zeros): $C_L(h, s) = C(h, s) - C(h-1, s)$ and $\Sigma_L(h, s) = \Sigma(h, s) - \Sigma(h-1, s)$ (subtracting strings with leading zero).

Then for even $k = 2h$ :

\text{Sum}_{2h} = \sum_{s=0}^{9h} \bigl[\Sigma_L(h,s) \cdot 10^h \cdot C(h,s) + C_L(h,s) \cdot \Sigma(h,s)\bigr]

For odd $k = 2h+1$ :

\text{Sum}_{2h+1} = \sum_{s=0}^{9h} \bigl[10 \cdot \Sigma_L(h,s) \cdot 10^{h+1} \cdot C(h,s) + 45 \cdot 10^h \cdot C_L(h,s) \cdot C(h,s) + 10 \cdot C_L(h,s) \cdot \Sigma(h,s)\bigr]

Proof. For even $k = 2h$ : a balanced number $N = L \cdot 10^h + R$ with $\operatorname{digitsum}(L) = \operatorname{digitsum}(R) = s$ . Summing over all such $N$ :

\sum_N N = \sum_N (L \cdot 10^h + R) = 10^h \sum_L L \cdot |\{R : \operatorname{digitsum}(R) = s\}| + \sum_R R \cdot |\{L : \operatorname{digitsum}(L) = s, L \geq 10^{h-1}\}|

= 10^h \cdot \Sigma_L(h,s) \cdot C(h,s) + C_L(h,s) \cdot \Sigma(h,s)

Summing over $s$ gives the formula. For odd $k = 2h+1$ : $N = L \cdot 10^{h+1} + m \cdot 10^h + R$ , summing over $m = 0, \ldots, 9$ (giving a factor of 10 for $L$ and $R$ terms, and $\sum m = 45$ for the middle digit term). $\square$

Lemma 1 (DP for digit-sum statistics). The functions $C(h, s)$ and $\Sigma(h, s)$ satisfy the recurrences:

C(h, s) = \sum_{d=0}^{9} C(h-1, s-d)

\Sigma(h, s) = \sum_{d=0}^{9} \bigl[10 \cdot \Sigma(h-1, s-d) + d \cdot C(h-1, s-d)\bigr]

with base cases $C(0, 0) = 1$ , $C(0, s) = 0$ for $s \neq 0$ , $\Sigma(0, 0) = 0$ .

Proof. The last digit $d$ of an $h$ -digit string contributes $d$ to the digit sum and $d$ to the numeric value. Removing the last digit gives an $(h-1)$ -digit string with digit sum $s - d$ and value $v$ . The original string has value $10v + d$ . Summing: $\Sigma(h, s) = \sum_d \sum_v (10v + d) = \sum_d [10 \cdot \Sigma(h-1, s-d) + d \cdot C(h-1, s-d)]$ . The count recurrence is analogous. $\square$

Editorial

Sum of all balanced numbers below 10^47, mod 3^15 = 14348907. A k-digit number is balanced if the digit sum of the first floor(k/2) digits equals the digit sum of the last floor(k/2) digits. For odd k, the middle digit is ignored. We compute C(h, s) and Sigma(h, s) via DP. We then also compute C(h-1, s) and Sigma(h-1, s). Finally, we build the tables C[0..h][0..max_s] and Sigma[0..h][0..max_s].

Pseudocode

1-digit balanced numbers: 1+2+...+9 = 45
Compute C(h, s) and Sigma(h, s) via DP
Also compute C(h-1, s) and Sigma(h-1, s)
DP: build tables C[0..h][0..max_s], Sigma[0..h][0..max_s]
Compute left-half tables (no leading zeros)
Accumulate sum for this digit length
if k is even

Complexity Analysis

Time: For each digit length $k$ (up to 47), the DP builds tables of size $h \times 9h$ where $h \leq 23$ . Each entry requires $O(10)$ work. Total: $O\bigl(\sum_{k=2}^{47} h \cdot 9h \cdot 10\bigr) = O(47 \cdot 23^2 \cdot 90) \approx O(2.2 \times 10^6)$ .
Space: $O(h \cdot 9h) = O(h^2)$ per digit length, reusable. Maximum $O(23^2) \approx O(500)$ .

Answer

\boxed{6273134}

C++ project_euler/problem_217/solution.cpp

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

/*
 * Problem 217: Balanced Numbers
 *
 * Sum of all balanced numbers below 10^47, mod 3^15.
 *
 * A k-digit number is balanced if the digit sum of the first floor(k/2)
 * digits equals the digit sum of the last floor(k/2) digits.
 *
 * We compute for each digit length k from 1 to 47.
 */

const long long MOD = 14348907LL; // 3^15

int main() {
    // Maximum half-length
    int maxH = 23; // floor(47/2)
    int maxSum = 9 * maxH; // max digit sum for h digits

    // For each h, compute:
    // cnt[h][s] = count of h-digit strings (with leading zeros) with digit sum s
    // sm[h][s]  = sum of values of such strings
    // cntL[h][s] = count of h-digit numbers (no leading zero) with digit sum s
    // smL[h][s]  = sum of such numbers

    // We'll compute these incrementally.
    // cnt[0][0] = 1, sm[0][0] = 0
    // For h digits, adding a new digit d at the most significant position:
    // Actually let's build from the least significant digit.
    // A string of h digits: d_{h-1} d_{h-2} ... d_0
    // Value = sum(d_i * 10^i), digit sum = sum(d_i).

    // DP: after placing i digits (positions 0..i-1), with digit sum s:
    // cnt_dp[i][s], sum_dp[i][s]

    // Transition: add digit d at position i:
    // cnt_dp[i+1][s+d] += cnt_dp[i][s]
    // sum_dp[i+1][s+d] += sum_dp[i][s] + d * 10^i * cnt_dp[i][s]

    // This gives us cnt(h, s) = cnt_dp[h][s] and sm(h, s) = sum_dp[h][s]
    // for h-digit strings with possible leading zeros.

    // For left halves (leading digit >= 1 at position h-1):
    // cntL(h, s) = cnt(h, s) - cnt(h-1, s)  [subtract those with d_{h-1}=0]
    // smL(h, s) = sm(h, s) - sm(h-1, s)

    // Actually more carefully: h-digit strings with leading zero are exactly
    // 0 followed by (h-1)-digit string. So cnt(h,s) with leading zero = cnt(h-1,s),
    // and sum with leading zero = sm(h-1,s) (value is same since leading 0 adds nothing).

    // So cntL(h,s) = cnt(h,s) - cnt(h-1,s), smL(h,s) = sm(h,s) - sm(h-1,s).

    // We need arrays up to h=23, sum up to 9*23=207.
    int MAXS = maxSum + 1;

    // cnt_dp[s] and sum_dp[s] for current h
    vector<vector<long long>> cnt(maxH + 1, vector<long long>(MAXS, 0));
    vector<vector<long long>> sm(maxH + 1, vector<long long>(MAXS, 0));

    cnt[0][0] = 1;
    sm[0][0] = 0;

    // pow10[i] = 10^i mod MOD
    vector<long long> pow10(48, 1);
    for (int i = 1; i < 48; i++) pow10[i] = pow10[i-1] * 10 % MOD;

    for (int i = 0; i < maxH; i++) {
        // Add digit d at position i (0-indexed from right)
        for (int s = 0; s < MAXS; s++) {
            if (cnt[i][s] == 0 && sm[i][s] == 0) continue;
            for (int d = 0; d <= 9; d++) {
                int ns = s + d;
                if (ns >= MAXS) break;
                cnt[i+1][ns] = (cnt[i+1][ns] + cnt[i][s]) % MOD;
                sm[i+1][ns] = (sm[i+1][ns] + sm[i][s] + (long long)d % MOD * pow10[i] % MOD * cnt[i][s]) % MOD;
            }
        }
    }

    long long total = 0;

    // 1-digit numbers (k=1): all are balanced (h=0, both halves empty).
    // Sum = 1+2+...+9 = 45
    total = 45 % MOD;

    for (int k = 2; k <= 47; k++) {
        int h = k / 2;
        bool odd = (k % 2 == 1);

        // For even k=2h: sum = sum_s [ smL(h,s) * 10^h * cnt(h,s) + cntL(h,s) * sm(h,s) ]
        // For odd k=2h+1: sum = sum_s [ 10 * smL(h,s) * 10^(h+1) * cnt(h,s)
        //                              + 45 * 10^h * cntL(h,s) * cnt(h,s)
        //                              + 10 * cntL(h,s) * sm(h,s) ]

        long long contribution = 0;

        for (int s = 1; s <= 9 * h; s++) { // s >= 1 since left half has no leading zero => digit sum >= 1
            long long cntH = cnt[h][s];
            long long smH = sm[h][s];
            long long cntL_s = (cnt[h][s] - (h >= 1 ? cnt[h-1][s] : 0) % MOD + MOD) % MOD;
            long long smL_s = (sm[h][s] - (h >= 1 ? sm[h-1][s] : 0) % MOD + MOD) % MOD;

            if (!odd) {
                // even: k = 2h
                long long term = (smL_s % MOD * pow10[h] % MOD * cntH % MOD
                                  + cntL_s % MOD * smH % MOD) % MOD;
                contribution = (contribution + term) % MOD;
            } else {
                // odd: k = 2h+1
                long long term = (10 * smL_s % MOD * pow10[h+1] % MOD * cntH % MOD) % MOD;
                term = (term + 45 * pow10[h] % MOD * cntL_s % MOD * cntH % MOD) % MOD;
                term = (term + 10 * cntL_s % MOD * smH % MOD) % MOD;
                contribution = (contribution + term) % MOD;
            }
        }

        total = (total + contribution) % MOD;
    }

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

Python project_euler/problem_217/solution.py

"""
Problem 217: Balanced Numbers

Sum of all balanced numbers below 10^47, mod 3^15 = 14348907.

A k-digit number is balanced if the digit sum of the first floor(k/2)
digits equals the digit sum of the last floor(k/2) digits.
For odd k, the middle digit is ignored.

Answer: 6273134
"""

def solve():
    MOD = 3**15  # 14348907
    MAX_K = 47
    MAX_H = MAX_K // 2  # 23
    MAX_S = 9 * MAX_H   # 207

    # cnt[h][s] = count of h-digit strings (leading zeros OK) with digit sum s
    # sm[h][s]  = sum of values of such strings
    cnt = [[0] * (MAX_S + 1) for _ in range(MAX_H + 1)]
    sm = [[0] * (MAX_S + 1) for _ in range(MAX_H + 1)]

    cnt[0][0] = 1

    pow10 = [1] * 48
    for i in range(1, 48):
        pow10[i] = pow10[i-1] * 10 % MOD

    for i in range(MAX_H):
        for s in range(MAX_S + 1):
            if cnt[i][s] == 0 and sm[i][s] == 0:
                continue
            for d in range(10):
                ns = s + d
                if ns > MAX_S:
                    break
                cnt[i+1][ns] = (cnt[i+1][ns] + cnt[i][s]) % MOD
                sm[i+1][ns] = (sm[i+1][ns] + sm[i][s] + d * pow10[i] * cnt[i][s]) % MOD

    # 1-digit numbers: all balanced, sum = 45
    total = 45 % MOD

    for k in range(2, MAX_K + 1):
        h = k // 2
        odd = (k % 2 == 1)

        contribution = 0

        for s in range(1, 9 * h + 1):
            cntH = cnt[h][s]
            smH = sm[h][s]
            cntL = (cnt[h][s] - (cnt[h-1][s] if h >= 1 else 0)) % MOD
            smL = (sm[h][s] - (sm[h-1][s] if h >= 1 else 0)) % MOD

            if not odd:
                term = (smL * pow10[h] % MOD * cntH + cntL * smH) % MOD
            else:
                term = (10 * smL % MOD * pow10[h+1] % MOD * cntH) % MOD
                term = (term + 45 * pow10[h] % MOD * cntL % MOD * cntH) % MOD
                term = (term + 10 * cntL % MOD * smH) % MOD

            contribution = (contribution + term) % MOD

        total = (total + contribution) % MOD

    print(total % MOD)

if __name__ == "__main__":
    solve()