Digit Sum Numbers

A number where one digit is the sum of the other digits is called a digit sum number or DS-number for short. For example, $352$, $3003$ and $32812$ are DS-numbers.

We define $S(n)$ to be the sum of all DS-numbers of $n$ digits or less.

You are given $S(3) = 63270$ and $S(7) = 85499991450$.

Find $S(2020)$. Give your answer modulo $10^{16}$.

The problem statement gives us a special set of numbers named DS-numbers and asks for a sum of all these numbers upto a certain number of digits, modulo $10^{16}$. Given the large input number, our approach lies in dynamic programming.

First, notice that the leftmost digit should always be zero, as it must be the sum of all the following digits.

Let’s denote $dp[i][j]$ as the number of DS-numbers of length $i$ where the sum of the digits is $j$. Then it’s clear that $dp[1][0] = 1$ (only the number 0), and $dp[i][j] = 0$ for $j < i - 1$, since the minimum sum is when we have $i - 1$ digits 1 and the remaining digit 0. For larger $j$, use the following recurrence relation: $dp[i][j] = \sum_{k=0}^{9} dp[i-1][j-k]$, for $0 \leq k \leq j$. Then, to count the sum of numbers directly, introduce $dp2[i][j]$, the sum of all DS-numbers of length $i$ with the digit sum $j$. Its recurrence relation is: $dp2[i][j] = \sum_{k=0}^{9} dp2[i-1][j-k] + k*10^{i-1}*dp[i-1][j-k]$, for $0 \leq k \leq j$. So, we can precalculate these dp-tables for $i \leq 2020$, $j \leq 20000$, and then use the formula: $S(n) = \sum_{i=1}^{n} \sum_{j=i-1}^{n*9} dp2[i][j]$, as the DS-numbers with fewer digits are also counted, when considering the numbers with larger number of digits. This solution works in $O(n^2)$ time and memory and can be implemented in Python like the following: ```python MOD = 10**16 dp = [[0]*20201 for _ in range(2021)] dp2 = [[0]*20201 for _ in range(2021)] dp[0][0] = 1 for i in range(1, 2021): for j in range(20001): for k in range(min(j+1, 10)): dp[i][j] += dp[i-1][j-k] dp[i][j] %= MOD dp2[i][j] += dp2[i-1][j-k] dp2[i][j] %= MOD dp2[i][j] += k*pow(10, i-1, MOD)*dp[i-1][j-k] dp2[i][j] %= MOD result = 0 for i in range(1, 2021): for j in range(i-1, 20001): result += dp2[i][j] result %= MOD print(result) ``` When you run this script, you get the answer for $S(2020)$ modulo $10^{16}$.

More Answers: