Determining whether a number is a Fibonacci number

Emily picture Emily · Jun 29, 2010 · Viewed 11.7k times · Source

I need to to write a Java code that checks whether the user inputed number is in the Fibonacci sequence.

I have no issue writing the Fibonacci sequence to output, but (probably because its late at night) I'm struggling to think of the sequence of "whether" it is a Fibonacci number. I keep starting over and over again. Its really doing my head in.

What I currently have is the nth.

public static void main(String[] args)
{
    ConsoleReader console = new ConsoleReader();

    System.out.println("Enter the value for your n: ");
    int num = (console.readInt());
    System.out.println("\nThe largest nth fibonacci: "+fib(num));
    System.out.println();
}

static int fib(int n){
    int f = 0;
    int g = 1;
    int largeNum = -1;
    for(int i = 0; i < n; i++)
    {
      if(i == (n-1))
          largeNum = f;
      System.out.print(f + " ");
      f = f + g;
      g = f - g;
    }
    return largeNum;
}

Answer

IVlad picture IVlad · Jun 29, 2010

Read the section titled "recognizing fibonacci numbers" on wikipedia.

Alternatively, a positive integer z is a Fibonacci number if and only if one of 5z^2 + 4 or 5z^2 − 4 is a perfect square.[17]

Alternatively, you can keep generating fibonacci numbers until one becomes equal to your number: if it does, then your number is a fibonacci number, if not, the numbers will eventually become bigger than your number, and you can stop. This is pretty inefficient however.