Can someone give me a clue on how am I going to prove that this pattern is true or not as I deal with repeated division by 2? I tried dividing 360 by 2 repeatedly, eventually the digits of the result, when added repeatedly, always result to 9 for example:
\begin{align*}
360 ÷ 2 &= 180 \text{, and } 1 + 8 + 0 = 9\\
180 ÷ 2 &= 90 \text{, and } 9 + 0 = 9\\
90 ÷ 2 &= 45 \text{, and } 4 + 5 = 9\\
45 ÷ 2 &= 22.5 \text{, and } 2 + 2 + 5 = 9\\
22.5 ÷ 2 &= 11.25 \text{, and } 1 + 1 + 2 + 5 = 9\\
11.25 ÷ 2 &= 5.625 \text{, and } 5 + 6 + 2 + 5 = 18 \text{, and } 1 + 8 = 9\\
5.625 ÷ 2 &= 2.8125 \text{, and } 2 + 8 + 1 + 2 + 5 = 18 \text{, and } 1 + 8 = 9
\end{align*}
As I continue this pattern I found no error (but not so sure)… please any idea would be of great help!
Best Answer
Define the digit sum of the positive integer $n$ as the sum $d(n)$ of its digits. The reduced digit sum $d^*(n)$ is obtained by iterating the computation of the digit sum. For instance $$ n=17254,\quad d(n)=1+7+2+5+4=19, \quad d(d(n))=1+9=10, \quad d(d(d(n)))=1+0=1=d^*(n) $$ Note that $d(n)\le n$, equality holding if and only if $1\le n\le 9$. Also, $1\le d^*(n)\le 9$, because the process stops only when the digit sum obtained is a one-digit number.
The main point is that $n-d(n)$ is divisible by $9$: indeed, if $$ n=a_0+a_1\cdot10+a_2\cdot10^2+\dots+a_n\cdot10^n, $$ then $$ n-d(n)=a_0(1-1)+a_1(10-1)+a_2(10^2-1)+\dots+a_n(10^n-1) $$ and each factor $10^k-1$ is divisible by $9$. This extends to the reduced digit sum, because we can write (in the example above) $$ n-d^*(n)=\bigl(n-d(n)\bigr)+\bigl(d(n)-d(d(n))\bigr)+\bigl(d(d(n))-d(d(d(n)))\bigr) $$ and each parenthesized term is divisible by $9$. This works the same when a different number of steps is necessary.
Since the only one-digit number divisible by $9$ is $9$ itself, we can conclude that
Since $360$ is divisible by $9$, its reduced digit sum is $9$; the same happenso for $180$ and so on.
When you divide an even integer $n$ by $2$, the quotient is divisible by $9$ if and only if $n$ is divisible by $9$.
What if the integer $n$ is odd? Well, the digits sum of $10n$ is the same as the digit sum of $n$. So what you are actually doing when arriving at $45$ is actually \begin{align} &45 \xrightarrow{\cdot10} 450 \xrightarrow{/2} 225 && d^*(225)=9 \\ &225 \xrightarrow{\cdot10} 2250 \xrightarrow{/2} 1225 && d^*(1225)=9 \end{align} and so on. Note that the first step can also be stated as $$ 45 \xrightarrow{\cdot5} 225 $$
Under these operations divisibility by $9$ is preserved, because you divide by $2$ or multiply by $5$.