Here is an implementation in OCaml. Time taken on a 1.3 GHz MacBook Air:
:tmp $ time ./collatz.native 1000000
start: 837799 length 329
real 0m0.782s
user 0m0.776s
sys 0m0.004s
exception Error of string
let (@@) f x = f x
let error fmt = Printf.kprintf (fun msg -> raise (Error msg)) fmt
let max (a, x) (b, y) = if x > y then (a, x) else (b, y)
let length start =
let rec loop len a =
let next = if a mod 2 = 0 then a/2 else (3*a+1)/2 in
if a != 1 then
loop (len+1) next
else
len
in
loop 0 start
let collatz limit =
let rec loop start longest =
if start >= limit
then longest
else loop (start+1) (max longest (start, length start))
in
loop 1 (1,0)
let report (start, len) = Printf.printf "start: %d length %d\n" start len
let main () =
let argv = List.tl @@ Array.to_list Sys.argv in
match argv with
| [] -> report @@ collatz 10000
| [n] -> report @@ collatz @@ int_of_string n
| _ -> error "usage: collatz [n]"
let () = main ()
The code probably could be made faster by avoiding passing tuples (start, length) around as these are allocated on the heap. However, I found it a little bit more abstract.