Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer
    
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
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 ;-) –  marlu Mar 24 '12 at 21:00
add comment

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.

share|improve this answer
1  
How you bound size of $A$ to $10^N$? –  Saeed Mar 24 '12 at 17:57
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.