How to calculate the lucas number?

Question

Lucas numbers are numbers in a sequence defined like this:

L(n) = 2 if n = 0

L(n) = 1 if n = 1

otherwise

L(n) = L(n - 1) + L(n - 2)

Here is my code:

public class Lucas {
    public static int lucasnum(int n) {
        if (n >= 0) {
            if (n == 0)
                return 2;
            else if (n == 1)
                return 1;
            else
                return lucasnum(n - 1) + lucasnum(n - 2);
        }
        else{
            if (n == 0)
                return -2;
            else if (n == -1)
                return -1;
            else
                return lucasnum(n + 1) - lucasnum(n + 2);
        }
    }

    public static void main(String[] args) {
        System.out.println(Lucas.lucasnum(-5));
    }
}

But I have some problem with negative number. If n == -5 it must return -11 but my code above return 3.

Answer 1

I think You got the formula for negative indexes backward.

Since,

L(n+2)=L(n+1)+L(n)

=> L(n)=L(n+2)-L(n+1)

So, change

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

to

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

Faster Algorithms

Your Algorithm is an O(n) algorithm, which is slow for large n. You can do it faster.

• O(1). Use Binet's Formula for Lucas Numbers, However, This doesn't give exact results for large values of n due to fixed precision floating point arithmetic.

• O(log n) using recursion:

  Let f(n) be the Fibonacci sequence

  f(0) = 0, f(1) = 1,
  f(n) = f(n-1) + f(n-2)
  

  Calculate Fibonacci numbers in O(log n) time with the recursion:

  f(2n-1) = f(n)^2 + f(n-1)^2
    f(2n) = f(n)^2 + 2*f(n-1)*f(n)
  

  Then Calculate Lucas numbers with:

   L(n) = f(n-1) + f(n+1)
  

  You can find the formulas here:

  • http://mathworld.wolfram.com/FibonacciNumber.html
  • http://mathworld.wolfram.com/LucasNumber.html
  • https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form
  • https://en.wikipedia.orgwiki/Lucas_number#Relationship_to_Fibonacci_numbers

Answer 2

Change

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

to

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