如何测试一个数是否为斐波那契数

1. Overview

In this tutorial, we’ll discuss the Fibonacci series. We’ll define the Fibonacci series and explore various methods to generate Fibonacci numbers with examples.

Finally, we’ll present the pseudocode to check if a given number is a Fibonacci number or not.

2. Fibonacci Series

The Fibonacci series can be defined as the sequence of numbers: (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, .....) . The Fibonacci series was initially elaborated and used in Indian mathematics by Pingala. However, it was illustrated to the world by Leonardo Pisano Bogollo, later known as Fibonacci.

Additionally, the Fibonacci series follows an interesting property. The property is we can find the next element in the series by adding two elements that appear before it:

fibo

Let’s verify the property. Element 34 can be found by adding two previous elements, 21 and 13 (21 + 13 = 31). Similarly, we can find element 8 by adding two previous elements, 5 and 3. Additionally, we can find the next element of 34 in the series. It’ll be 55 (34 + 21).

Now, let’s derive a generalized equation for generating the Fibonacci series. Initially, it starts with initial data $S_{0}=0$ and $S_{1}=1$ , which are given in advance. Moreover, the series proceeds further by adding two previous adjacent elements. Hence, the element at the position in the series can be calculated as:

$[S_{x}=S_{x-1}+S_{x-2}, x>=2, S_{0}=0, S_{1}=1]$

Additionally, the numbers that are part of the Fibonacci series are known as the Fibonacci numbers. Hence, the Fibonacci series helps us to verify if a given number is a Fibonacci number or not.

3. Binet’s Formula

Besides the general property, there’s another way to find the elements in the Fibonacci sequence. We can generate the elements in the Fibonacci series using the golden ratio method. Additionally, it’s popularly known as Binet’s formula. Therefore, the equation to find the $x^{th}$ element in the series is:

$[S_{x}=\frac{\varphi^{x}- \psi^{x}}{\varphi - \psi}]$

The variable $\varphi$ represents the golden ratio. Additionally, the variable $\psi$ is the conjugate of $\varphi$ . Therefore, we can express $\psi$ in form of $\varphi$ :

$[\psi = 1 - \varphi]$

Therefore, we can simplify Binet’s formula:

$[S_{x}=\frac{\varphi^{x}- (1 - \varphi)^{x}}{2\varphi - 1}]$

Moreover, the golden ration $\varphi$ can be expressed as:

$[\varphi=\frac{1+\sqrt{5}}{2}\simeq 1.618034, (1 - \varphi) \simeq 0.618034]$

Hence, the final equation is:

$[S_{x}=\frac{1.618034^{x}-0.618034^{x}}{\sqrt{5}}]$

Now, let’s verify this formula. Therefore, we’ll calculate some elements from the Fibonacci series and compare them with the Fibonacci series presented in the previous section. Let’s check for x = 5:

$[S_{5}=\frac{1.618034^{5}-0.618034^{5}}{\sqrt{5}}=4.919349\simeq5]$

Next, let’s set to 6:

$[S_{6}=\frac{1.618034^{6}-0.618034^{6}}{\sqrt{5}}=8.000000\simeq8]$

Finally, we set x = 7:

$[S_{7}=\frac{1.618034^{7}-0.618034^{7}}{\sqrt{5}}=12.969194\simeq13]$

Hence, as we can see using Binet’s formula, we can generate the elements of the Fibonacci series.

4. Approach for Checking a Fibonacci Number

As of now, we know how to generate the elements in the Fibonacci series. Now let’s discuss how to check whether a given number is a Fibonacci number or not. First, let’s look at the flowchart:

fib check

Initially, we input a number to start the checking process. In the next step, we compute two variables A_1 and A_2 :

$[A_1=5 n^{2}+4, A_2=5 n^{2}-4]$

Additionally, we check if any of them is a perfect square or not. In mathematics, a number is a perfect square if we can express it as a product of two equal integers. A number is a perfect square if $q=\sqrt{p}$ and $\quad q^2 ==p$ .

Therefore, in order to check if A_1 or A_2 is a perfect square or not, we compute B_1 and B_2 . Finally, the given number is a Fibonacci number, if at least one of A_1 or A_2 is a perfect square.

5. Pseudocode

Now let’s take a look at the pseudocode:

algorithm CheckIfFibonacci(n):
    // INPUT
    //    n = the input number
    // OUTPUT
    //    "Yes", if n is a Fibonacci number
    //    "No", if n is not a Fibonacci number

    A1 <- 5 * n^2 + 4
    A2 <- 5 * n^2 - 4

    B1 <- sqrt(A1)
    B2 <- sqrt(A2)

    if (B1^2 = A1) or (B2^2 = A2):
        return "Yes"
    else:
        return "No"

Initially, we take a given number as an input, and the pseudocode returns whether the number is a Fibonacci or not. Let’s analyze the time complexity of the pseudocode. In this pseudocode, we can only input a single number. Hence, both time and space complexity are ${\mathcal{O}(1)}$ . Moreover, if we want to input an array and the total number of elements in the array is $\mathbf{N}$ , the time complexity would be ${\mathbf{\mathcal{O}(N)}}$ .

6. Validation of Pseudocode

Let’s verify the pseudocode with some examples. Let’s take n = 5 as input and run the pseudocode:

$[A_1=5(5*5)+4=129, A_2=5(5*5)-4=121, B_1= \sqrt{A_1} = \sqrt{129} =11.36, B_2= \sqrt{A_2} = \sqrt{121} =11]$

In this example as we can see $B_2^{2} = A_2$ . Hence, the input number 5 is a Fibonacci number. Let’s take another example. In this case, the given input number is 7. The number 7 isn’t part of the Fibonacci series. Hence, it’s not a Fibonacci number. Let’s run the pseudocode and verify it:

$[A_1=5(7*7)+4=249, A_2=5(7*7)-4=241, B_1= \sqrt{A_1}= \sqrt{249} =15.78, B_2= \sqrt{A_2} = \sqrt{241}=15.52]$

Here, neither $B_1^{2} = A_1$ nor $B_2^{2} = A_2$ . Both 249 and 241 are not perfect squares. Therefore, the given input $\mathbf{7}$ is not a Fibonacci number.

7. Applications

The Fibonacci series and numbers are used in several applications in the field of computer science and mathematics. In computer science, the Fibonacci numbers are used in lossy compression in audio file format, binary tree representation, Fibonacci heap data structure, Fibonacci cube graph, sorting algorithms, the golden-section search, pseudorandom number generators.

In the mathematics field, many important applications, including optimization method, obtaining the common divisors, number game prediction, dynamic integer generation, use the Fibonacci numbers.

Other fields like high energy physics, quantum mechanics, cryptography utilize the Fibonacci series in various applications.

8. Summary

In this tutorial, we discussed the Fibonacci series and numbers. We talked about two methods to generate the Fibonacci numbers in the Fibonacci series with numerical examples.

Finally, we presented pseudocode for testing a given number is a Fibonacci number or not. We validated the pseudocode with examples.

Persistence

REST

Security