Monday, January 19, 2009

Erlang solution for Euler problem 14

In project Euler problem number 14 we are asked to find the longest Collatz sequence using a starting number under one million.

The code for the straight-forward brute force approach (which executes in 9.6 seconds on my MacBook Pro) is:


%% Project Euler, problem 14
%%
%% Find the longest sequence using a starting number under one million.

-module(euler14).
-author('Cayle Spandon').

-export([solve/0, solve/1, series_length/1]).

next_in_series(Nr) ->
if
Nr rem 2 == 0 ->
Nr div 2;
true ->
3 * Nr + 1
end.

series_length(StartNr) ->
if
StartNr == 1 ->
1;
true ->
1 + series_length(next_in_series(StartNr))
end.

longest_series(MaxStartNr) ->
longest_series(1, MaxStartNr, 0, 0).

longest_series(StartNr, MaxStartNr, Longest, LongestStartNr) ->
if
StartNr >= MaxStartNr ->
LongestStartNr;
true ->
Length = series_length(StartNr),
if
Length > Longest ->
longest_series(StartNr + 1, MaxStartNr, Length, StartNr);
true ->
longest_series(StartNr + 1, MaxStartNr, Longest, LongestStartNr)
end
end.

solve() ->
solve(1000000).

solve(N) ->
longest_series(N).

1 comment:

Anonymous said...

661 ms - Assembler on old Athlon XP 1800 Mhz
versus
9600 ms Erlang on MacBook
14.5 times faster on slower machine.
not too bad, isn't it?
+++
C:\Asm>euler14

MAX 837800 525 Terme
661 ms