## Leonardo Numbers

### June 9, 2015

The Leonardo numbers A001595 are defined as L0 = 1, L1 = 1, Ln = Ln−2 + Ln−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 Ln = 2 Fn+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

### 6 Responses to “Leonardo Numbers”

1. FA said

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)

2. Francesco said

`leo@(_:lt) = 1 : 1 : zipWith (\a b -> a + b + 1) lt leo`
3. Graham said

Python iterator in the usual fashion:

```def leonardo_numbers():
a, b = 1, 1
while True:
yield a
a, b = b, a + b + 1
```

And in J, using this for matrix exponentiation:

```lm=:1 1,:1 0			  NB. 2x2 matrix
mp=:+/ .*			  NB. matrix (inner) product
pow=: 4 : 'mp/ mp~^:(I.|.#:y) x'  NB. matrix exponentiation by repeated squaring
leonardo=:x:0{0{lm pow	      	  NB. 'leonardo 10' returns 89
```
4. haari said

public class LeonardoNumbers {

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

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

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;

}
}

5. haari said
```import java.io.BufferedReader;
import java.io.IOException;

public class LeonardoNumbers {

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

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

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;

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