Assignment 1 - Erlang (due Thu 22 Nov 2012)

1. Write a function that takes an integer N and returns the list of integers in the range 2..N-1 that divide N.
2. Write a function that takes an integer N and returns a list of prime numbers less than or equal to N.

List comprehensions must be an integral part of the solutions.

The following type specifiers should be valid for your solutions:

-spec dividers_of(integer()) -> [integer()].
-spec primes_up_to(integer()) -> [integer()].

(Please note that there are other definitions of the term "Fibonacci tree".)

Say that a Fibonacci tree has the following structure

• every node in the tree has either no children (a leaf) or two children.
• a node of order one or zero has no children (it is a leaf).
• a node of order n, where n>1, has one child of order n-1 and one of order n-2.
• A Fibonacci tree of order n is a Fibonacci tree where the root has order n.

Fibonacci trees of order 3 and 4. The digits indicate the order of each node.

     3               4
    / \            /   \
   1   2          2     3
      / \        / \   / \
     0   1      0   1 1   2
                         / \
                        0   1

Your task is to define a function that creates a Fibonacci tree of processes, i.e., each node is represented by a process. Each process in the tree should keep track of its children and nothing else. Internal nodes in the tree should only be referred to by their parents.

The function that creates the tree should return only when all nodes are created.

Each node in the tree should accept a message "sum" that requests the node to compute the number of nodes in the subtree in which it is root. Since each node only knows its children, this computation must be implemented by propagating messages. As part of the assignment you need to decide on the format of the "sum" message.

Define a function that creates the Fibonacci tree, as explained above.
Define an appropriate interface.
Define a test function that tests your implementation of Fibonacci trees by building trees of order 10 and 15 and computing their sums a few times.
You may use the gen_server behaviour of OTP in your solution, but you are not required to.

Signature:

-spec fibonacci_tree(integer()) -> integer().

Write a program that given an integer returns the prime factors of that number. Assume that the numbers can be very large and that several computations will be done. This means that you should remember state from previous computations for reuse. Also, try to parallelise your solution so it can be spread on several cores, VMs or machines.

Signatures:

-spec factorize_initial_state() -> State :: term().
-spec factorize(integer(), State :: term()) -> {[integer()], NewState :: term()}.
%% Optional: if you want the possibility to dispose of the state.
-spec factorize_dispose_state(State :: term()) -> ok.

Template for submission

-module(assignment1).

-export([dividers_of/1, primes_up_to/1]).
-export([fibonacci_tree/1]).
-export([factorize_initial_state/0, factorize/2, factorize_dispose_state/1]).

-spec dividers_of(integer()) -> [integer()].
dividers_of(20) -> [2,4,5,10].

-spec primes_up_to(integer()) -> [integer()].
primes_up_to(10) -> [2,3,5,7].

fibonacci_tree(3) -> 5;
fibonacci_tree(4) -> 9.

-spec factorize_initial_state() -> State :: term().

-spec factorize(integer(), State :: term()) ->
   {[integer()], NewState :: term()}.