The Collatz Conjecture
by Bbob on March 24, 2007
When I was lecturing at university, I had engineering and math students for the most part. Very few took advanced graduate Computer Science courses who didn't have a good mathematics background.
Many people in the general population, however, suffer from "math anxiety". They either (a) don't have the math background to read some intimidating higher math, or (b) they just are afraid of math, a priori.
So let's look at some really intuitive simple mathematics problems just for fun.
Sometime in the 1930s, the German mathematician Lothar Collatz formulated (other people think this math problem goes back much further in time) a problem and a conjecture which has baffled mathematicians since. No one has conquered it.
So let's have a go at its statement.
We define a function, which generates a sequence of integers, in the following way:
The function f(x) returns 3x+1 if x is an odd number, or x divided by 2 if x is an even number. Keep on going to the next, etc.
So let's take the number 10 and run it through the function.
f(10) is ...
... since 10 is an even number, we divide it in half, getting 5.
then ...
for the next number out of the function, we're holding 5 and since 5 is an odd number, we multiply it by 3 and add 1, getting 16.
So far, we have generated f(10) as 10,5,16 ...
So we keep on going.
16 is even, so we divide it by 2 generating 8.
8 is even so we do the same, getting 4.
4 as well, and we get 2.
2 also, and we get 1.
Stop.
So, f(10) is 10,5,16,8,4,2,1.
Let's try f(18).
And we get: 18, 9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.
Stop when we get to 1.
So Collatz conjectured that the sequence for any given number x put into the function would ultimately stop at and get to the number 1.
No one has been able to prove that yet. It's been baffling mathematicians for quite some decades now.
And some numbers input to the function, like 27 seem to dance around way up in the sky before coming back down to 1 ultimately. Try it. The sequence has 112 numbers in it !
What is daunting is that the late great Hungarian mathematician, Paul Erdos, said when asked about the conjecture and solving this problem and proving the conjecture, that "mathematics is not ready for this kind of problem".
Well, that has never stopped mathematicians from trying to prove it ! But so far no one has had any luck.