Algorithm to find smallest number divisible by N with sum of digits as N

Question

Problem:

Given $N$, find the smallest number divisible by $N$ whose sum of digits is equal $N$.

For example:

• $n = 1$, answer is $1$
• $n = 10$, answer is $190$

There is some dynamic programming algorithm, but I can't find it. It is sequence https://oeis.org/A002998.

Answer 1

Here is some Python code that solves this problem:

def niven(s, base=10):
    # if s < base:
    #     return s
    best = dict()
    best[(0, 0)] = 0
    new_candidates = dict()
    new_candidates[(0, 0)] = 0

    target_key = (s, 0)
    dc = 0
    while (True):
        dc += 1
        candidates = new_candidates
        new_candidates = dict()
        for ((ds, r), v) in candidates.items():
            vhi = v * base
            rhi = r * base
            for d in range(0, base):
                nv = vhi + d
                nds = ds + d
                nr = (rhi + d) % s
                nkey = (nds, nr)
                if nkey not in best or nv < best[nkey]:
                    best[nkey] = nv
                    new_candidates[nkey] = nv
        if target_key in best:
            return best[target_key]


for i in range(1, 20):
    print "%d => %s" % (i, str(niven(i)))

The logic behind this code is following:

For a fixed sum s the dictionary best contains the best solution for a more general problem: given digits sum ds and reminder r what is the minimal number with that sum of digits and that reminder modulo s? Obviously the solution for our problem is the record in that dictionary for a key (s,0).

So now the question is how to fill the dictionary? The algorithm is based on a simple formula for calculating reminder for a number with a known last digit d:

(10*v + d) mod 10 = (10*(v mod 10) + d) mod 10

In other words, the best solution for some key (ds, r) should be based on the best solution for a smaller number with a last digit added for some of the possible last digits

best(ds,r) = min(for d in [0..9] of d + 10 * best(ds-d, (r-d) mod 10) if ds > d))

which is exactly a dynamic programming problem. The code above fills the best dictionary starting from an obvious solution best(0,0) = 0. It stops after it has processed all the solutions of dc digits if the best[(s,0)] is filled now. This works because obviously any number of dc+1 digits is bigger than any number of dc digits.

Answer 2

Assuming that "number" means "positive integer", every number divisible by $N$ must be at least $N$. Conversely, $N$ has the same digit sum as itself. Therefore the answer is simply $N$, as your two examples demonstrate.

Answer 3

Note that the question has changed: There is an answer for the trivial question "Find the smallest multiple of N which has the same digit sum as N". The more sensible question is "Find the smallest multiple of N which has the digit sum N". For example for N = 10, the first multiple of 10 with a digit sum 10 is 190 (1+9+0 = 10).

(It seems that SergGr's answer is much better... :-)

The solutions for 0 ≤ N ≤ 9 are trivial, so assume N ≥ 10.

Start with k = 0. Define d(x) = "sum of decimal digits of x". Replace k with the first integer k' > k with d(k') = N. If k' is a multiple of N then we are done. Otherwise replace k with the smallest multiple of N which is greater than k' and start all over.

How do we find k'? Starting with k' = k, if d(k') > N then add the number from 1 to 9 which makes the last digit 0. If still d(k') > N then add the number 10, 20, 30, ... 90 to make the last two digits 0, and so on until d(k') <= N. As long as d(k') < N add 1, or add 10 if the last digit is 9, or 100 if the last two digits are 99, and so on.