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.

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

$\endgroup$
5
  • $\begingroup$ N is not defined? $\endgroup$ Mar 24, 2012 at 13:15
  • $\begingroup$ You dont need a "limit" for N. Only things needed is that N is finite, then a correct program will still find the answer. $\endgroup$
    – FiniteA
    Mar 24, 2012 at 13:48
  • $\begingroup$ @dato, N is positive integer. $\endgroup$
    – Saeed
    Mar 24, 2012 at 16:32
  • $\begingroup$ @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. $\endgroup$
    – Saeed
    Mar 24, 2012 at 16:36
  • $\begingroup$ @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$)? $\endgroup$
    – Saeed
    Mar 24, 2012 at 19:24

2 Answers 2

3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Saeed
    Mar 24, 2012 at 20:31
  • 1
    $\begingroup$ 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 ;-) $\endgroup$
    – marlu
    Mar 24, 2012 at 21:00
0
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ How you bound size of $A$ to $10^N$? $\endgroup$
    – Saeed
    Mar 24, 2012 at 17:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .