I am coninuing my adventure in Haskell. In order to make it a bit more fun, I decided to code a simple yet very intriguing problem, I first heard of when I read AI Memo 239: The Collatz conjecture.
Construct a sequence of integers where given an arbitrary interger the value of the next is:
- If the number is even, divide it by two.
- If the number is odd, triple it and add one.
This can easily be coded in Haskell as follows:
collatz :: Int -> Int
collatz 1 = 1
collatz n =
if (even n)
then (n `div` 2)
else (3 * n + 1)
But how can one obtain a sequence of numbers from this? A very clever solution is here where the author implements a variation of takeWhile which includes also the first list item that fails the test the first time. So my question became, can it be done in another way? Yes it can:
collatzSequence :: Int -> [Int]
collatzSequence n =
if n == 1
then [1]
else [n] ++ collatzSequence (collatz n)
Let's see some test runs:
*Main> collatzSequence 5
[5,16,8,4,2,1]
*Main> collatzSequence 50
[50,25,76,38,19,58,29,88,44,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1]
*Main> collatzSequence 500
[500,250,125,376,188,94,47,142,71,214,107,322,161,484,242,121,364,182,91,274,137,412,206,103,310,155,466,233,700,350,175,526,263,790,395,1186,593,1780,890,445,1336,668,334,167,502,251,754,377,1132,566,283,850,425,1276,638,319,958,479,1438,719,2158,1079,3238,1619,4858,2429,7288,3644,1822,911,2734,1367,4102,2051,6154,3077,9232,4616,2308,1154,577,1732,866,433,1300,650,325,976,488,244,122,61,184,92,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1]
*Main> collatzSequence 512
[512,256,128,64,32,16,8,4,2,1]
*Main> collatzSequence 513
[513,1540,770,385,1156,578,289,868,434,217,652,326,163,490,245,736,368,184,92,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1]
*Main>
You may have observed we only run it on positive integers. When we run it with negative integers, there are a few more cycles that we need to take into account. Here is the updated sequence function, written with guards:
collatzSequence :: Int -> [Int]
collatzSequence n
| n == 1 = [1]
| n == (-2) = [(-2)]
| n == (-5) = [(-5)]
| n == (-17) = [(-17)]
| otherwise = [n] ++ collatzSequence (collatz n)
Test:
*Main> collatzSequence (-50)
[-50,-25,-74,-37,-110,-55,-164,-82,-41,-122,-61,-182,-91,-272,-136,-68,-34,-17]
Now if there was also a way to prove the conjecture...
Please note that in Haskell the unary minus is a function and not an operator, hence, you need to parenthesize. This also works:
*Main> collatzSequence $ -50
[-50,-25,-74,-37,-110,-55,-164,-82,-41,-122,-61,-182,-91,-272,-136,-68,-34,-17]
Update: A friend posted me his own elegant version of the Collatz sequence:
collatz :: Int -> [Int]
collatz 1 = [1]
collatz n
| even n = n : collatz (n `div` 2)
| odd n = n : collatz (n * 3 + 1)
main = do
putStrLn $ show $ collatz 1
putStrLn $ show $ collatz 6
putStrLn $ show $ collatz 23