|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?
Ok, so here it is. Lets have fun with F#:
let seq_length n = n > Seq.unfold(fun x -> match x with
x when x = 0L -> None
x when x = 1L -> Some((1L,0L))
x when x%2L=0L -> Some((x,x/2L))
_ -> Some((x,3L*x + 1L))
) > Seq.length
[for i in 1L..1000000L -> (i, seq_length i)]
> List.fold1_left(fun (ai,al) (i,l) -> if l > al then (i,l) else (ai,al) )
> (fun (x,y) -> x ) > print_any
Elegant, slow version of solution-> ~20 lines; ~10 seconds.
Now lets try C#:
static long CountTerms(long x, ref long terms)
long tc = 1;
long k = x;
k = (k % 2 == 0) ? k / 2 : 3 * k + 1;
if (k <= x)
if (terms[k] > 0)
terms[x] = terms[k] + tc;
terms[x] = tc;
return terms[x] ;
static long LongestSeq()
long max = 1000000;
long termcount = new long[max+1];
long tcmax = 0;
long c = 0;
long ix = 0;
for (int i = 1; i <= max; i++)
c = CountTerms(i, ref termcount);
if ( c > tcmax)
tcmax = c;
ix = i;
static void Main(string args)
Ugly, fast version of solution -> ~0.18 second; ~60 lines.
F# solutions can be done in more elegant/less code way, but in contrary it is slower that C#
counterpart. Also C# solutions can be written in fast way, but needs more code and attention.
F# solution was by factor 55 slower than C# solution, but also code was by factor of 3 shorter than C# counterpart. So if you want elegancy/generics power - take F#; and if you want only perfomance- take C#.
P.S. There is a way in F# to code (using mutable keyword) very very ugly like in C#, but i`ve not
suggest using it on F#,- why to code ugly in F# if you can grab C# instead ?? :-)