Take a Break - The Collatz Conjecture

Posted by: @ronbentley1

Hi all,

I thought I might offer to you a little diversion from your current toils and share with you the Collatz Conjecture – something to amuse and amaze family and friends, and a good party ‘trick’.  The only thing you might needs is pencil & paper or a calculator if mental maths is not your forte. If you already know about this conjecture then back to work, otherwise why not take a break.

The Collatz Conjecture is easily stated and understandable but, as yet, remains unproven by the mathematical community (I think there is a big prize if you can prove it)!  Anyway, the conjecture says:

Take any positive number, N, (a natural number) and keep applying the following rules until you reach 1:

1. If the N is odd, then multiply it by 3 and add 1 (this will always result in an even number), or
2. If N is even, then divide it by 2 (this may result in an even or odd number)

Continue to apply the above rules until the number converges to 1.

Whatever the number you start with the sequence will always converge to 1! Neat eh!

Example:

Let N be 23.  Then the Collatz sequence is:

23, 70, 35,106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1

Convergence occurs in 16 steps.

The sequences generated can’t be readily guessed from the start number - even low start numbers can generate long sequences and high numbers relatively short ones.

Try it out; grab a coffee, pencil & paper or a calculator and have a go.

If you wish to explore the Collatz conjecture a little further without doing the calculations yourself then the attached sketch (Arduino and ESP 32 friendly) will generate the Collatz sequence for any given starting number and uses the serial monitor for input and output (set at 115200 b). Some of the sequences are surprising!

If you switch to the serial plotter you can see the ‘shape’ or profile of a Collatz sequence in terms of its individual elements.

If you run several examples what do you notice about convergence? Yep, convergence will occur as soon as a generated number becomes a power of 2!  This will always happen at some point.  If you can prove this then you have proven the conjecture and it becomes a theorem! The prize awaits.

Have fun

Ron B

collatz.ino

 

 

One of my favourite Youtube channels is Veritasium and he covered this subject at 

The sketch will be something fun to take a break with, thanks Ron @ronbentley1

@zander

Thanks for the post and video link which others will, I am sure, find fascinating.

Yes, there is lots and lots of material on the net about this problem. I have been aware of it for many years and also its intractability, something that comes out very nicely in your video link.

If my post inspires readers to explore the conjecture further and more deeply then I would be delighted - there is much beauty and elegance to find in the conjecture for the interested.

Cheers

Ron B

Correction

In my post I said that convergence occurs as soon as a sequence produces a number that is a power of 2.

I should had been more accurate here. Convergence will occur when a sequence produces an even power of 2. That is when 3xN+1=2^(2n) where n= 1,2,3,etc

Proof is by induction if anyone interested

@ronbentley1

Posted by: @ronbentley1

Correction

In my post I said that convergence occurs as soon as a sequence produces a number that is a power of 2.

I should had been more accurate here. Convergence will occur when a sequence produces an even power of 2. That is when 3xN+1=2^(2n) where n= 1,2,3,etc

Proof is by induction if anyone interested

Now, lets solve Tesla's 3, 6, 9 😉

Cheers

@zander

Posted by: @zander

One of my favourite Youtube channels is Veritasium and he covered this subject at 

 

 

The sketch will be something fun to take a break with, thanks Ron @ronbentley1

You, me, and ~13,000,000 others 😉

However, he did cop a bit of mud on his face not long ago, called out by my other fav's EEVBLOG, ELECTROBOOM, etc... for this post: The Big Misconception About Electricity 😉

Cheers

@ronbentley1

Posted by: @ronbentley1

Correction

In my post I said that convergence occurs as soon as a sequence produces a number that is a power of 2.

I should had been more accurate here. Convergence will occur when a sequence produces an even power of 2. That is when 3xN+1=2^(2n) where n= 1,2,3,etc

Proof is by induction if anyone interested

BTW... if anyone of you like such puzzles, check out the following 

Oskar Puzzles

Cheers

@frogandtoad I saw that, but I haven't figured out who if either is right. It certainly is very different from what I learned over 60 years ago.

@zander

Posted by: @zander

@frogandtoad I saw that, but I haven't figured out who if either is right. It certainly is very different from what I learned over 60 years ago.

Well, I'm pretty sure that Veritasium was proven wrong... even his mentors told him that they thought he would be called out on the theory, if you watched it in full.

Nevertheless, he did a followup video to conceed somewhat, but I still like watching when I get a chance.

Likewise, Dave from EEVBLOG is an Aussie legend, and ElectroBoom is as entertaining as AvE 😉

Cheers

@frogandtoad I will give it another watch, so much of that was new so I likely missed some details.