Harsh J

About the immutability of variables once bounded in Erlang:

Single assignment is like algebra.

When I went to school, my math teacher said, “If there’s an X in several different parts in the same equation, then all the Xs mean the same thing.” That’s how we can solve equations: if we know that X+Y=10 and X-Y=2, then X will be 6 and Y will be 4 in both equations.

But when I learned my first programming language, we were shown stuff like this:
X = X + 1

Everyone protested, saying “you can’t do that!”. But the teacher said we were wrong, and we had to unlearn what we learned in math class. X isn’t a math variable: it’s like a pigeon hole/little box…

In Erlang, variables are just like they are in math. When you associate a value with a variable, you’re making an assertion – a statement of fact. This variable has that value. And that’s that.

– Joe Armstrong, in his book Programming Erlang.

Learning Erlang is a fun task. Solving PE problems with it even more. You can never really beat PE problems unless you have your own fast implementations of primality tests, prime generation sieves and so on.

A quick way to generate primes, as many would tell you, would be to implement and use the Sieve of Eratosthenes. Its a simple sieve that works by striking off all multiples of primes thus observed in sequence. Wikipedia has an illustration on its working technique.

There is another simple sieve derived from the same idea, known as the Sieve of Euler, which uses a filtering technique based on products of an encountered prime across the remaining elements. This sort of a sieve, again explained in a good manner at Wikipedia, is shorter and easier to implement in Erlang than the traditional Eratosthenes (and I mean proper Eratosthenes, mind you).

The following is the solution I came up with, a couple of days into learning Erlang for great good:

-module(primes).
-export([generatePrimes/1]).

% Sieve of Euler %

generatePrimes (N) when is_integer(N) and (N > 1) ->
    Numbers = lists:seq(2,N),
    BeginIndex = 1,
    generatePrimes(Numbers, [], BeginIndex).

generatePrimes (Numbers, Numbers, _Index) ->
    Numbers;

generatePrimes (Numbers, _PreviousNumbers, Index) ->
    FilteredNumbers = ordsets:subtract(Numbers, multiples(lists:nth(Index, Numbers), Numbers)),
    generatePrimes(FilteredNumbers, Numbers, Index + 1).

multiples (Prime, Numbers) ->
    lists:map(fun(Num) -> Prime * Num end, Numbers).

% Compile as c(primes). %

The function primes:generatePrimes(N) will generate all primes until N. On my 2.93 GHz machine it takes about 2.1s to generate all primes under a million (78498 primes).

As a bonus, you can go ahead and compute single-line inelegant solutions #3 and #10 of Project Euler as:

% Solution to problem 3 %
lists:nth(1, lists:dropwhile(fun(X) -> not(600851475143 rem X == 0) end, lists:reverse(primes:generatePrimes(trunc(math:sqrt(600851475143)))))).

% Solution to problem 10 %
lists:sum(primes:generatePrimes(2000000)).

Notes: There is some redundant multiple calculation involved but I noticed that if I perform a sublist operation to remove that it slows the generation down, so I let it be. The sieving operation also terminates when it notices that no number was filtered in one of its call, as this marks the proper end of it. For instance, to generate all primes under 100, it only sieves through the first five primes.

Update:

Kind commenter Angel (angel at uah dot es) posted a solution (and a multi-process one!) to a proper Eratosthenes’ Sieve (based on the O’Neill’s paper I referenced above), which goes below:

% "Genuine" Erathostenes sieve in erlang
% based on www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf
% 2009 Angel Alvarez
%
% Process  1     2     3     4     5     6     7 ....
%
%         02    03    05    07    11    13    17
% P 02 -> 04
% P 03    04 -> 09
% C 04 == 04    09
% P 05    06    09 -> 25
% C 06 == 06    09    25
% P 07    08    09    25 -> 49
% C 08 == 08    09    25    49
% C 09    10 == 09    25    49
% C 10 == 10    12    25    49
% P 11    12    12    25    49 -> 121
% C 12 == 12    12    25    49    121
% P 13    14    15    25    49    121 -> 169
% C 14 == 14    15    25    49    121    169
% C 15    16 == 15    25    49    121    169
% C 16 == 16    18    25    49    121    169
% P 17    18    18    25    49    121    169 -> 289

-module(multi_erathostenes).
-author("angel at uah dot es").
-compile(export_all).

compare(X,Y) when X > Y -> greater;
compare(X,Y) when X < Y -> smaller;
compare(_,_) -> equal.

worker(Prime,UpperBound)->
	receive
		{test,Number,ParentPID} ->
			ParentPID ! ok,
			case compare(Number,UpperBound) of
				equal ->
%					io:format("[Worker of prime: ~w (~w)] Found composite: ~w~n",[Prime,UpperBound,Number]),
					worker(Prime,UpperBound + Prime);
				smaller ->
					io:format("[Worker of prime: ~w (~w)] Spawn new worker for Prime: ~w~n",[Prime,UpperBound,Number]),
					NextPID =spawn(?MODULE,worker,[Number,Number*Number]),
					worker(Prime,UpperBound,NextPID)
			end;
		stop ->
		    noop
	end.

worker(Prime,UpperBound,NextPID) ->
	receive
		{test,Number,ParentPID} ->
			ParentPID ! ok,
			case compare(Number,UpperBound) of
				equal ->
%					io:format("[Worker of prime: ~w (~w)] Found composite: ~w~n",[Prime,UpperBound,Number]),
					worker(Prime,UpperBound + Prime,NextPID);
				smaller ->
% 					io:format("[Worker of prime: ~w (~w)] passing along: ~w~n",[Prime,UpperBound,Number]),
					NextPID ! {test,Number,self()},
					receive
					    ok -> ok
					end,
					worker(Prime,UpperBound,NextPID);
				greater ->
% 					io:format("[Worker of prime: ~w (~w)] passing along: ~w~n",[Prime,UpperBound,Number]),
					NextPID ! {test,Number,self()},
					receive
					    ok -> ok
					end,
 					worker(Prime,UpperBound+Prime,NextPID)
			end;
		stop ->
		    NextPID ! stop,
		    noop
	end.

start(N) ->
    OnePID=spawn(?MODULE,worker,[2,4]),
    cicle(3,N,OnePID).

cicle(Last,Last,Worker) ->
    Worker ! stop;
cicle(Current,Last,Worker) ->
    Worker ! {test,Current,self()},
    receive
	ok -> ok
    end,
    cicle(Current+1,Last,Worker).