Skip to content

Instantly share code, notes, and snippets.

@crunchie84
Created January 2, 2018 11:56
Show Gist options
  • Save crunchie84/c917b24fbc36f51bdf5549e6e8c58d40 to your computer and use it in GitHub Desktop.
Save crunchie84/c917b24fbc36f51bdf5549e6e8c58d40 to your computer and use it in GitHub Desktop.
Find fibonacci numbers using perfect square formula
/**
* The question may arise whether a positive integer x is a Fibonacci number. This is true if and only if one or both of 5x^{2}+4 or 5x^{2}-4 is a perfect square.
* https://en.wikipedia.org/wiki/Fibonacci_number#Recognizing_Fibonacci_numbers
*/
// the first 20 fibonacci numbers are found 0->6765
Array.from(generate(6765+1))
.map((i, idx) => ({number: i, isFibonacci: isFibonacciNumber(i)}))
.filter(kv => kv.isFibonacci)
.map((kv, index) => console.log(`found ${1+index}th fibonacci number: ${kv.number}`));
function isFibonacciNumber(n) {
return n == 0 ||
(n >= 0 && (isPerfectSquare(5 * n * n + 4) || isPerfectSquare(5 * n * n - 4)));
}
// perfect square - square root of given value is an integer number
function isPerfectSquare(value) {
const sqrt = Math.sqrt(value);
return (sqrt | 0) === sqrt;
}
function* generate(length) {
var idx = 0;
while(idx < length) {
yield idx++;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment