The 3n+1 Problem & Beatty Sequences

08262014, 03:13 AM
Post: #1




The 3n+1 Problem & Beatty Sequences
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. <0ɸ0> Joe 

08262014, 09:45 PM
Post: #2




RE: The 3n+1 Problem & Beatty Sequences
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...


08282014, 07:03 PM
Post: #3




RE: The 3n+1 Problem & Beatty Sequences
(08262014 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 nonrepeating 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. <0ɸ0> Joe 

08282014, 08:45 PM
Post: #4




RE: The 3n+1 Problem & Beatty Sequences  
08282014, 09:15 PM
Post: #5




RE: The 3n+1 Problem & Beatty Sequences
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) 

10092014, 09:56 PM
(This post was last modified: 10092014 10:08 PM by Thomas Klemm.)
Post: #6




RE: The 3n+1 Problem & Beatty Sequences
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_{k1}}{\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 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)}pq<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 

10102014, 03:11 AM
(This post was last modified: 10112014 04:16 PM by Joe Horn.)
Post: #7




RE: The 3n+1 Problem & Beatty Sequences
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. <0ɸ0> Joe 

« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)