Properties of a digit sum and modulo

Question

I am trying to solve a computational problem. The problem is like this;

Let me define a number and show it as $s(n)$ that represents the smallest number, that has a digit sum of $n$. So $s(10) = 19 (1+9=10)$, $s(11) = 29$, $s(18) = 99$, $s(23) = 599$ etc.

Now I need to calculate the $s(n)$ for $n \geq 10^8$. In this case, one of the problems is storage. For instance,

$s(1000) =1999999999 99999999999999999999999 9999999999999999999999999999999999999999999 999999999999999999999999999999999999$

So It's hard for me to calculate $s(10^8)$ computationally, and the computer could not handle such large values. For this reason I want to only store the $k$, where $k = s(n)\mod(h)$. The main problem is that since $s(10^8)$ is so large, the computer cannot store it properly to calculate its $\mod (h)$ to find $k$.

I believe that in order to solve this problem we need some sort of relation between $s(n)$ values (i.e $s(n)$ and $s(n-1)$ etc.) or between $s(n)$ and $n$.

So that we can calculate its mod before storing that number. For instance (imagine that) if we had known $s(n-2) \mod (h)$ and $s(n-1) \mod (h)$, it would be much easier to calculate $s(n) \mod(h)$. So simply I need some realation between $s(n)$ values...Any ideas ?

The pattern that I have noticed between $n$ and $s(n)$ is something like this

s(n) = int(str(n % 9) + '9' * (n // 9)) for $n \geq 9$

(In python)

but this is not useful for $n \geq 10^6$ which is clear from the example I am given above. I need to insert mod in some places so that I can go up to $n \approx 10^8$ and more

Answer 1

The key observations that should allow you to accomplish your task are:

• A string of $k$ $9$s in a row is equal to the number $10^k-1$. Therefore a digit $d$ followed by a string of $k$ $9$s is equal to $(d+1)10^k-1$.
• Modular exponentiation will allow you to compute $10^k\pmod h$ extremely quickly, without storing any numbers larger than $\max\{h,k\}$.

Answer 2

Your pattern is essentially to put as many $9$s as possible on the right, and any remainder on the left.

• So if $f(n)=\lfloor n/9 \rfloor$ then you have $f(n)$ $9$s on the right, which is $10^{f(n)} -1$

• plus $n-9f(n)$ on the left, corresponding to $(n-9f(n)) \times 10^{f(n)}$

• making a total of $(n-9f(n)+1) \times 10^{f(n)}-1$, or if you prefer $$s(n) =(n-9\lfloor n/9 \rfloor+1) \times 10^{\lfloor n/9 \rfloor}-1$$

Since powers of $10$ are $1$ more than a multiple of $9$, giving you $1$ on the left, you can say for example that $$s(10^{18}) = 2 \times 10^{(10^{18}-1)/9}-1$$

For modulo $p$ powers when $p$ is prime, you can use Fermat's little theorem to speed up calculations