Faffing round the edges Its easier than getting stuck in

Erlang for Project Euler problem 2.

Ok. So now I am looking at problem 2 from Project Euler.

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Find the sum of all the even-valued terms in the sequence which do not exceed four million

Fibonacci series? I have heard of it...Quick look at wikipedia and I at least know what it is. My rather brute force approach is (thanks mainly to the rather excellent LiteratePrograms.org. There was actually a (purportedly) more optimised version on the site but since I did not understand it there was nothing I could do to appropriate it):-

prob_2() ->
	L = lists:filter(fun(X) -> (X rem 2 =:= 0) end, fib(33)),
	lists:sum(L).

%used by the problem 2
fib_acc( 0, _Result, _Next, List) -> List;
fib_acc( Iter, Result, Next, List) when Iter > 0 ->
        fib_acc( Iter -1, Next, Result + Next,[Next|List]).

fib(N) -> fib_acc( N, 0, 1,[]).

I guess this is rather sub optimal since I have to first run the Fib sequence function a few times and figure out which Fib number is the closest to 4 million. Then there is the hack where I have hardcoded that number (33). But it gets me the answer so I get to learn loads more by reading the forum.

I am really let down by my lack of maths at school. Sure some of that is my fault for being a cocky, arrogant jerk at 13 but then again the teachers should have been used to that.

Ok, so after reading a bit I have these two more optimal approaches:-

prob_2_alt(Limit) ->
	summer(Limit, 0, 1, 1).

summer(Limit, Sum, _A, B) when B >= Limit -> Sum;
summer(Limit, Sum, A, B) when B rem 2 =:= 0->
	summer(Limit, Sum+B, B, A+B );
summer(Limit, Sum, A, B) ->
	summer(Limit, Sum, B, A+B).

And this (which is just a novice's erlanging of the Euler pdf on the problem):-

prob_2_alt2(Limit) ->
	summer2(Limit, 0,  1, 2).

summer2(Limit, Sum,  _B, C) when C >= Limit -> Sum;
summer2(Limit, Sum,  B, C) ->
	summer2(Limit, Sum+C,  C+B+C, C+B+C+B+C).

Not sure how much I have learned here except that I have had my admiration of Erlang further stoked. I understand the more elegant Euler solutions and I'm pleased I was able to brute force my way in to get an answer and learn a lot more about the problem. Thankfully I understand the answers completely so feel satisfied if a tad dim.

I am not sure how pretty my Java Impl of the above would be. Might try later...then again, I might not.

Erlang for Project Euler problem 1.

I saw this post and it made me have a crack at Project Euler problem 1.

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

I  thought I'd better have a go before reading the post. My first crack was a bit long:-

-module (sum_3_5).

-compile(export_all).

sum_3_5() ->
	L = lists:seq(1, 999),
	lists:sum(lists:filter(fun worker/1, L)).

worker(Elem) ->
	by_3(Elem) or by_5(Elem).		

by_3(Elem) ->
	case Elem rem 3 of
		0 -> true;
		_ -> false
	end.

by_5(Elem) ->
	case Elem rem 5 of
		0 -> true;
		_ -> false
	end.

But it worked. Second attempt (2 minutes later) is much more terse:-

prob_1(N) ->
	lists:sum([A || A <- lists:seq(1,N), (A rem 3 =:=0) or (A rem 5 =:= 0)]).

I had one more go at it to try and speed it up for large values of N:-

prob_1_alt(N) ->
	lists:sum(lists:seq(0, N, 3)) +
        lists:sum(lists:seq(0,N, 5)) -
        lists:sum(lists:seq(0, N, 15)).

Which was a lot faster for large numbers. Is it worth creating a process to calculate each term in the above equation? Will that speed it up more for very large values of N? I might try later. But I'll probably try Project Euler 1 in Squeak, Clojure and Scheme first. And problem 2 in Erlang.