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

    Haskell:

    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{

    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;

    }
    }

  5. haari said
    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;
    		
    	}
    }
    
  6. […] saw this on Programming Praxis, and I like a lot the solution proposed by Graham on the comments, using an […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: