# Convergence of Collatz sequences

I may be using the wrong terminology here, but please bear with me, I'm not a mathematician, just a hobbyist... ;-)

I noticed that for some pairs of numbers n and n+1, when you put them through the Collatz rule, sometimes they fall into step with each other. The rule - as I assume will be known - is: when n is even, divide by two, when n is odd, multiply by three and add 1. Repeat this until you get 1 as a result.

As an example: when you put the numbers 350 and 351 through this algorithm, they will have the same sequence after step 12. Like so:

350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, etc

351, 1054, 527, 1582, 791, 2374, 1187, 3562, 1781, 5344, 2672, 1336, 668, 334, etc

Other examples are: 242 and 243 (after only 5 steps), 1346 and 1347 (same), 237 and 238 (8 steps)

If the sequences converge it seems to happen after only a small number of steps.

Has any study been done on this phenomenom? Does anyone have a hint on where to start looking?

-
Interesting observation! –  André Nicolas May 25 '12 at 18:07
Jeff Lagarias has edited a book on the Collatz problem. It's a good place to start looking for nearly anything about that problem. –  Gerry Myerson May 27 '12 at 8:58
Boy, ask a silly question, get a sensible answer. Many thanks to Zander for your extensive reply to my query. Now... I'm off to try and understand it properly (as I said, I'm not a mathematician). Thank you! –  John Goverts May 27 '12 at 18:07
@John: Before you are off, you should upvote and accept Zander's answer if it is indeed useful to you. –  Asaf Karagila May 27 '12 at 20:42

I don't know if this has been studied, but I can partly explain it.

Write $f(n)$ for the Collatz rule. Consider the binary representation of $n$. If it ends in a 0-bit followed by exactly $t$ 1-bits with $t>1$, i.e. $n=a2^{t+1}+2^t-1$ with $a\ge 0$, then \begin{align} f(f(n-1)) & = f(a2^t+2^{t-1}-1) & = (3a+1)2^t+2^{t-1}-2 \\ f(f(n)) & = f((3a+1)2^{t+1}+2^t-2) & = (3a+1)2^t+2^{t-1}-1 \end{align} That is, $f(f(n))-1=f(f(n-1))$ and $f(f(n))$ ends in a 0-bit followed by exactly $(t-1)$ 1-bits.

If we write $\langle a,t \rangle$ for $a2^{t+1}+2^t-1$ then we have the rule $f(f(\langle a,t \rangle)) = \langle 3a+1,t-1 \rangle$ when $t>1$. Note that this changes the parity of both parts $a\to 3a+1$ and $t\to t-1$. Using this notation your example starting with 351 goes: $$351=\langle 5,5 \rangle \to 527=\langle 16,4 \rangle \to \langle 49,3 \rangle \to \langle 148,2 \rangle \to \langle 445,1 \rangle = 1781$$ where each arrow is applying $f$ twice.

Finally, if $n=8k+5$ then \begin{align} f(f(f(n-1))) & = f(2k+1) & = 6k+4 \\ f(f(f(n))) & = f(f(24k+16)) & = 6k+4 \end{align} so the sequences starting with $n$ and $n-1$ converge after 3 steps.

Now $n=8k+5=\langle 2k+1,1\rangle$, so if we start with $\langle a_1,t \rangle \to \langle a_2,t-1 \rangle \to \cdots$ and arrive at $\langle a_t,1 \rangle$ with $a_t$ odd, then the series converges after 3 more $f$-steps. Since the $a_i$ have alternating parity, this will happen if we start with any $a_1\equiv t \pmod{2}$.

In summary: For any $a\equiv t \pmod{2}$ with $a\ge 0$ and $t>1$ let $n=a2^{t+1}+2^t-1$. Then $f^c(n)=f^c(n-1)$ where $c=2(t-1)+3$ (and this is the smallest value of $c$ for which they match).

This is sufficient to generate examples of converging sequences. e.g. let $a=1001,t=3$ then $n=16023$ and the sequences go: $$\begin{array}{llll} 16022,8011, & 24034, 12017, & 36052, 18026, 9013, & 27040,\ldots \\ 16023,48070, & 24035, 72106, & 36053, 108160, 54080, & 27040,\ldots \end{array}$$

However, there are other possibilities, as your 237,238 example shows. That particular case can be explained by observing that if $n=4k+2$ then $f^3(n)=3k+2=f^3(n-1)+1$. Here $f^3(238)=179=\langle 22,2\rangle$. In general we can get to $\langle 3m+1,2 \rangle = f^3(32m+14)$. You should be able to generate other rules like this by trying to solve $f^c(n)=f^c(n-1)+1$ for small $c$.

-

I've just seen something interesting that Zander has more or less explained. For every odd number m between 17 and 99, excluding 31, if:

m $\equiv 13 \pmod{8}$ , then $f^3(m)= f^3(m-1)$

m $\equiv 19 \pmod{16}$ , then $f^5(m)= f^5(m-1)$

m $\equiv 23 \pmod{32}$ , then $f^7(m)= f^7(m-1)$

m $\equiv 15 \pmod{64}$ , then $f^9(m)= f^9(m-1)$

m $\equiv 95 \pmod{128}$ , then $f^{11}(m)= f^{11}(m-1)$

m $\equiv 63 \pmod{256}$ , then $f^{13}(m)= f^{13}(m-1)$

m $\equiv 27 \pmod{16}$ or $\equiv 39 \pmod{32}$ or $\equiv 47 \pmod{64}$ then $f^2(m)= f^2(m-1)+1$

else $m \equiv 17 \pmod{8}$ , and $f^2(m) +2 = f^2(m+1)$

-