2
$\begingroup$

I was working on a computer program and came up with an intuitive idea that reduces the program module by a considerable length . The idea is intuitive but I never came up with a proof.

Claim : For a natural number n , let S(n) denote the sum of digits of n in its decimal expansion. Prove that there exists a natural number k , such that S(S(S(.......(n))...)) [S composed k times] is a single digit number.

Any help with this proof will be appreciable.

$\endgroup$
2
$\begingroup$

Well this is very easy to see, because $s(n)<n$ unless $n$ is a single digit number. So $s(s(n))>s(n)$ and so on, we get $s(s(...s(n))...)<...<s(s(n))<s(n)<n$ as long as $s(s(...s(n))...)$ is not a single digit integer. So if you compose that very many times (enough times), you will reach a single digit number.

To prove $s(n)<n$, simply use the base 10 expansion.

$\endgroup$
2
$\begingroup$

Suppose $n$ has $d$ digits. Then $S(n) \le 9 \, d \,$. For $d \ge 3, 9d \,$ will always have fewer than $d$ digits, i.e. if $n$ has three digits or more, then $S(n)$ will have fewer digits than $n \,$.

Thus the sequence $n, S(n), S(S(n)), S(S(S(n))), \ldots$ must reduce the number of digits at every step until one gets number with less than three digits, call it $N$.

If $N$ is a single-digit number, then we're done. If $N$ is a two-digit number, then $S(N) \le 18$, but then $S(S(N)) \le 9$, and again we're done.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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