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.

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

share|improve this question

2 Answers 2

up vote 8 down vote accepted

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

share|improve this answer
    
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).

share|improve this answer

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.