2
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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).

$\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.