How to Check If a Number Is a Fibonacci Number in Java

Introduction

In this lab, you will learn how to check if a given number is a Fibonacci number in Java. We will explore three different approaches to achieve this.

First, you will learn how to generate the Fibonacci sequence up to a specified number of terms. Then, you will implement a method to check if a given number exists within the generated sequence. Finally, we will optimize the checking process by utilizing a mathematical formula that can efficiently determine if a number is a Fibonacci number without generating the entire sequence.

Generate Fibonacci Sequence

In this step, we will write a Java program to generate the Fibonacci sequence up to a certain number of terms. The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, usually starting with 0 and 1. The sequence looks like this: 0, 1, 1, 2, 3, 5, 8, 13, 21, and so on.

We will create a new Java file and write the code to generate this sequence.

Open the WebIDE if it's not already open. You should be in the ~/project directory by default. If not, open the Terminal at the bottom and type:
```
cd ~/project
```
Create a new file named Fibonacci.java in the ~/project directory. You can do this by right-clicking in the File Explorer on the left and selecting "New File", then typing Fibonacci.java.
Open the Fibonacci.java file in the editor and copy and paste the following Java code:
```
import java.util.Scanner;

public class Fibonacci {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter the number of terms for Fibonacci sequence: ");
        int n = scanner.nextInt();

        if (n <= 0) {
            System.out.println("Please enter a positive integer.");
        } else if (n == 1) {
            System.out.println("Fibonacci sequence up to 1 term:");
            System.out.println("0");
        } else {
            System.out.println("Fibonacci sequence up to " + n + " terms:");

            int firstTerm = 0;
            int secondTerm = 1;

            System.out.print(firstTerm + ", " + secondTerm);

            for (int i = 3; i <= n; ++i) {
                int nextTerm = firstTerm + secondTerm;
                System.out.print(", " + nextTerm);
                firstTerm = secondTerm;
                secondTerm = nextTerm;
            }
            System.out.println(); // Print a newline at the end
        }

        scanner.close();
    }
}
```
Let's quickly understand the key parts of this code:
- import java.util.Scanner;: Imports the Scanner class to read user input.
- public class Fibonacci: Declares the main class named Fibonacci.
- public static void main(String[] args): The main method where the program execution begins.
- Scanner scanner = new Scanner(System.in);: Creates a Scanner object to read input from the console.
- System.out.print("Enter the number of terms... ");: Prompts the user to enter the number of terms.
- int n = scanner.nextInt();: Reads the integer input from the user and stores it in the variable n.
- The if-else if-else block handles different cases for the number of terms (n).
- int firstTerm = 0; int secondTerm = 1;: Initializes the first two terms of the sequence.
- System.out.print(firstTerm + ", " + secondTerm);: Prints the first two terms.
- The for loop calculates and prints the subsequent terms.
- int nextTerm = firstTerm + secondTerm;: Calculates the next term by summing the previous two.
- firstTerm = secondTerm; secondTerm = nextTerm;: Updates firstTerm and secondTerm for the next iteration.
- scanner.close();: Closes the Scanner object.
Save the Fibonacci.java file (Ctrl+S or Cmd+S).
Now, compile the Java program using the javac command in the Terminal:
```
javac Fibonacci.java
```
If there are no errors, this command will create a Fibonacci.class file in the ~/project directory.
Finally, run the compiled program using the java command:
```
java Fibonacci
```
The program will prompt you to enter the number of terms. Enter a number (e.g., 10) and press Enter to see the Fibonacci sequence.
```
Enter the number of terms for Fibonacci sequence: 10
Fibonacci sequence up to 10 terms:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34
```

You have successfully written, compiled, and run a Java program to generate the Fibonacci sequence!

Check if Number Exists in Sequence

In this step, we will modify our Java program to check if a given number exists within the generated Fibonacci sequence. This involves adding logic to compare the user's input number with the terms of the sequence as they are generated.

Open the Fibonacci.java file in the WebIDE editor.

Modify the main method to include the logic for checking if a number exists in the sequence. Replace the existing main method with the following code:

import java.util.Scanner;

public class Fibonacci {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter the number of terms for Fibonacci sequence: ");
        int n = scanner.nextInt();

        if (n <= 0) {
            System.out.println("Please enter a positive integer for the number of terms.");
            scanner.close();
            return; // Exit the program
        }

        System.out.print("Enter the number to check if it exists in the sequence: ");
        int checkNum = scanner.nextInt();

        System.out.println("Fibonacci sequence up to " + n + " terms:");

        int firstTerm = 0;
        int secondTerm = 1;
        boolean found = false;

        // Check the first two terms
        if (checkNum == firstTerm) {
            found = true;
        }
        System.out.print(firstTerm);

        if (n > 1) {
            if (checkNum == secondTerm) {
                found = true;
            }
            System.out.print(", " + secondTerm);
        }


        // Generate and check subsequent terms
        for (int i = 3; i <= n; ++i) {
            int nextTerm = firstTerm + secondTerm;
            if (checkNum == nextTerm) {
                found = true;
            }
            System.out.print(", " + nextTerm);
            firstTerm = secondTerm;
            secondTerm = nextTerm;
        }
        System.out.println(); // Print a newline at the end

        if (found) {
            System.out.println(checkNum + " exists in the Fibonacci sequence.");
        } else {
            System.out.println(checkNum + " does not exist in the Fibonacci sequence.");
        }

        scanner.close();
    }
}

Here's a breakdown of the changes:

We added a prompt to ask the user for the number they want to check (System.out.print("Enter the number to check...")).
We read this number into a new variable checkNum (int checkNum = scanner.nextInt();).
A boolean variable found is initialized to false. This variable will track if the number is found in the sequence.
We check if checkNum is equal to the firstTerm or secondTerm before the loop.
Inside the for loop, after calculating nextTerm, we check if checkNum is equal to nextTerm. If it is, we set found to true.
After the loop finishes, we use an if-else statement to print whether the number was found based on the value of the found variable.

Save the Fibonacci.java file.
Compile the modified program in the Terminal:
```
javac Fibonacci.java
```

Run the compiled program:

java Fibonacci

The program will now ask for the number of terms and then the number to check.

Example 1 (Number exists):

Enter the number of terms for Fibonacci sequence: 10
Enter the number to check if it exists in the sequence: 8
Fibonacci sequence up to 10 terms:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34
8 exists in the Fibonacci sequence.

Example 2 (Number does not exist):

Enter the number of terms for Fibonacci sequence: 10
Enter the number to check if it exists in the sequence: 10
Fibonacci sequence up to 10 terms:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34
10 does not exist in the Fibonacci sequence.

You have successfully modified your program to check if a number is part of the generated Fibonacci sequence.

Optimize with Mathematical Formula

In the previous steps, we generated the Fibonacci sequence iteratively and checked if a number exists by comparing it with each term. For very large numbers, generating the entire sequence can be inefficient. In this step, we will explore a mathematical property of Fibonacci numbers that allows us to check if a number is a Fibonacci number without generating the sequence.

A positive integer x is a Fibonacci number if and only if either 5*x^2 + 4 or 5*x^2 - 4 is a perfect square. A perfect square is an integer that is the square of an integer (e.g., 4 is a perfect square because it's 2*2).

We will create a new Java program that uses this formula to check if a number is a Fibonacci number.

Create a new file named CheckFibonacci.java in the ~/project directory.

Open CheckFibonacci.java and copy and paste the following Java code:

import java.util.Scanner;

public class CheckFibonacci {

    // Function to check if a number is a perfect square
    public static boolean isPerfectSquare(int n) {
        if (n < 0) {
            return false;
        }
        int sqrt = (int) Math.sqrt(n);
        return (sqrt * sqrt == n);
    }

    // Function to check if a number is a Fibonacci number
    public static boolean isFibonacci(int n) {
        // n is Fibonacci if 5*n^2 + 4 or 5*n^2 - 4 is a perfect square
        return isPerfectSquare(5 * n * n + 4) ||
               isPerfectSquare(5 * n * n - 4);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter a number to check if it is a Fibonacci number: ");
        int num = scanner.nextInt();

        if (isFibonacci(num)) {
            System.out.println(num + " is a Fibonacci number.");
        } else {
            System.out.println(num + " is not a Fibonacci number.");
        }

        scanner.close();
    }
}

Let's look at the new parts of this code:

public static boolean isPerfectSquare(int n): This is a helper function that takes an integer n and returns true if n is a perfect square, and false otherwise. It calculates the integer square root and checks if squaring it gives back the original number.
public static boolean isFibonacci(int n): This function implements the mathematical formula. It calculates 5*n*n + 4 and 5*n*n - 4 and uses the isPerfectSquare function to check if either result is a perfect square. The || operator means "or".
The main method now prompts the user for a number, calls the isFibonacci function, and prints the result.

Save the CheckFibonacci.java file.
Compile the new program in the Terminal:
```
javac CheckFibonacci.java
```

Run the compiled program:

java CheckFibonacci

The program will ask you to enter a number. Enter a number (e.g., 13) and press Enter.

Example 1 (Fibonacci number):

Enter a number to check if it is a Fibonacci number: 13
13 is a Fibonacci number.

Example 2 (Not a Fibonacci number):

Enter a number to check if it is a Fibonacci number: 10
10 is not a Fibonacci number.

This method is much more efficient for checking if a single large number is a Fibonacci number compared to generating the sequence up to that number.

Summary

In this lab, we learned how to check if a number is a Fibonacci number in Java. We started by generating the Fibonacci sequence up to a certain number of terms using a simple iterative approach. This involved understanding the definition of the Fibonacci sequence and implementing the logic to calculate and print the terms.

Next, we explored how to check if a given number exists within the generated Fibonacci sequence. Finally, we learned about an optimized approach using a mathematical formula to efficiently determine if a number is a Fibonacci number without explicitly generating the entire sequence. This involved understanding the properties of Fibonacci numbers and applying the formula to perform the check.