Jtdylktuy

I noticed that if you sequentially add integers together, or even multiply them, and then reduce the result, an interesting pattern emerges.

(+1) 1  >> 1

(+2) 3  >> 3

(+3) 6  >> 6

(+4) 10 >> 1

(+5) 15 >> 6

(+6) 21 >> 3

(+7) 28 >> 1

(+8) 36 >> 9

(+9) 45 >> 9

This pattern, 1, 3, 6, 1, 6, 3, 1, 9, 9, repeats itself without end. Obviously this is due at least in part to the fact that we use a base 10 number system.

1. Are there any other interesting patterns that I'm missing?




2. Is there a logical reason for this?

If you double the numbers, 1, 2, 4, 8, 16, 32, 64, etc, and then reduce them, you get a different pattern, 1, 2, 4, 8, 7, 5 that repeats itself endlessly.

The answer to all of these question lies in what actually happens when you "reduce" a number by repeatedly summing its digits. In particular, the following is true

Let $n$ be a positive integer. If $n$ is divisible by $9$, its reduction will be $9$. Otherwise, its reduction will be the remainder of $n$ when divided by $9$.

Here, for formal purposes, "remainder" means the number $0leq r<9$ such that you can write
$$n=9q+r$$
For instance, the remainder of $23$ divided by $9$ is $5$ since $9times 2 + 5 = 23$. Note that $2+3=5$ as well.

The basic thing to notice in order to prove this is that the difference between an integer $n$ and the sum of its digits $s$ is always a multiple of $9$. For instance, $23-(2+3)=18=9times 2$. You can prove this by looking at the expanded form of decimal representation; in particular if $n$ has decimal expansion $d_kd_{k-1}ldots d_1d_0$ for some sequence of digits $d_i$, we have
$$n=10^kd_k+10^{k-1}d_{k-1}+ldots+10^1cdot d_1 + 10^0cdot d_0.$$
Then, the sum of the digits is
$$s=d_k+d_{k-1}+ldots+d_1+d_0.$$
The difference between these two values is
$$n-s=(10^k-1)d_k+(10^{k-1}-1)d_{k-1}+ldots+(10^1-1)cdot d_1 + (10^0-1)cdot d_0.$$
However, note that $$10^k-1=underbrace{99ldots 99}_{ktext{ digits}}=9cdot underbrace{11ldots 11}_{ktext{ digits}}.$$
Thus, every term in the difference $n-s$ is $9$ times something, so the whole thing is $9$ times something - so $n-s$ is divisible by $9$.

You can repeat this logic as many times as necessary to see that if $r$ was the reduction of $n$, then $n-r$ is divisible by $9$ - but then you find that there are only actually $9$ positive single digits numbers - and $r$ is definitely one of them - so it's only a matter of checking that there is only one positive single digit number $r$ so that $n-r$ is a multiple of $9$.

Okay, so why does this help us? Well, it reveals another surprising fact:

Let $n$ and $n'$ be positive integers with reductions $r$ and $r'$ respectively. The reduction of $n+n'$ and $ncdot n'$ equal the reductions of $r+r'$ or $rcdot r'$ respectively.

If you want to prove this, you basically write $n=9q+r$ and $n'=9q+r'$ and then note that $n+n'=9(q+q')+(r+r')$ then $nn'=9(9qq'+qr'+q'r)+rr'$ and use the last theorem, which gets rid of all those multiples of $9$ being added, since they can't change the result.

The significance is that you get a multiplication table and addition table where, given the two reductions, you can look up the reduction of the sum and product without knowing the original two numbers. Those tables look like this:

This framework basically sets up the answer to your questions: the reductions of the doubling sequence is easiest to explain. To find that sequence, you start at $1$, then, using the table above, multiply that by $2$. You repeat that for a while - and eventually you get back to $1$. The sequence is bound to repeat from there, since you've entered a loop. Note that this method completely forgets about what the number your reducing was - it just cares about the reduction!

For the addition, note that as we add the integers together sequentially, we'll be adding reductions where we start at $1$, add $2$, and so on - until we add $9$. Then instead of adding $10$, we add its reduction of $1$, then instead of $11$ we add $2$ - and so on. So, we are adding an infinitely cycling sequence of $1,2,3,4,5,6,7,8,9$ instead of thinking about adding the integers up sequentially. However, we note that after we add $1+2+3+4+5+6+7+8+9$, we get $9$ - which has a special property; in the above table, we always have $9+r=r$. Thus, when we jump back to adding a reduction of $1$, we get back to a sum with reduction $1$ - and the cycle repeats.

In more generality, this sort of reasoning is known as modular arithmetic. There's a lot of interesting things that happen when one develops this theory further.