project-euler/Sidef/014 Longest Collatz sequence.sf

#!/usr/bin/ruby

# Author: Daniel "Trizen" Șuteu
# License: GPLv3
# Website: https://github.com/trizen

# The following iterative sequence is defined for the set of positive integers:

# n → n/2 (n is even)
# n → 3n + 1 (n is odd)

# Which starting number, under one million, produces the longest chain?

# https://projecteuler.net/problem=14

# Runtime: 34.996s (previously: 47.259s)

func collatz(n) is cached {
    n.is_one ? 1
             : (n.is_even ? 1+collatz(n>>1)
                          : 1+collatz((3*n + 1)>>1));
}

var num = 0;
var max = 0;

for i in (1 ..^ 1e6) {
    var value = collatz(i);
    if (value > max) {
        max = value;
        num = i;
    }
}

say num;