Notifications
Clear all

Take a Break - The Collatz Conjecture

10 Posts
3 Users
11 Likes
218 Views
ron bentley
(@ronbentley1)
Reputable Member
Joined: 9 months ago
Posts: 328
Topic starter  

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

 

 

Ron Bentley
Creativity is an input to innovation and change is the output from innovation. Braden Kelley
A computer is a machine for constructing mappings from input to output. Michael Kirby
Through great input you get great output. RZA
Gauss is great but Euler rocks!!


   
Inq and THRandell reacted
Quote
Ron
 Ron
(@zander)
Famed Member
Joined: 2 years ago
Posts: 3403
 
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

 

 

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

 

 

"Don't tell people how to do things. Tell them what to do and let them surprise you with their results.” - G.S. Patton, Gen. USA
"Never wrestle with a pig....the pig loves it and you end up covered in mud..." anon


   
ron bentley reacted
ReplyQuote
ron bentley
(@ronbentley1)
Reputable Member
Joined: 9 months ago
Posts: 328
Topic starter  

@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

Ron Bentley
Creativity is an input to innovation and change is the output from innovation. Braden Kelley
A computer is a machine for constructing mappings from input to output. Michael Kirby
Through great input you get great output. RZA
Gauss is great but Euler rocks!!


   
ReplyQuote
ron bentley
(@ronbentley1)
Reputable Member
Joined: 9 months ago
Posts: 328
Topic starter  

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

 

 

 

Ron Bentley
Creativity is an input to innovation and change is the output from innovation. Braden Kelley
A computer is a machine for constructing mappings from input to output. Michael Kirby
Through great input you get great output. RZA
Gauss is great but Euler rocks!!


   
ReplyQuote
frogandtoad
(@frogandtoad)
Noble Member
Joined: 3 years ago
Posts: 1476
 

@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


   
ron bentley reacted
ReplyQuote
frogandtoad
(@frogandtoad)
Noble Member
Joined: 3 years ago
Posts: 1476
 

@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


   
ron bentley reacted
ReplyQuote
frogandtoad
(@frogandtoad)
Noble Member
Joined: 3 years ago
Posts: 1476
 

@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


   
ron bentley reacted
ReplyQuote
Ron
 Ron
(@zander)
Famed Member
Joined: 2 years ago
Posts: 3403
 

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

"Don't tell people how to do things. Tell them what to do and let them surprise you with their results.” - G.S. Patton, Gen. USA
"Never wrestle with a pig....the pig loves it and you end up covered in mud..." anon


   
ReplyQuote
frogandtoad
(@frogandtoad)
Noble Member
Joined: 3 years ago
Posts: 1476
 

@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


   
ron bentley reacted
ReplyQuote
Ron
 Ron
(@zander)
Famed Member
Joined: 2 years ago
Posts: 3403
 

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

"Don't tell people how to do things. Tell them what to do and let them surprise you with their results.” - G.S. Patton, Gen. USA
"Never wrestle with a pig....the pig loves it and you end up covered in mud..." anon


   
ReplyQuote