Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
Interesting observation! –  André Nicolas May 25 '12 at 18:07
1  
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
1  
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
2  
@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

2 Answers 2

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$.

share|improve this answer

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)$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.