0
$\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 $$ \underbrace { S \bigg( S \Big( S \big( \dots S } _ { k \text { times} } ( n ) \big) \dots \Big) \bigg) $$ is a single digit number.

Any help with this proof will be appreciable.

$\endgroup$
2
  • $\begingroup$ This process of taking repeated sums of digits is often called "casting out nines". It results in a single digit which is congruent to $n$ modulo $9$. Perhaps you've already heard of this in that context? There have been previous questions about it on the site. $\endgroup$ Commented May 11, 2021 at 1:37
  • 2
    $\begingroup$ Does this answer your question? A pedagogical proof that 9's can be ignored when calculating digital roots $\endgroup$ Commented May 11, 2021 at 1:43

2 Answers 2

Reset to default
3
$\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$
3
$\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$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.