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

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.

• Isn't the answer always $N$? – Yuval Filmus Dec 2 '18 at 0:17

3 Answers

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.

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.

• I have seen homework questions in my time that were made to look difficult while being totally trivial, to check whether the student's brain actually understands the question. This might be one of those. More interesting would be: Given N and k, find the smallest x divisible by N, with the digit sum equal to k. – gnasher729 Dec 2 '18 at 12:03
• I'm so sorry. There was a lot of mistakes. For n = 10 result is 190. It is oeis.org/A002998, but I still cant solve it – Gleb Dec 2 '18 at 15:04
• The first step in solving a question is ascertaining what the question exactly is... – Yuval Filmus Dec 2 '18 at 17:17

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.