2
$\begingroup$

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

  • 0
    @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$)?2012-03-24

2 Answers 2

3

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

  • 1
    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 ;-)2012-03-24
0

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.

  • 1
    How you bound size of $A$ to $10^N$?2012-03-24