“Mathematics is not yet ripe for such problems”
– Paul Erdős
I was listening to Madari today(by Clinton Cerejo; awesome song) when thought for this post struck to me. (don’t ask how; even I am still figuring out, it may be a NP complete!)
I came across this 3n+1 problem on uva online judge 2 years ago. I am sure programmers reading this must have solved it; anyways this post is not for giving solution of it (if you are reading for it please close the tab and try it on your own). By reading the quote above you must have guessed I am discussing the conjecture here.
Yes the conjecture is well documented and it is called Collatz conjecture. It is known by many more names like 3n+1 conjecture, Ulam’s conjecture, Kakutani’s problem,Hasse’s algorithm,Thwaite’s conjecture or the syracuse problem.(names source wikipedia)
Lets state it again:
start with a positive integer n.
if n is odd then make it 3n+1 or divide by 2. It is conjectured that eventually it reaches 1 regardless of n.
e.g. lets check for 18 – 18 9 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 – in 20 steps. This is one of the unsolved problems in mathematics.
The reason this post is titled hailstones is the sequence this process generates is called hailstone sequence/numbers or wondrous numbers. Awesome this is but this is not which interested me it is something called as m-cycles can’t occur.
Let’s define the notion first: f(n) is the function which produces the sequence with a slight modification that for odd n the definition would be f(n) = (3n+1)/2 and (a0,a1,a2…an) be the sequence such that a1 = f(a0), a2 = f(a1)….an = f(an-1). It is called a n-cycle if a0 = f(an). For the given function there is not a single cycle except for the trivial one -> (1,2). Hmm this sounds fascinating. It is proved that there is no cycle till m = 68.
Normally when I come across such problems I specifically think/search of possible ways of tackling them. There is ample literature available regarding that but somehow for this one I don’t want it to be solved (Just like Joker never wants Batman to die; he wants to keep him alive so that he can fight with someone). I was more taken by the extensions of the problem – what if we include all integers instead only positive integers? Well this surely produces cycles in it. But still there are only 5 known cycles even in that case. What do you think of rational numbers?real or complex numbers?
Yes there is lot to discover and tonnes of wannabe solvers(including me 😛 just kidding I have wasted enough time thinking on it in my college classes to stop it now). I would though surely discuss different approaches the inspired friends of mine can take in coming posts.
So lets cover it up by answering one unanswered question – Why hailstone sequence? -> because they go up and down just like hailstones in cloud before crashing to earth(4,2,1)
And a light moment (or shall I say a warning call??) for you
That’s all folks,