Created
January 2, 2018 11:56
-
-
Save crunchie84/c917b24fbc36f51bdf5549e6e8c58d40 to your computer and use it in GitHub Desktop.
Find fibonacci numbers using perfect square formula
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* 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