Problem 515: Dissonant Numbers

Mathematical Foundation

Theorem 1 (Generating Function for Digit Sums). The number of non-negative integers with exactly $L$ digits in base $b$ (allowing leading zeros) whose digit sum equals $s$ is the coefficient

Proof. Each digit $d_i \in \{0, 1, \ldots, b-1\}$ contributes $x^{d_i}$ to the generating function. The generating function for a single digit is $1 + x + x^2 + \cdots + x^{b-1} = \frac{1 - x^b}{1 - x}$. Since the $L$ digits are independent, the generating function for the digit sum of an $L$-digit string is $\left(\frac{1-x^b}{1-x}\right)^L$. The coefficient of $x^s$ counts the strings with digit sum $s$. $\square$

Lemma 1 (Inclusion-Exclusion Evaluation). For $L$ digits in base $b$ with digit sum $s$:

Proof. Expand $\left(\frac{1-x^b}{1-x}\right)^L = (1-x^b)^L \cdot (1-x)^{-L}$. Using the binomial theorem on $(1-x^b)^L = \sum_{j=0}^{L}(-1)^j\binom{L}{j}x^{jb}$ and the negative binomial series $(1-x)^{-L} = \sum_{m=0}^{\infty}\binom{m+L-1}{L-1}x^m$, the coefficient of $x^s$ is obtained by convolution:

$\square$

Theorem 2 (Digit DP Correctness). The digit DP with states $(\mathrm{pos}, \mathrm{rem}, \mathrm{tight})$ correctly counts all integers $n \in [0, N]$ with $\mathrm{ds}_b(n) = s$.

Proof. We represent $N = (d_k d_{k-1} \cdots d_0)_b$. The DP builds $n$ digit-by-digit from the most significant position. At each step:

• If $\mathrm{tight} = \mathrm{true}$, the current digit is bounded by $d_{\mathrm{pos}}$; choosing $d < d_{\mathrm{pos}}$ releases the tight constraint for all subsequent positions.
• If $\mathrm{tight} = \mathrm{false}$, the digit ranges freely over $\{0, \ldots, b-1\}$.
• $\mathrm{rem}$ tracks the remaining digit sum needed.

Each integer $n \leq N$ corresponds to exactly one path through the DP, so the count is exact. $\square$

Editorial

Count integers with specific digit-sum properties across bases. D(b, s, N) = count of 1 <= n <= N with digit_sum_base_b(n) = s. We memo[pos][rem][tight] -> count. Finally, count integers in [0, N] with digit sum s, then subtract.

Pseudocode

memo[pos][rem][tight] -> count
Count integers in [0, N] with digit sum s, then subtract
the case n = 0 if s == 0

Complexity Analysis

• Time: $O(L \cdot s \cdot b)$ per query, where $L = \lfloor\log_b N\rfloor + 1$ is the number of digits. The tight flag doubles the state space by at most a factor of 2 (absorbed into the constant).
• Space: $O(L \cdot s)$ for the memoization table.

Answer

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

// Digit DP to count integers in [1, N] with digit sum s in base b

vector<int> to_base(long long n, int b) {
    if (n == 0) return {0};
    vector<int> ds;
    while (n > 0) { ds.push_back(n % b); n /= b; }
    reverse(ds.begin(), ds.end());
    return ds;
}

// dp[pos][rem][tight]
map<tuple<int,int,int>, long long> memo;
vector<int> digs;
int BASE, LEN;

long long dp(int pos, int rem, int tight) {
    if (rem < 0) return 0;
    if (pos == LEN) return (rem == 0) ? 1 : 0;
    auto key = make_tuple(pos, rem, tight);
    auto it = memo.find(key);
    if (it != memo.end()) return it->second;

    int limit = tight ? digs[pos] : BASE - 1;
    long long total = 0;
    for (int d = 0; d <= limit; d++) {
        total += dp(pos + 1, rem - d, tight && (d == limit));
    }
    return memo[key] = total;
}

long long D(int b, int s, long long N) {
    if (N <= 0 || s < 0) return 0;
    BASE = b;
    digs = to_base(N, b);
    LEN = digs.size();
    memo.clear();
    return dp(0, s, 1);
}

int main() {
    // Example: D(10, s, 10^6) for various s
    long long N = 1000000;
    int b = 10;

    long long total = 0;
    for (int s = 1; s <= 54; s++) {
        long long val = D(b, s, N);
        if (val > 0) {
            cout << "D(" << b << ", " << s << ", " << N << ") = " << val << endl;
            total += val;
        }
    }
    cout << "Total: " << total << " (should be " << N << ")" << endl;
    return 0;
}

"""
Problem 515: Dissonant Numbers
Count integers with specific digit-sum properties across bases.
D(b, s, N) = count of 1 <= n <= N with digit_sum_base_b(n) = s.
"""

from functools import lru_cache

def digit_sum(n: int, b: int):
    """Compute the digit sum of n in base b."""
    s = 0
    while n > 0:
        s += n % b
        n //= b
    return s

def digits_in_base(n: int, b: int) -> list:
    """Return digits of n in base b, most significant first."""
    if n == 0:
        return [0]
    ds = []
    while n > 0:
        ds.append(n % b)
        n //= b
    return ds[::-1]

def D(b: int, s: int, N: int):
    """
    Count integers 1 <= n <= N with digit sum s in base b.
    Uses digit DP.
    """
    if N <= 0 or s < 0:
        return 0

    digs = digits_in_base(N, b)
    L = len(digs)

    # dp(pos, remaining_sum, tight) = count of valid completions
    from functools import lru_cache

    @lru_cache(maxsize=None)
    def dp(pos, rem, tight):
        if rem < 0:
            return 0
        if pos == L:
            return 1 if rem == 0 else 0
        limit = digs[pos] if tight else b - 1
        total = 0
        for d in range(0, limit + 1):
            total += dp(pos + 1, rem - d, tight and (d == limit))
        return total

    # Count for 0..N; subtract n=0 which has digit sum 0
    result = dp(0, s, True)
    if s == 0:
        result -= 1  # exclude n=0
    dp.cache_clear()
    return result

def D_brute(b: int, s: int, N: int):
    """Brute-force verification."""
    return sum(1 for n in range(1, N + 1) if digit_sum(n, b) == s)

# Verify
for b in [2, 10]:
    for s in range(0, 10):
        N = 100
        assert D(b, s, N) == D_brute(b, s, N), f"Mismatch b={b}, s={s}, N={N}"
print("Verification passed.")

# Compute some values
print("\nD(10, s, 10^6) for various s:")
for s in range(1, 55):
    val = D(10, s, 10**6)
    if val > 0:
        print(f"  D(10, {s}, 10^6) = {val}")

# The full problem asks for a specific sum; compute partial example
total = sum(D(10, s, 10**6) for s in range(1, 55))
print(f"\nSum over s: {total} (should be 10^6 = {10**6})")