How many four digit numbers divisible by 29 have the sum of their digits 29?

How many four digit numbers divisible by $29$ have the sum of their digits $29$?

A way to do it would be to write $1000a+100b+10c+d=29m$ and $a+b+c+d=29$ and then form equations like $14a+13b+10c+d=29m'$ and eventually $4a + 3b – 9d = 29 (m'' – 9)$. Analysing this equation for integer solutions using the advantage we have $\to$ $29$ is a prime; will give the solutions, but is tedious work.

Are there better solutions?

• $13a+12b+9c=29m''$ is only $290,261,232$... – Takahiro Waki May 6 '17 at 13:46

If the sum of the digits of $n$ is $29$, then the number $n$ must be congruent to $2$ (modulo $9$). Since $29$ and $9$ are relatively prime, and their product is $261$, we need only consider numbers congruent to $29$ (modulo $261$). There are only about three dozen candidates between $1000$ and $9999$.

Furthermore, the average of the digits is $\frac{29}4>7$; no digit can be $1$, and only one digit can be below $6$. That means we can start our search at $2999$; the first candidate is $3161$, easily discarded, and we just repeatedly add $261$ until we get above $9999$.

$4 \times 9 = 36$, and we must end up with $29$ as a sum.

There are $7 \choose 4$ ways to reduce the sum from 36 to 29 over 4 digits.

Tedious = 35 cases.

$(a=4\land b=9\land c=8\land d=8\land m=172)\lor (a=7\land b=5\land c=9\land d=8\land m=262)\lor (a=7\land b=8\land c=5\land d=9\land m=271)\lor (a=9\land b=6\land c=8\land d=6\land m=334)\lor (a=9\land b=9\land c=4\land d=7\land m=343)$

So 5 numbers which are $4988,7598,7859,9686,9947$.

• How did your arrive at that answer – Apurv May 5 '17 at 9:02
• @Apurv computer check – Ahmad May 5 '17 at 9:10
• He is looking for a method using pencil and paper. – Andrew Woods May 5 '17 at 9:43