Harshad numbers with given sum

Question

By definition Harshad number for base $~10~$ is any number divisible by sum of its decimal digits. Wikipedia gives some information on such numbers but i still have some questions and unforunately i wasn't able to answer them myself.

So let $~s~$ be some positive integer.

a) Does there exist Harshad number with digit-sum $~s~$?

b) If so, how can we construct such number?

c) How can we construct smallest such number?

For example if $~s = 11~$ then one possible answer for question b) is $~1010101010101010101010~$ ($11$ ones) while the answer for question c) is $~209$.

Answer 1

This post only provides answers to a) and b).

---

To answer your question a), yes. We'll prove this by answering b), constructing a Harshad number with digit sum $n$.

First, we define $l(n)$ to be $n$ without its factors $2$ and $5$. Examples are: $l(23)=23$, $l(24)=3$, $l(25)=1$. If we can construct a number with digit sum $n$ that is divisible by $l(n)$, then surely we can make it divisible by $n$ by just adding enough $0$'s at the end (equivalent to multiplying it with $10$ repeatedly, so this wont change the fact that it is divisible by $l(n)$). Let $A$ be a set of $n$ non-negative integers, that is, $A\subseteq\mathbb{N}_0$ and $|A|=n$. Now the number

$$\xi=\sum_{a\in A}10^a$$

has digit sum $n$, and this doesn't depend on the numbers in $a$. For it to be divisible by $l(n)$, we'd need

$$\xi=\sum_{a\in A}10^a\equiv 0\mod l(n)$$

and since $10^{\phi(l(n))}\equiv1\mod l(n)$ (note that we use $\gcd(10,l(n))=1$ here), we can choose

$$A=\{0\cdot\phi(l(n)),1\cdot\phi(l(n)),2\cdot\phi(l(n)),\cdots,(n-1)\cdot\phi(l(n))\}$$

so that we get (all equivalences are $\mod l(n)$): \begin{align} \xi&\equiv\sum_{a\in A}10^a\\ &\equiv\sum_{k=0}^{n-1}10^{k\cdot\phi(l(n))}\\ &\equiv\sum_{k=0}^{n-1}\left(10^{\phi(l(n))}\right)^{k}\\ &\equiv\sum_{k=0}^{n-1}1^{k}\\ &\equiv\sum_{k=0}^{n-1}1\\ &\equiv n\\ &\equiv 0\mod l(n) \end{align} where the last, $n\equiv0\mod l(n)$, holds since $l(n)\mid n$, because $l(n)$ has the same factors as $n$ and maybe a little less, but never more. Now we can append enough zeroes at the end so that it is not only divisible by $l(n)$, but also by $n$. To get back to your example $n=11$, we get $l(11)=11$, and $\phi(l(n))=\phi(11)=10$, so we get $A=\{0,10,20,30,\cdots,100\}$, arriving at the number

10000000001000000000100000000010000000001000000000100000000010000000001000000000100000000010000000001

and we don't need to append zeroes because $11$ didn't contain any factors $2$ or $5$. This construction method proves your question b).