Jtdylktuy

I am trying to find the smallest number if we are given the sum of its digits. Suppose that sum of digits is 9 then it should be 9 instead of 18,36,63 and similarly if sum of digits is 11 then desired answer is 29 not 92 or any other number bigger than 29.I tried to write sum of all numbers upto 53 and got this but i am not able to come up with a general formula.
from 1 to 9 it is just 9.FROM 10 to 18 it is 19,29,39,...... and for 19(1+9) it is 199 that is increase by 100.
from 19 to 27 it is 199,299,399,499.... and for 28 it is 1999 that is increase by 1000.
from 29 to 36 it is 29999,39999,49999,..... for 37 it is 19999 (increse by 10000).
for 38 to 45 it is it is 29999,39999,49999,........999999 and for 46 it is 199999 (increased by 100000)

In our so-called positional numeration system, the digits get a weight that increases from right to left, following the powers of ten (units, tens, hundreds, thousands...).

So to minimize the number you will allocate the budget in priority to the positions with the smallest weight.

This is why the solution is by putting as many $9$s to the right as you can, preceded by the remainder of the budget. There will be $btext{ div }9$ nines and the digit $bbmod9$, forming the number

$$(bbmod 9)10^{btext{ div }9}+10^{btext{ div }9}-1=(bbmod 9+1)10^{btext{ div }9}-1.$$

If on the opposite you want to maximize the sum, then you must forbid the digit $0$ (because you could insert them "for free"), and the solution is formed by a maximum of $9$s followed by the remainder, i.e.

$$10,(10^{btext{ div }9}-1)+bbmod9$$ unless $bbmod9=0$, then

$$10^{btext{ div }9}-1.$$

Let's build the output number starting from the last (i.e. the lowest) digit.

As long as the input number is bigger than 9, it is the best way to set the current digit of the output number to 9 than to any other value.
If you, hypothetically, set it to a value lower than 9, you would have to set another digit in the front to a higher value. So, your whole number would be higher.

If the input number is smaller than 9, just add it to the front of the output number.

i = 0

while(input > 9) {

    // Set i-th digit of output to 9

    output.set(i, 9)

    input = input - 9

    i = i+1

}



// Finally set the front digit of output to the rest of input

output.set(i, input)

In your example with 29, there would be one while-loop. The last digit of output would be set to 9. Then, the front digit of output would be set to 2.

Mathematically:

$$
text{output} = x99dots9
$$

where you have $log_9(text{input})$ $9$'s behind the $x$ and $x = text{input} - log_9(text{output})$.

I have found a general formula to find the smallest number whose digits sum up to S and has M digits. Here is a python implementation of it:

def bla(M,S):

    n=(S+7)//9

    sl=9*n -7

    c=10**(n-1)

    b=10**(M-1)

    p=int((2+S-sl)*c -1)

    return p+b

If you have any doubts please comment below.