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.
Programming Praxis 
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:
def leonardo_numbers(): a, b = 1, 1 while True: yield a a, b = b, a + b + 1And 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 89public 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;
}
}
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; 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 […]