Properties of a digit sum and modulo 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
 A: 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
A: 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\}$.

