# Repeatedly summing the digits of a number

Take an arbitrary number - for the sake of an example, I'll use 392. If we add the digits, we get 3 + 9 + 2 = 14, and then add those digits to get 5 (keep adding the digits of each result until it reduces to a single-digit number).

Compare that to this method: let q and r be the quotient and remainder of the number with respect to 10. Take q+r, and repeat with that new result until it reduces to a single digit number. So, for 392, we do 39+2 = 41, and 4+1 = 5.

In this case, the two methods end up with the same result. I haven't been able to find any counter examples. Is this guaranteed to happen?

• Since no one has mentioned this (yet), I thought I'd mention that the end result is called the digital root of the number. The notion, if not the name, has been around for quite a while, as you can see by this google-books search for "sum of digits" that is restricted to 19th century results. – Dave L. Renfro Jan 28 '14 at 15:49
• I’m showing my age, but when I was a boy, the method of “casting out nines” was routinely taught to elementary-school students. It’s an efficient way of finding the least residue modulo $9$, useful for making a (partial) check on integer calculations, since $\overline{a+b}=\bar a+\bar b$ (and similarly for subtraction and multiplication), where the bar refers to the result of the process you describe. – Lubin Jan 29 '14 at 16:06

For both operations (add all digits or replace $10q+r$ with $q+r$), the result of the operation has the same remainder when dividing by $9$ as the original number (for the digit sum this is a well-known arithmetic "trick", for the othr operation note that $(10q+r)-(q+r)=9q$). Therefore, by starting with $n$ and repeating either of the operations until the result is single-digit (which is guaranteed to happen), we obtain a result $m$ with $m\equiv n\pmod{10}$ and $0\le m\le 9$. Note that neither of the two operations produces $0$ unless its input is $0$. Therefore, if $n>0$, we will in fact have $1\le m\le 9$, which then together with the modulo 9 condition determines $m$ uniquely.

Yes. Writing your number as $n=\sum_{k=0}^N a_k 10^k$ where $0\leq a_k\leq 9$ are the digits. The first sum you compute is $n'=\sum_{k=1}^{N}a_k 10^{k-1}+a_0$.

The sum of the digits of $n$ is $\sum_{k=0}^N a_k$.

• If $a_0+a_1\leq9$, the sum of digits of $n'$ is $\sum_{k=1}^N a_k+a_0$, which is the same as the sum of the digits of $n$.

• If $a_0+a_1\geq 10$, then the last digit of $n'$ is $a'_0=a_0+a_1-10$ and the second to last digit is

1. $a'_1=a_2+1$ if $a_2\leq 8$
2. $a'_1=0$ if $a_2=9$.

In the case 1. ($a'_1\leq 8$), the sum of the digits of $n'$ is $\sum_{k=3}^N a_k+(a_2+1)+(a_0+a_1-1)$, it is again the sum of the digits of $n$.

In the case 2., the same procedure is repeated and the sum of the digits is again the same as for $n$.

So to conclude, we observe that when we do this procedure on a number (dividing by 10 and adding the quotient and the rest), the sum of the digits remains constant and equal to the sum of the digits of $n$, which proves that your guess is true.

Both are ways of reducing a positive integer modulo $9$ to obtain its unique least positive congruent rep in the interval $[1,9]$. By induction, the methods terminate with this value since each recursive step replaces any input $\,m>9\,$ by a smaller positive integer $n< m$ with $\,n\equiv m\pmod 9.\,$ Indeed, if $\,m>9\,$ then each method replaces one or more terms $10^i$ with the congruent value $1$, therefore descreases its input. Any such positive decreasing reduction algorithm will suffice to compute the (unique) least congruent representative, i.e. to reduce the input to normal form. We are free to perform such modular reductions in any convenient order, as long as the reductions preserve congruence and are (eventually) always decreasing. Such techniques are ubiquitous in modular arithmetic calculations (and, more generally, in normal-form rewrite rule calculations).