How many numbers between $1$ and $123456789$ have digital root equal to $5$?

$S(n)$ is a function. If applied to a number, it sums up all the digits until a single digit is obtained. e.g.: $S(919)=S(9+1+9)=S(19)=S(1+9)=S(10)=1+0=1$

Find how many such numbers exists if $1\lt n\lt 123456789$ and $S(n)=5$.

The function $S$ gives the remainder when dividing the number by $9$, except that it gives $9$ instead of $0$ when the number is divisible by $9$; this is also known as the digital root of $n$. So your question is exactly the same as asking how many numbers of the form $9k+5$ are there strictly between $1$ and $123456789$.

• thanks for giving such a good imformation. so its solution is 13717420 – rohit Aug 7 '11 at 19:02

I think this is relevant. It's complementary to Arturo's (excellent and arguably sufficient) answer.

Have you ever heard of the arithmetic technique Casting Out Nines? It's the old gradeschool (though I still use it now) technique to check your sums, differences, products, and quotients by finding the 'digit sums' aka digital roots and making sure they are the same for the question and answer. For example,

\begin{align} \quad \; 111 & \qquad (1 + 1 + 1 = 3) \\ + \; 234 & \qquad (2 + 3 + 4 = 9 \to 0) \\ = \; 345 & \qquad (3 + 4 + 5 = 12 \to 3) \end{align}

Since both have digital sum 3, we have additional suspicion that the answer is correct. This is the exact idea that needs to be employed here, and that Arturo used.

Why does it work? It's entirely because we use base 10 arithmetic. So taking the digit sum of 1 = the digit sum of 10 (9 + 1) = the digit sum of 100 (99 + 1), i.e. modding by 9 doesn't change the digit sum. If we were in base 16, we might cast out 15s. And that would be annoying, so thank goodness. The base 2 case, though, doesn't help too much (casting out 1's... not a good idea).