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.

I'm wondering if for every integer $N$, can we always find a positive number $q$ such that, it is dividable by $N$ and the sum of its digits is $N$?
 A: 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$.
A: 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.
