1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
-- Longest Collatz sequence
--
-- Problem 14
-- The following iterative sequence is defined for the set of positive integers:
--
-- n → n/2 (n is even)
-- n → 3n + 1 (n is odd)
--
-- Using the rule above and starting with 13, we generate the following sequence:
--
-- 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
-- It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms.
-- Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.
--
-- Which starting number, under one million, produces the longest chain?
--
-- NOTE: Once the chain starts the terms are allowed to go above one million.
import Data.List
type Sequence = [Int]
main = do
print (snd $ maximumBy (\(l0, n0) (l1, n1) -> compare l0 l1)
[(length $ collatz n, n) | n <- [1..1000000]]) -- takes 7s
-- can be optimise by keeping creating other collatz sequence with the numbers after n
-- print ([(n, length n_seq) | n <- tails $ collatz 7, length n_seq != 0])
-- print (collatzLenFrom 1000000)
-- print (snd $ maximumBy (\(l0, n0) (l1, n1) -> compare l0 l1) (collatzLenBellow 10))
-- print (collatzLenBellow 10)
-- print (collatzUntil 10)
collatz :: Int -> [Int]
collatz 1 = [1]
collatz n = case n `mod` 2 of 0 -> n : collatz (n `div` 2)
1 -> n : odd_next : collatz (odd_next `div` 2)
where odd_next = 3 * n + 1
-- need to build a tree, a sequence can merge in another one,
-- reduce calculation cost tremendously (probably)
--
-- collatzUntil :: Int -> [[Int]]
-- collatzUntil n = collatzRange 1 n
-- collatzRange :: Int -> Int -> [[Int]]
-- collatzRange lo hi
-- | lo >= hi = []
-- | otherwise = collatzBase lo
-- collatzLenBellow :: Int -> [(Int, Int)]
-- collatzLenBellow 1 = [(1, 1)]
-- collatzLenBellow up = (collatzLenFrom up) `union` collatzLenBellow (up - 1)
-- collatzLenFrom :: Int -> [(Int, Int)]
-- collatzLenFrom top = [(head seq, length seq) | seq <- init $ tails $ collatz top]
--
-- data Tree a = Empty | Tree a [Tree a]
|
