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.