The generation problem - revisited

To conclude we would like to present an algorithm for the generation of the first $n$ elements of $\cal{L}$, which is based on a recursive definition of $\cal{L}$. The the algorithm itself is not recursive. The teacher should not fail to use this opportunity and point out the difference between a recursive definition of a concept and a recursive algorithm. Claim 4, which has to be proven mathematically (in class or as a home exercise), defines $\cal{L}$ recursively.

Claim 4:
$\cal{L}$ can be defined as follows:
$a_0 = 0, a_1 = 1$, and for every $i, i \geq 1$,
$a_{2i} = 2a_i+1$, $a_{2i+1} = 3a_i+1$.

Below is the algorithm given as a Pascal program which outputs all the elements of $\cal{L}$ from $a_0$ to $a_{n-1}$:

program $generate$(input,output);

const  n = 10000;

var i: integer;


a: array[0..n] of integer;

begin


a[0]:=0; a[1]:=1;      

for i:=1 to (n-1) div 2  do 

begin 


a[2$\ast$i]:=2$\ast$a[i]+1;


a[2$\ast$i+1]:=3$\ast$a[i]+1

end;

for i:=0 to n-1 do write(a[i]) 

end.

As mentioned before we can now solve the problem of Example1 formulated in the previous section. To solve this problem it is sufficient to generate the elements $a[0]$ to $a[n-1]$, and ignore the elements that are greater than $n$.