2
$\begingroup$

How can we compute the least Harshad number with given sum of decimal digits $S$? Harshad number in base 10 is any number divisible by sum of its decimal digits.

I think that some kind of dynamic programming should be used. But which one?

Thanks in advance for any ideas.

$\endgroup$
2
$\begingroup$

You solve the following more general problem: find the least number $N$ with sum of digits $T$ such that $N \mod M = R$ (the inputs are $M,T,R$). Initially, $T=M=S$ and $R=0$. Now you go over all possible least significant digits $b$. Using the formula $$ (10n+b) \pmod{M} = 10(n \pmod{M}) + (b \pmod{M}), $$ you reduce the problem to a smaller one, and so on.

The total amount of work appears to be $O(S^2)$, since the number of possible values for $T$ and $R$ is $O(S^2)$. Care needs to be taken with zero digits, however, a detail which I leave you to ponder.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.