Fibonacci Numbers

Let's begin by clarifying what the Fibonacci series is: it’s a sequence where each number is the sum of the two preceding ones, with the first two numbers defined as 0 and 1.

The initial numbers in the series are: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233.

The Obvious Solution

The simplest method for checking if a number belongs to the series is to generate the series up to that number. Here’s an example function:

const isFibonacci = (n) => {

let a = 0;

let b = 1;

if (n === a || n === b) {

return true;

}

let c = a + b;

while (c <= n) {

if (c === n) return true;

a = b;

b = c;

c = a + b;

}

return false;

};

However, this approach becomes inefficient as the number increases, resulting in longer calculation times. While it works, it isn't practical for real-world applications.

A Better Solution

To enhance efficiency, we can explore the properties of the Fibonacci series. According to Wikipedia, French mathematician Jacques Philippe Marie Binet developed a formula that can compute the nth Fibonacci number:

F(n) = frac{(phi^n - (1 - phi)^n)}{sqrt{5}}

where F(n) is the nth Fibonacci number and ? (phi) represents the golden ratio, approximately 1.61803398875.

Here’s a JavaScript function that uses Binet’s formula to compute the nth Fibonacci number:

const fibonacci = (n) => {

const phi = (1 + Math.sqrt(5)) / 2;

return Math.round(

(Math.pow(phi, n + 1) - Math.pow(1 - phi, n + 1)) / Math.sqrt(5)

);

};

Alternatively, you can use this version of the function:

const fibonacci = (n) => {

const x = n - 1;

const sqr = 5 ** 0.5;

const a = (1 + sqr) ** x;

const b = (1 - sqr) ** x;

const c = 2 ** x * sqr;

return Math.round((a - b) / c);

};

This function receives a single argument n, which represents the index of the Fibonacci number to compute, returning the corresponding Fibonacci number. For example, to compute the 8th Fibonacci number, you would call the function as follows:

console.log(fibonacci(8)); // Output: 13

From Binet’s formula, we can derive a method to determine if a number belongs to the Fibonacci sequence:

If quad 5N^2 + 4 quad text{or} quad 5N^2 - 4 quad text{is a perfect square, then the number is in the Fibonacci sequence.}

Using this definition, I can create the function isFibonacci(n):

const isFibonacci = (n) => {

const x1 = 5 * n ** 2 + 4;

const x2 = 5 * n ** 2 - 4;

return Number.isInteger(Math.sqrt(x1)) || Number.isInteger(Math.sqrt(x2));

};

This function checks if a given number n is a Fibonacci number, returning true if it is, and false otherwise. For example, to check if 13 is a Fibonacci number, you can call it like this:

console.log(isFibonacci(13)); // Output: true

A more concise version of the same function can be written as follows:

const isFibonacci = (n) =>

Number.isInteger((5 * n ** 2 + 4) ** 0.5) ||

Number.isInteger((5 * n ** 2 - 4) ** 0.5);

How to Find the Position of a Number in the Fibonacci Series?

To summarize, we've created a JavaScript function to calculate the nth Fibonacci number (fibonacci(n)) and another to verify if a number belongs to the Fibonacci series (isFibonacci(n)). Now we need to develop a function to determine the position of a Fibonacci number within the sequence.

The simplest method, though resource-intensive, is as follows:

const fibonacciPosition = (n) => {

let position = 0;

let current = 0;

let next = 1;

while (current < n) {

position++;

let temp = current;

current = next;

next = temp + current;

}

if (current === n) {

return position + 1;

} else {

return -1;

}

};

Using Binet’s formula again, we can create a more efficient function:

const fibonacciPosition = (n) => {

const phi = (1 + Math.sqrt(5)) / 2;

const position = Math.log(n * 5 ** 0.5 + 0.5) / Math.log(phi);

return Math.floor(position) + 1;

};

However, the initial numbers in the series require special handling as they are part of the Fibonacci series definition. Therefore, we can add conditions at the beginning:

const fibonacciPosition = (n) => {

if (n === 0) return 1;

if (n === 1) return 2;

const phi = (1 + Math.sqrt(5)) / 2;

const position = Math.log(n * 5 ** 0.5 + 0.5) / Math.log(phi);

return Math.floor(position) + 1;

};

Lastly, we should check whether the number is a Fibonacci number before performing calculations:

const fibonacciPosition = (n) => {

if (!isFibonacci(n)) return -1;

if (n === 0) return 1;

if (n === 1) return 2;

const phi = (1 + Math.sqrt(5)) / 2;

const position = Math.log(n * 5 ** 0.5 + 0.5) / Math.log(phi);

return Math.floor(position) + 1;

};

With this, we have wrapped up the topic.

Before I conclude, I’d like to note that in the functions, I added 1 to the position (in both fibonacciPosition(n) and fibonacci(n)) to assign the first position an index of 1. However, if we intend to work with arrays where the first position has an index of 0, it would be simpler to omit this adjustment.

Thank you for reading! Stay tuned for more insights.

Don’t miss my next article — sign up for my Medium email list.

Join Medium with my referral link — Samuele Read every story from Samuele (and thousands of other writers on Medium). Not a Medium member? Join here and a piece of…

el3um4s.medium.com

Originally published at https://blog.stranianelli.com on December 21, 2022.

More content at **PlainEnglish.io*. Sign up for our free weekly newsletter. Follow us on Twitter, LinkedIn, YouTube, and Discord.*

Interested in scaling your software startup? Check out **Circuit*.*