Monday, January 12, 2009

Erlang solution for Euler problem 6

Euler problem 6 asks us to compute the difference between the sum of squares and the square of the sums for the numbers 1 ... 100.

I remembered the formula for adding up the integers from 1 to N from an amusing story about how Gauss solved it when he was 10 years old:

1 + 2 + 3 + ... + n = n(n+1)/2.

I did not remember a formula for the sum of squares, so I computed that brute force.

After I wrote the Erlang program I found that there is in fact a formula (the square pyramidal number which is a special case of Faulhaber's formula) for the sum of squares too:

12 + 22 + 32 + ... + n2 = (2n3 + 3n2 + n)/2

Here is the Erlang solution:

%% Project Euler, problem 6
%%
%% The sum of the squares of the first ten natural numbers is,
%% 1^2 + 2^2 + ... + 10^2 = 385
%%
%% The square of the sum of the first ten natural numbers is,
%% (1 + 2 + ....+ 10)^2 = 55^2 =3025
%%
%% Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum
%% is 3025 - 385 = 2640.
%%
%% Find the difference between the sum of the squares of the first one hundred natural numbers and the square of
%% the sum.

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

-export([solve/0]).

sumOfSquares(N) ->
if
N == 0 -> 0;
true -> N * N + sumOfSquares(N-1)
end.

squareOfSum(N) ->
Sum = N * (N+1) div 2,
Sum * Sum.

solve() ->
solve(100).

solve(N) ->
squareOfSum(N) - sumOfSquares(N).

No comments: