Math Enthusiasts: Have you heard about the Collatz Conjecture?

Chat about just about anything else
Post Reply
ylevental
Level 1
Level 1
Posts: 35
Joined: Tue Jul 18, 2017 2:37 pm

Math Enthusiasts: Have you heard about the Collatz Conjecture?

Post by ylevental » Sat Mar 03, 2018 11:55 am

https://en.wikipedia.org/wiki/Collatz_conjecture

Start with any positive integer n. Then each term is obtained from the previous term as follows: if the previous term is even, the next term is one half the previous term. Otherwise, the next term is 3 times the previous term plus 1. The conjecture is that no matter what value positive integer n, the sequence will always reach 1.

Very easy to understand this problem, but not even the world's best mathematicians have managed to come even close to proving it. I should also warn you that this problem is worth more than $500, maybe about $10 million!

User avatar
Fred Barclay
Level 12
Level 12
Posts: 4147
Joined: Sat Sep 13, 2014 11:12 am
Location: Bumping around in the bush

Re: Math Enthusiasts: Have you heard about the Collatz Conjecture?

Post by Fred Barclay » Sat Mar 03, 2018 12:12 pm

Obligatory xkcd: :mrgreen:
Image
Image
"Once you can accept the universe as matter expanding into nothing that is something, wearing stripes with plaid comes easy."
- Albert Einstein

User avatar
Flemur
Level 16
Level 16
Posts: 6058
Joined: Mon Aug 20, 2012 9:41 pm
Location: Potemkin Village

Re: Math Enthusiasts: Have you heard about the Collatz Conjecture?

Post by Flemur » Sat Mar 03, 2018 3:14 pm

I'd never heard of it.

Code: Select all

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
int main(ac,av)
int ac; char **av;
{
   int k=3;
   int n=0;

   if ( ac > 1 ) k = atoi(av[1]);

   while (k != 1) 
   {
      if( k%2 ) k= 1+(3*k);
      else      k=k/2;

      ++n;
      printf("n=%d, k=%d\n", n, k);
   }
   exit(0);
}
It looks a little...chaotic:

Code: Select all

$ ./a.out 12
n=1, k=6
n=2, k=3
n=3, k=10
n=4, k=5
n=5, k=16
n=6, k=8
n=7, k=4
n=8, k=2
n=9, k=1
Please edit your original post title to include [SOLVED] if/when it is solved!
Your data and OS are backed up....right?
Mint 18.3 Xfce/fluxbox/pulse-less
Xubuntu 17.10/fluxbox/pulse-less

ylevental
Level 1
Level 1
Posts: 35
Joined: Tue Jul 18, 2017 2:37 pm

Re: Math Enthusiasts: Have you heard about the Collatz Conjecture?

Post by ylevental » Sat Mar 03, 2018 6:46 pm

Flemur wrote:
Sat Mar 03, 2018 3:14 pm
It looks a little...chaotic:
That is a huge understatement :wink: . The Wikipedia page I linked to contains a graph for the Collatz sequence starting from the number 27, which runs on for a really long time. Of course, there are many other graphs showing its properties, which seem to have no distinct patterns whatsoever. The famous mathematician Paul Erdos said that proving it is “Hopeless, absolutely hopeless”.

Terry Tao, one of the world's best mathematicians and a fields medalist, tried to prove it many years ago but didn't even come close.

User avatar
slipstick
Level 5
Level 5
Posts: 774
Joined: Sun Oct 21, 2012 9:56 pm
Location: Somewhere on the /LL0 scale

Re: Math Enthusiasts: Have you heard about the Collatz Conjecture?

Post by slipstick » Sat Mar 03, 2018 7:45 pm

ylevental wrote:
Sat Mar 03, 2018 11:55 am
https://en.wikipedia.org/wiki/Collatz_conjecture

Start with any positive integer n. Then each term is obtained from the previous term as follows: if the previous term is even, the next term is one half the previous term. Otherwise, the next term is 3 times the previous term plus 1. The conjecture is that no matter what value positive integer n, the sequence will always reach 1.

Very easy to understand this problem, but not even the world's best mathematicians have managed to come even close to proving it. I should also warn you that this problem is worth more than $500, maybe about $10 million!
I had not heard of that one. There is also the "Beal Conjecture" with a $1 million USD prize. And if that's not hard enough, of course there is the "Riemann Hypothesis" where you could really achieve world-wide fame and $$$$.

https://en.wikipedia.org/wiki/Beal_conjecture
https://en.wikipedia.org/wiki/Riemann_hypothesis

Strange how these problems which seem so simple at first are so intractable.

EDIT: I forgot to mention - "Goldbach's Conjecture"
https://en.wikipedia.org/wiki/Goldbach%27s_conjecture
Last edited by slipstick on Sun Mar 04, 2018 12:39 am, edited 1 time in total.
In theory, theory and practice are the same. In practice, they ain't.

User avatar
all41
Level 13
Level 13
Posts: 4637
Joined: Tue Dec 31, 2013 9:12 am
Location: Computer, Car, Cage

Re: Math Enthusiasts: Have you heard about the Collatz Conjecture?

Post by all41 » Sat Mar 03, 2018 11:27 pm

There are other interesting sequences that will resolve to 1 for any n

When n is even then n/2 in all cases
When n is odd :

n+1

2n+2

4n+4

8n+8

2048n+2048
Proud to be a supporter and monthly contributor to Mint.

rene
Level 8
Level 8
Posts: 2090
Joined: Sun Mar 27, 2016 6:58 pm

Re: Math Enthusiasts: Have you heard about the Collatz Conjecture?

Post by rene » Tue Mar 06, 2018 1:13 am

Collatz is definitely hopeless. The immediately above is not, so for the heck of it...

Let for n a positive integer f be defined by f(n)=n/2 if n even, f(n)=n+1 if n odd. Assume that for some positive n and all positive m<=n there exist an i>=0 such that f^i(m)=1.

1. Certainly such is the case for both n=1, f^0(1)=1, and n=2, f(2)=1.
2. If n>1 is odd let i be such that f^i(n)=1; certainly i>0 since otherwise n=1. Then f^(i-1)(n+1)=f^(i-1)(f(n))=f^i(n)=1.
3. If n>1 is even then (n+2)/2 <= n: let i be such that f^i((n+2)/2)=1. Then f^(i+2)(n+1)=f^(i+1)(n+2)=f^i((n+2)/2)=1.

Inductively we conclude that for all positive n there exist an i>=0 such that f^i(n)=1. The mentioned variants are trivial extensions: let g be defined by g(n)=n/2 if n even, g(n)=2^k(n+1) for k>=0 if n odd. If n even g(n)=n/2=f(n) and if n odd g^(k+1)(n)=n+1=f(n) which is to say that f is a subsequence of g. Given that f visits 1 so then does g.

Less mathematically: in the basic n+1 case you simply divide by two each time while rounding up the result. For odd n you take two rather than one step to do so but who cares: you're still going to end up in 1 (that's also a description of an alternative proof but a little unwieldy to make precise). In the variant cases you for odd n take not just 2 but 2+k steps to divide by two but again, who cares? (that is the above proof).

[EDIT] Edited in the n=2 induction base: can clearly not use the n=1 base when we in the induction step assume n>1. Seems to be valid now.

Post Reply

Return to “Open chat”