Problem 290: Digital Signature

Mathematical Foundation

Theorem (Divisibility Constraint). If $S(n) = S(137n)$, then $9 \mid n$.

Proof. For any non-negative integer $k$, $S(k) \equiv k \pmod{9}$ (since $10 \equiv 1 \pmod{9}$). Therefore $S(n) = S(137n)$ implies $n \equiv 137n \pmod{9}$. Since $137 \equiv 2 \pmod{9}$, this gives $n \equiv 2n \pmod{9}$, hence $n \equiv 0 \pmod{9}$. $\quad\square$

Theorem (Digit DP Recurrence). Define $f(\text{pos}, c, d)$ as the number of ways to choose digits at positions $\text{pos}, \text{pos}+1, \ldots, 17$ (from least significant to most significant) such that:

• $c$ is the current carry in the multiplication by 137,
• $d$ is the accumulated difference $S(n) - S(137n)$ from the already-processed positions.

Then the recurrence is: for each digit $y \in \{0, 1, \ldots, 9\}$, compute $137y + c = 10u + v$ where $u = \lfloor(137y+c)/10\rfloor$ and $v = (137y+c) \bmod 10$. Then:

Base case: $f(18, c, d) = [d = S(c)]$ where $S(c)$ is the digit sum of the carry $c$.

The answer is $f(0, 0, 0)$.

Proof. Write $n = \sum_{i=0}^{17} y_i \cdot 10^i$. The multiplication $137n$ produces digits that depend on the carry chain. At position $\text{pos}$, if the digit of $n$ is $y$ and the incoming carry from lower positions is $c$, then the digit of $137n$ at this position is $v = (137y + c) \bmod 10$ and the outgoing carry is $u = \lfloor(137y+c)/10\rfloor$.

The contribution to $S(n)$ from this position is $y$, and the contribution to $S(137n)$ is $v$. The accumulated difference updates by $y - v$.

After processing all 18 digits of $n$, the remaining carry $c$ forms additional upper digits of $137n$ (since $137n$ can have up to 20 digits). These upper digits have digit sum $S(c)$. The condition $S(n) = S(137n)$ becomes $d_{\text{accumulated}} = S(c)$, yielding the base case. $\quad\square$

Lemma (State Space Bounds). The DP state space is bounded as follows:

• Position: $0 \le \text{pos} \le 18$.
• Carry: $0 \le c \le 136$ (since $\max(137 \cdot 9 + c_{\text{prev}}) = 137 \cdot 9 + 136 = 1369$, giving $u \le 136$).
• Difference: $-162 \le d \le 162$ (since each of 18 digits contributes at most $\pm 9$).

Total states: $19 \times 137 \times 325 = 846{,}175$.

Proof. The carry bound: at the first position, $c = 0$. For subsequent positions, $u = \lfloor(137y + c)/10\rfloor \le \lfloor(137 \cdot 9 + 136)/10\rfloor = \lfloor 1369/10 \rfloor = 136$. By induction, the carry never exceeds 136.

The difference bound: each position changes $d$ by $y - v$ where $|y - v| \le 9$. Over 18 positions, $|d| \le 162$. $\quad\square$

Editorial

Count integers 0 <= n < 10^18 where S(n) = S(137n). Approach: Digit DP processing digits from least to most significant. State: (carry, diff) where carry is from the 137n multiplication and diff = S(n) - S(137n) accumulated so far. We base case: after processing 18 digits. We then process positions 17 down to 0. Finally, this state will be reached from some (c_in, d_in) via digit y.

Pseudocode

dp[carry][diff_offset] where diff_offset = diff + 162
Base case: after processing 18 digits
Process positions 17 down to 0
This state will be reached from some (c_in, d_in) via digit y
Actually, iterate forward:
Forward formulation:

Complexity Analysis

• Time: $O(18 \times 137 \times 325 \times 10) = O(81{,}022{,}500) \approx 8.1 \times 10^7$.
• Space: $O(137 \times 325) = O(44{,}525)$ for the DP table.

Answer

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

int main() {
    // Count 0 <= n < 10^18 with S(n) = S(137*n)
    // Digit DP: process digits from least significant to most significant
    // State: (position, carry, diff) where
    //   carry = carry from 137*n multiplication
    //   diff = S(n) - S(137*n) accumulated so far

    const int DIGITS = 18;
    const int MAX_CARRY = 137; // max carry: floor((137*9 + 136)/10) = 136, so 0..136
    const int DIFF_OFFSET = 162; // diff ranges from -162 to 162
    const int DIFF_RANGE = 325;

    // dp[carry][diff+offset] = count of numbers
    // Process digit by digit from position 0 to DIGITS-1

    vector<vector<long long>> dp(MAX_CARRY, vector<long long>(DIFF_RANGE, 0));
    dp[0][DIFF_OFFSET] = 1; // carry=0, diff=0

    for (int pos = 0; pos < DIGITS; pos++) {
        vector<vector<long long>> ndp(MAX_CARRY, vector<long long>(DIFF_RANGE, 0));
        for (int carry = 0; carry < MAX_CARRY; carry++) {
            for (int di = 0; di < DIFF_RANGE; di++) {
                if (dp[carry][di] == 0) continue;
                long long cnt = dp[carry][di];
                for (int y = 0; y <= 9; y++) {
                    int val = 137 * y + carry;
                    int new_carry = val / 10;
                    int v = val % 10;
                    int new_di = di + (y - v);
                    if (new_di >= 0 && new_di < DIFF_RANGE && new_carry < MAX_CARRY) {
                        ndp[new_carry][new_di] += cnt;
                    }
                }
            }
        }
        dp = ndp;
    }

    // After processing all digits of n, the remaining carry c represents
    // additional upper digits of 137*n. Their digit sum S(c) must equal
    // the accumulated diff: diff = S(carry).
    auto digitSum = [](int x) {
        int s = 0;
        while (x > 0) { s += x % 10; x /= 10; }
        return s;
    };

    long long ans = 0;
    for (int carry = 0; carry < MAX_CARRY; carry++) {
        int ds = digitSum(carry);
        int di = DIFF_OFFSET + ds;
        if (di >= 0 && di < DIFF_RANGE) {
            ans += dp[carry][di];
        }
    }
    cout << ans << endl;

    return 0;
}

"""
Problem 290: Digital Signature

Count integers 0 <= n < 10^18 where S(n) = S(137*n).

Approach: Digit DP processing digits from least to most significant.
State: (carry, diff) where carry is from the 137*n multiplication and
diff = S(n) - S(137n) accumulated so far.
"""

def solve():
    DIGITS = 18
    MAX_CARRY = 137  # 0..136
    DIFF_OFFSET = 162
    DIFF_RANGE = 325

    # dp[carry][diff+offset] = count
    dp = [[0] * DIFF_RANGE for _ in range(MAX_CARRY)]
    dp[0][DIFF_OFFSET] = 1

    for pos in range(DIGITS):
        ndp = [[0] * DIFF_RANGE for _ in range(MAX_CARRY)]
        for carry in range(MAX_CARRY):
            for di in range(DIFF_RANGE):
                cnt = dp[carry][di]
                if cnt == 0:
                    continue
                for y in range(10):
                    val = 137 * y + carry
                    new_carry = val // 10
                    v = val % 10
                    new_di = di + (y - v)
                    if 0 <= new_di < DIFF_RANGE and new_carry < MAX_CARRY:
                        ndp[new_carry][new_di] += cnt
        dp = ndp

    # After processing all digits of n, remaining carry c gives additional
    # upper digits of 137*n. We need diff = digit_sum(carry).
    def digit_sum(x):
        s = 0
        while x > 0:
            s += x % 10
            x //= 10
        return s

    result = 0
    for carry in range(MAX_CARRY):
        ds = digit_sum(carry)
        di = DIFF_OFFSET + ds
        if 0 <= di < DIFF_RANGE:
            result += dp[carry][di]
    print(result)

if __name__ == "__main__":
    solve()

    # Optional visualization: distribution of digit sum differences