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

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

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

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
Level 12 Posts: 4207
Joined: Sat Sep 13, 2014 11:12 am
Location: Bumping around in the bush

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

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

Flemur
Level 17 Posts: 7065
Joined: Mon Aug 20, 2012 9:41 pm
Location: Potemkin Village

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

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);

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 19.1 Xfce/fluxbox
Manjaro openbox/fluxbox

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

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

Flemur wrote:
Sat Mar 03, 2018 3:14 pm
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
Level 5 Posts: 936
Joined: Sun Oct 21, 2012 9:56 pm
Location: Somewhere on the /LL0 scale

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

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.

all41
Level 15 Posts: 5546
Joined: Tue Dec 31, 2013 9:12 am
Location: Computer, Car, Cage

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

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
Level 11 Posts: 3606
Joined: Sun Mar 27, 2016 6:58 pm

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

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.