2008-07-12

3n + 1 in Erlang

This is my second Programming Challenges solution written in Erlang. First here.

This time I chose the first problem 3n + 1 #110101.

It is a little bit of a cheat doing it in Erlang, as the major point of the original problem is knowing the limits of your data types, and thus C’s int type is not large enough to manage the problem. I am not even sure is a int64 is large enough or if you need to drop down to your own large number type. Ether way, Erlang does not suffer from this problem with it’s dynamic size number type.

So here is my solution:

-module(threenplusone).
-export([three_n_plus_one_range/2,test/0]).

three_n_plus_one_range(Min, Max) ->
    lists:max([threenplusone(X) || X <- lists:seq(Min, Max) ]).

threenplusone(Num) ->
    threenplusone(Num, 1)

threenplusone(1, Count) -> Count;
threenplusone(Num, Count) ->
    case (Num rem 2) of
        1 -> threenplusone( (Num * 3) + 1, Count + 1);
        0 -> threenplusone( Num div 2, Count + 1)
    end.

test() ->
    20 = three_n_plus_one_range(1,10),
    125 = three_n_plus_one_range(100, 200),
    89 = three_n_plus_one_range(201, 210),
    174 = three_n_plus_one_range(900,1000),
    true.

The problem states that numbers up to 1,000,000 are known to converge to 1, so I ran the problem from 1 -> 1,000,000 and the largest number of steps is 525. This took around 10 seconds on my MacBook which I feel is performant enough.

I quite like using the lists:seq generator and the list comprehension together, but I wonder if there is a better way to-do number generation and function calling in a single line.