# Find smallest number which is divisible to $N$ and its digits sums to $N$

Someone asked this question in SO:

$1\le N\le 1000$

How to find the minimal positive number, that is divisible by N, and its digit sum should be equal to N.

But I wonder if we don't have a limit for $N$, always we can find a positive number $q$ which is dividable by $N$, and its digits sums to $N$?

-
N is not defined? –  dato datuashvili Mar 24 '12 at 13:15
You dont need a "limit" for N. Only things needed is that N is finite, then a correct program will still find the answer. –  FiniteA Mar 24 '12 at 13:48
@dato, N is positive integer. –  Saeed Mar 24 '12 at 16:32
@FiniteA, How you can prove your claim? you claim that you can write an algorithm such that works fine for any given (finite) $n$ but with finite step (like $n^n$), but you should prove this. –  Saeed Mar 24 '12 at 16:36
@ChristianBlatter, may be I didn't write it clear, Actually I'm not looking for minimal n, I say assume number $n$ is given, what is minimal number $q$ such that $q \text{ mod } n = 0 \text{ and sum of digits of q is n}$. actually for $1\le n \le 1000$ we can find $q$, I'm asking is this true for all $n \in N$ (is there exists such a $q$)? –  Saeed Mar 24 '12 at 19:24

For every $N$ there is a number $X$ such that $N$ divides $X$ and the sum of digits of $X$ equals $N$.

Proof: Write $N = RM$ where $M$ is coprime to $10$ and $R$ contains only the prime factors $2$ and $5$. Then, by Euler's theorem, $10^{\varphi(M)} \equiv 1 \pmod M$. Consider $X' := \sum_{i=1}^{N} 10^{i\varphi(M)}$. It is a sum of $N$ numbers each of which is congruent to $1$ modulo $M$, so $X' \equiv N\cdot 1 \equiv 0 \pmod M$. Furthermore, the decimal representation of $X'$ contains exactly $N$ ones, all other digits are $0$, so the sum of digits of $X'$ is $N$. Multiply $X'$ by a high power of ten to get a multiple of $R$, call the result $X$. Then $X$ is divisible by $M$ and $R$, hence by $N$, and it has the same digit sum as $X'$ which is $N$.

-
Thanks, actually this answers my question, but how we can find minimum $X$? May be I ask second question in new thread, but I'm wonder if there is a mathematical way, of-course by your proof, I can run dynamic programing and sure that I can find result for any $N$, but I think there is a mathematical and faster way. –  Saeed Mar 24 '12 at 20:31
Yes, the proof does not help in finding an efficient way to actually compute the minimum $X$. Of course you could just loop over all multiples of $N$ and check if there digit sum equals $N$. Then the above proof gives a rough upper bound: You have to check not more than $N^2 10^{N^2}$ numbers ;-) –  marlu Mar 24 '12 at 21:00

If 10 doesn't divise N we can define the set $A = \{(n=x_1x_2\cdots x_i0) : \sum\limits_{k} x_k = N\}$ wich is a set containing at least one solution (if it exists) of the problem above (in particular the minimum one). The size of $A$ can be brutaly bounded by $10^N$. It is easy to construct all elements in $A$ by an algorithm and then try them one by one. In the other case, we can easily reduce the problem to the first case.

Actualy, a good program will always find a solution (or not) in a finite number of steps.

The question of existence still resists to me.

-
How you bound size of $A$ to $10^N$? –  Saeed Mar 24 '12 at 17:57