# How to “efficiently” compute the number of solution of $25x= 5y+8z$ such that $x,y,z \in [0,9]$ and $x,y,z \in \mathbb{W}$?

The mother problem:

Find the sum of all $3$ digit numbers which are equal to $25$ times the sum of their digits.

So we can write: \begin{align} 100x+10y+z &= 25 \times (x+y+z) \\ &= 25x + 25y+25z \end{align}

$$\Rightarrow 25x= 5y+8z \quad ---(1)$$

Thus the question reduces to finding all possible solution of $(1)$ with the constraints of $x,y,z \in [0,9]$,now it may not be too hard using a brute force aproach (but however tedious) to find that only $3$ pairs of $(x,y,z)$ will be the required solution but I am looking for a smarter approach for this computation,any ideas?

Also if somebody knows any alternative but efficient solution for the actual problem, I will appreciate it as an answer.

-

Equation (1) $\Leftrightarrow y = 5x-\frac{8z}{5}$
Since $y$ $\in [0,9]$ and $5x$ is a natural number,
$\Rightarrow \frac{8z}{5}$ is also a natural number, $\Rightarrow z$ must be a multiple of $5$.
Since z $\in[0,9]$, $\Rightarrow z = 0 || z = 5$

For $z = 0$, $y = 5x \Rightarrow x=1$, $y=5$

For $z = 5$, $\Rightarrow y = 5x - 8$, (2)
since $0 \leq y \leq 9$
(2) $\Leftrightarrow 8/5 \leq x \leq 17/5$
$\Leftrightarrow 1.4 \leq x \leq 3.4$
$\Rightarrow x =2,3 \Rightarrow y =2,7$

-
+1 and accepted,cute trick! :-) – Quixotic Aug 28 '11 at 16:01

You know immediately that a multiple of $25$ ends in $00,25,50$, or $75$, so $5y+8z$ is $0$, $50$, $25$, or $75$, and $x$ is $0$, $2$, $1$, or $3$, of which the first is impossible for a $3$-digit number.

-
But how ending with $00,25,50$ and $75$ implies $5y+8z$ is $0, 50, 25$ or $75$? Is it because $x<10$? – Quixotic Aug 28 '11 at 6:48
It has nothing to do with $x$. The last two digits of the number are $y$ and $z$, so you just calculate $5y+8z$: in the first case $y=z=0$, in the second, $y=2,z=5$, in the third $y=5,z=0$, and in the fourth $y=7,z=5$. – Brian M. Scott Aug 28 '11 at 8:33

From your simplified question you can see that $$8z = 25x-5y = 5 \times (5x -y)$$

Thus $z$ must be a multiple of 5 (since 8 and 5 are relatively prime) and so $z$ is either 0 or 5.

From here you get two simpler equations on division by 5, when $z=0$ we have $y=5x$ and when $z=5$ it is $y= 5x - 8$. Both of these can then be solved to give the four solutions:

$z=0$, $x=0$, $y=0$, the number is $0$, the trivial answer, but still an answer, technically, giving a fourth answer...

$z=0$, $x=1$, $y=5$, the number is $150 = 6 \times 25$

$z=5$, $x=2$, $y=2$, the number is $225 = 9 \times 25$

$z=5$, $x=3$, $y=7$, the number is $375 = 15 \times 25$

-

From the "postage stamp" problem, it follows that every number larger than :

$(5-1)(8-1)=28$ can be written as a (non-negative) linear combination of 5,8

; writing 5 consecutive numbers is a good-enough proof:

$4\cdot5+8=28; 3\cdot 8+5=29; 6\cdot5=30; 2\cdot8+3\cdot5=31;8\cdot4=32$, and then you can get any

number larger than 32 by adding multiples of $5$ to any of the 5 given; you can use

too the obvious fact thaat $5\cdot5=25$, to get a solution for x=0,1,...,9. Note that

here you could, if you wanted, generalize to any coefficient of x.

-