Math Enthusiasts: Have you heard about the Collatz Conjecture?

[ylevental]

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!

[Fred Barclay]

Obligatory xkcd:

[Flemur]

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

[ylevental]

It looks a little...chaotic:

That is a huge understatement . 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.

[slipstick]

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

[all41]

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

[rene]

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.