collatz.c

#include <stdio.h>

int main() {
    unsigned long longest = 0;
    unsigned long longest_collatz = 0;
    unsigned long i = 2;
    unsigned long collatz, length;
    for(; i < 1000000; i++) {
        collatz = i;
        length  = 0;
        while(collatz != 1) {
            if(collatz % 2 == 0) {
                collatz /= 2;
            } else {
                collatz = 3*collatz + 1;
            }
            length++;

            if(collatz < 0) {
                printf("ARGH! %lu\n", collatz);
                break;
            }
        }
        length++;

        if(length > longest) {
            longest = length;
            longest_collatz = i;
        }

    }
    printf("Number: %lu Length: %lu\n", longest_collatz, longest);
    return 0;
}

collatz.hs

module Main where

import Data.List
import qualified Data.Map as Map
import Debug.Trace

{- Om jag hittar talet i tabellen så kan jag lägga till föregående tal med en längd som är talets längd + 1 
 - 13 -> 14 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1.
 -
 - Så jag hittar 13 med längden 10. 
 - Då vet jag att föregående tal ex. 26 ska ha längden 1 + 10.
 - Och talet innan det ska ha längden 1 + 1 + 10.
 -}

-- length -> list of numbers -> lookup table -> lookup table
collatz :: Int -> [Int] -> Map.Map Int Int -> Map.Map Int Int
collatz n xs m = case Map.lookup next m of
                     Just len -> insertLengths (len+1) xs (Map.insert n (len+1) m)
                     Nothing  -> collatz next (n:xs) m
    where next | even n    = div n 2
               | otherwise = 3*n + 1
          insertLengths len' xs m = Map.union m $ Map.fromList $ lengthList len' xs -- Insert all numbers that haven't been inserted yet.
          lengthList len' xs      = zip xs [len'+1..]
          -- lengthList len' xs      = trace (show len' ++ " " ++ show xs) (zip xs [len'+1..])

solve = Map.foldlWithKey' largest (0,0) $ foldl' (\m n -> collatz n [] m) (Map.fromList [(1,1)]) [1..999999]
    where largest (k1, v1) k2 v2 = if v1 > v2 
                                   then (k1,v1)
                                   else (k2,v2)
--solve = Map.foldl' max 0 $ collatz 999999 [] $ Map.fromList [(1,1)]

main = putStrLn $ show solve