## Leonardo Numbers

### June 9, 2015

The Leonardo numbers A001595 are defined as L_{0} = 1, L_{1} = 1, L_{n} = L_{n−2} + L_{n−1} + 1; Dijkstra discusses Leonardo numbers in EWD797, and uses them in the analysis of smoothsort. Leonardo numbers are similar to Fibonacci numbers, and are related by the formula L_{n} = 2 F_{n+1} − 1.

Your task is to write a function that computes Leonardo numbers. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

In Scala as a stream:

def LeonardoNumbers(n1: Int = 1, n2: Int = 1): Stream[Int] = Stream.cons(n1, LeonardoNumbers(n2, n1+n2+1))

LeonardoNumbers() take 15 toList

//> res1: List[Int] = List(1, 1, 3, 5, 9, 15, 25, 41, 67, 109, 177, 287, 465, 753, 1219)

Haskell:

Python iterator in the usual fashion:

And in J, using this for matrix exponentiation:

public class LeonardoNumbers {

public static void main(String[] args) throws NumberFormatException, IOException{

InputStreamReader isr = new InputStreamReader(System.in);

BufferedReader br = new BufferedReader(isr);

System.out.println(“Enter the range to which leonard numbers should be printed”);

int n = Integer.parseInt(br.readLine());

LeonardoNumbers lnd = new LeonardoNumbers();

System.out.println(“Leonardo Series is as follows “);

int result = 0;

for(int i = 1;i<=n; i++){

result = lnd.leonardo(i);

System.out.print(" "+result);

}

}

private int leonardo(int n) {

if(n == 1)

return 1;

if(n == 2)

return 1;

else

return leonardo(n-1)+leonardo(n-2) + 1;

}

}

[…] saw this on Programming Praxis, and I like a lot the solution proposed by Graham on the comments, using an […]