The 3n+1 Problem & Beatty Sequences

[Joe Horn]

Some of you old timers might remember that the famous "3n+1 Problem" (aka the "Collatz Conjecture") was called "Ulam's Conjecture" in many issues of the PPC Journal back in the heyday of HP calculators.

By any wild chance, have any of you played with the 3n+1 Problem long enough to have noticed that the parity sequences of T(n) are identical to the finite differences of the Beatty Sequence based on log(3)/log(2)? Or have I discovered something new? I haven't seen it even after several months of searching, and even attempting to read some unreadable papers by one of the biggest experts on the 3n+1 Problem, Jeff Lagarias.

I'd get a wider audience at comp.sci.math and other places, of course, but I know that some of you have played with 3n+1 for many years, armed with programmable HP calculators, so I'm taking a chance that somebody here might have run across this identity already. Thanks in advance.

[Jim Horn]

No, nor do I understand your observation completely from the above description. But if that will be touched on in your HHC2014 presentation, I'll be taking careful notes! Great find...

[Joe Horn]

(08-26-2014 09:45 PM)Jim Horn Wrote:  No, nor do I understand your observation completely from the above description. But if that will be touched on in your HHC2014 presentation, I'll be taking careful notes! Great find...

Yes, it'll be the crux of my Hailstone Numbers talk at HHC 2014. Sorry for not explaining it more clearly here, but this margin is too small to contain the whole thing.

Sneak preview: Make a list of n*log(2)/log(3) where n increments by 1 from 1 to something big. Now replace all those numbers with their ceiling. Now subtract each from the number before it (the first finite difference; aka DeltaLIST in RPL). You'll get a list that starts like this:

{ 1 1 0 1 1 0 1 1 0 1 0 ... }

Exactly the same non-repeating pattern (no matter how far out you go) appears as the "parity sequence" (aka parity vector) obtained by iterating T(n) which is defined as: \begin{equation}T(n) =\begin{cases}\frac{3n+1}{2} & n\equiv 1 \, \big(mod \, 2\big)\\\frac{n}{2} & n \equiv 0 \, \big(mod \, 2\big)\end{cases}\end{equation}

But wait! There's more! Lots more. At HHC 2014.

[Curlytop]

(08-28-2014 07:03 PM)Joe Horn Wrote:  but this margin is too small to contain the whole thing.

I like it!

[Jim Horn]

Thank you! I figured much of that out from the Wikipedia references you supplied. What puzzles me is that the Beatty sequence is by definition endless, while the Collatz conjecture holds that the parity sequence for any finite integer is itself finite. So I don't see how you can get the finite difference of Beatty's sequence of log(3)/log(2) from the parity sequence of any number at all. Expanding log(3)/log(2) as a continued fraction gets me nowhere, and using the "n" that was the sequence of positive integers to feed the parity sequence didn't either.

Looking forward to Reno next month! (my further comments were written orthogonal to the margin and fell down)

[Thomas Klemm]

From Wikipedia 6.3 As a parity sequence I followed the footnote [19] to find a rather old paper:
Terras, Riho (1976), "A stopping time problem on the positive integers".

The theorem 1.1 (Remainder representation) provides a formula to calculate the last value in the modified Collatz sequence:

\[ T^kn=\lambda_k(n)n+\rho_k(n) \]

where \(\lambda_i(n)=\frac{3^{S_i(n)}}{2^i}\) and \(\rho_k=\frac{\lambda_k}{2}(\frac{X_0}{\lambda_1}+\frac{X_1}{\lambda_2}+\ldots+​\frac{X_{k-1}}{\lambda_k})\).
Don't let you confuse by the formula. The important thing is that \(\lambda_k(n)\) is a factor < 1 and \(\rho_k(n)\) is considered small. With a little handwaving I'd say that the factor is the result of the multiplication by 3 and division by 2 and the remainder keeps track of the occasional addition of 1.

In case of the example of your slides in the video \(i=10\) and \(S_i(n)=6\) thus \(\lambda_k(n)=\frac{3^6}{2^{10}}\approx 0.7119140625\).
I just calculated \(\lambda_k(n)n\) and dare to say that the approximation isn't bad:

Code:

507 1101101100 362 ≈ 360.940
347 1101110100 248 ≈ 247.034
923 1101111000 658 ≈ 657.097
583 1110101100 416 ≈ 415.046
423 1110110100 302 ≈ 301.140
999 1110111000 712 ≈ 711.202
975 1111001100 695 ≈ 694.116
815 1111010100 581 ≈ 580.210
367 1111011000 262 ≈ 261.272
735 1111100100 524 ≈ 523.257
287 1111101000 205 ≈ 204.319
575 1111110000 410 ≈ 409.351

This factor \(\lambda_k(n)\) must be < 1 of course. Thus we have \(\frac{3^p}{2^q}<1\Rightarrow 3^p<2^q\Rightarrow p\log(3)<q\log(2)\Rightarrow p\log(3)-q\log(2)<0\Rightarrow \frac{\log(3)}{\log(2)}p-q<0\). But that's exactly the value that you calculate by the method you described.

Cool that you figured that out by yourself. Don't be disappointed that it's already known. At least to me it was new and I enjoyed your video a lot.

Cheers
Thomas

[Joe Horn]

Thanks, Thomas! My brother Jim also sent me some other similar info. It's good to know that the whole topic has already been examined so deeply. I'm pretty sure that the proof of the Collatz Conjecture is in "The Book", and that it mentions these parity sequences somewhere along the way.

EDIT: The file that Jim sent me can be downloaded from HERE.