## Leonardo Numbers

### June 9, 2015

Our first implementation is the natural recursive definition, which has exponential time complexity:

```(define (leo1 n)   (if ( (time (leo1 30)) (time (leo1 30))     2 collections     193 ms elapsed cpu time, including 1 ms collecting     193 ms elapsed real time, including 1 ms collecting     21541376 bytes allocated, including 16611696 bytes reclaimed 2692537```

Our second implementation iterates through the sequence of Leonardo numbers, keeping track of the two prior numbers in the sequence, and operates in linear time:

```(define (leo2 n)   (if ( (time (leo2 30)) (time (leo2 30))     no collections     0 ms elapsed cpu time     0 ms elapsed real time     3376 bytes allocated 2692537 > (time (begin (leo2 250000) 'done)) (time (begin (leo2 250000) ...))     612 collections     4475 ms elapsed cpu time, including 80 ms collecting     4492 ms elapsed real time, including 59 ms collecting     5459988896 bytes allocated, including 5457970720 bytes reclaimed done```

Our third implementation uses matrix multiplication to compute the related Fibonacci number, as we did in a previous exercise; it operates in logarithmic time:

```(define (fib n)   (if (zero? n) 0     (matrix-ref (matrix-power #(#(1 1) #(1 0)) n) 1 0)))```

``` (define (leo3 n) (- (* (fib (+ n 1)) 2) 1)) ```

```> (time (leo3 30)) (time (leo3 30))     no collections     0 ms elapsed cpu time     0 ms elapsed real time     34432 bytes allocated 2692537 > (time (begin (leo3 250000) 'done)) (time (begin (leo3 250000) ...))     1 collection     340 ms elapsed cpu time, including 0 ms collecting     339 ms elapsed real time, including 0 ms collecting     2792832 bytes allocated, including 8361360 bytes reclaimed done > (time (begin (leo3 1000000) 'done)) (time (begin (leo3 1000000) ...))     1 collection     5370 ms elapsed cpu time, including 1 ms collecting     5409 ms elapsed real time, including 0 ms collecting     10856992 bytes allocated, including 8591504 bytes reclaimed done```

We don’t get the full logarithmic effect of the algorithm because the numbers involved are so big that the time to do arithmetic on them becomes significant; note that L1000000 has 208988 digits. You can run the program at http://ideone.com/XQTUwK, where you will also see the matrix functions.

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 […]