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

Project Euler problem page: Problem 217
Digit sum: Wikipedia - Digit sum
Dynamic programming: Wikipedia - Dynamic programming
Positional notation: Wikipedia - Positional notation
Modular arithmetic: Wikipedia - Modular arithmetic

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;
                }
            }
        }
    }
}