Project Euler

Balanced Numbers

A positive integer with k digits 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 numbers are...

Source sync May 21, 2026

Problem #0217

Level Level 11

Solved By 1,776

Languages C++, Python

Answer 6273134

Length 368 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 Development

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

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

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

Theorem 1 (Decomposition of the balanced-number sum). For $h$ -digit strings allowing leading zeros, define

$C(h, s)$ = number of strings with digit sum $s$
$\Sigma(h, s)$ = sum of the numeric values of those strings

For genuine left halves with no leading zero, define

C_L(h, s) = C(h, s) - C(h-1, s), \qquad \Sigma_L(h, s) = \Sigma(h, s) - \Sigma(h-1, s).

Then for even length $2h$ ,

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

For odd length $2h+1$ ,

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

Proof. For even length, each balanced number is formed by pairing a valid left half and a right half with the same digit sum. Summing the contribution of the left block and the right block separately gives the stated formula.

For odd length, there are 10 choices for the middle digit. The left and right contributions are therefore multiplied by 10, while the middle position contributes

0 + 1 + \cdots + 9 = 45

times the corresponding place value. $\square$

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

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

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

with base values $C(0,0)=1$ and $\Sigma(0,0)=0$ .

Proof. Append a final digit $d$ to a shorter string of digit sum $s-d$ . The count recurrence is immediate, and the value recurrence follows from the decimal-value update

v \mapsto 10v + d.

$\square$

Editorial

The balance condition couples the two halves only through their digit sum. That means the useful state is not the half-string itself, but just two aggregated quantities for each pair (length, digit sum): how many half-strings realize that sum, and what the total of their numeric values is.

Once those tables are built, assembling balanced numbers is straightforward. For each possible total length and each feasible digit sum, pair a left half with a right half of the same sum. Even and odd lengths differ only in how the middle digit is handled, so the whole problem reduces to one reusable DP table plus a clean final accumulation.

Pseudocode

Set MOD = 3^15 and MAX_HALF = 23.
Create tables count[h][s] and total_value[h][s].

Initialize count[0][0] = 1 and total_value[0][0] = 0.
Precompute powers of 10 modulo MOD.

For half-length h from 0 to MAX_HALF - 1:
    For each reachable digit sum s:
        For digit d from 0 to 9:
            count[h + 1][s + d] += count[h][s]
            total_value[h + 1][s + d] += total_value[h][s] + d * 10^h * count[h][s]
            Reduce everything modulo MOD.

answer = sum of the 1-digit numbers = 45.

For full length k from 2 to 47:
    h = floor(k / 2)
    For each digit sum s:
        left_count  = count[h][s] - count[h - 1][s]
        left_total  = total_value[h][s] - total_value[h - 1][s]
        right_count = count[h][s]
        right_total = total_value[h][s]

        If k is even:
            add the contribution of left halves shifted by 10^h
            plus the contribution of right halves.
        Otherwise:
            also include the 10 choices for the middle digit
            and their total contribution 45 * 10^h.

Return answer modulo MOD.

Complexity Analysis

Time: Building the half-string tables costs $O(H S \cdot 10)$ with $H = 23$ and $S = 9H = 207$ . The final accumulation over all lengths costs $O(47S)$ .
Space: $O(HS)$ for the count and value tables.

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()