Check number is Fibonacci numbers or not
A simple way is to generate Fibonacci numbers until the generated number is greater than or equal to ‘n’. Following is an interesting property about Fibonacci numbers that can also be used to check if a given number is Fibonacci or not…
A simple way is to generate Fibonacci numbers until the generated number is greater than or equal to ‘n’. Following is an interesting property about Fibonacci numbers that can also be used to check if a given number is Fibonacci or not.
A number is Fibonacci if and only if one or both of ( 5*n2 + 4 ) or ( 5*n2 – 4 ) is a perfect square (Source: Wiki). Following is a simple program based on this concept.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
<?php $count = 0 ; $f1 = 0; $f2 = 1; echo '---- Correct Fibonacci series ----<br/>'; echo $f1." , "; echo $f2." , "; while ($count < 50 ) { $f3 = $f2 + $f1 ; echo $f3." , "; $f1 = $f2 ; $f2 = $f3 ; $count = $count + 1; } echo '<br/>---- Fibonacci series array with some wrong elements ----'; $aFabonacySeriesArray = [ 0 , 1 , 1 , 2 , 3 , 4, 5 , 6 , 8 , 12 , 13 , 16 , 21 , 34 , 55 , 89 , 144 , 233 , 377 , 610 , 987 , 1597 , 2584 , 4181 , 6765 , 10946 , 17711 , 28657 , 46368 , 75025 , 121393 , 196418 , 317811 , 514229 , 832040 , 1346269 , 2178309 , 3524578 , 5702887 , 9227465 , 14930352 , 24157817 , 39088169 , 63245986 , 102334155 , 165580141 , 267914296 , 433494437 , 701408733 , 1134903170 , 1836311903 , 2971215073 , 4807526976 , 7778742049 , 12586269025 , 20365011074 ]; var_dump($aFabonacySeriesArray); // Loop each number and check given number is Fibonacci or not foreach ( $aFabonacySeriesArray as $key => $value ) { echo isFibonacci( $value ) ? ( $value . ' - is a Fibonacci Number <br/>' ) : ( $value . ' - is a not Fibonacci Number <br/>' ); } function isPerfectSquare( $x ) { return gmp_perfect_square( ( string ) $x ); } // Returns true if n is a Fibinacci Number, else false function isFibonacci( $n ) { // n is Fibinacci if one of 5 * $n * $n + 4 or 5 * $n * $n - 4 or both // is a perferct square return isPerfectSquare( 5 * $n * $n + 4 ) || isPerfectSquare( 5 * $n * $n - 4 ); } ?> |
Output – #
—- Correct Fibonacci series —-
0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 , 89 , 144 , 233 , 377 , 610 , 987 , 1597 , 2584 , 4181 , 6765 , 10946 , 17711 , 28657 , 46368 , 75025 , 121393 , 196418 , 317811 , 514229 , 832040 , 1346269 , 2178309 , 3524578 , 5702887 , 9227465 , 14930352 , 24157817 , 39088169 , 63245986 , 102334155 , 165580141 , 267914296 , 433494437 , 701408733 , 1134903170 , 1836311903 , 2971215073 , 4807526976 , 7778742049 , 12586269025 , 20365011074 ,
—- Fibonacci series array with some wrong elements —-
array (size=56) 0 => int 0 1 => int 1 2 => int 1 3 => int 2 4 => int 3 5 => int 4 6 => int 5 7 => int 6 8 => int 8 9 => int 12 10 => int 13 11 => int 16 12 => int 21 13 => int 34 14 => int 55 15 => int 89 16 => int 144 17 => int 233 18 => int 377 19 => int 610 20 => int 987 21 => int 1597 22 => int 2584 23 => int 4181 24 => int 6765 25 => int 10946 26 => int 17711 27 => int 28657
0 – is a Fibonacci Number
1 – is a Fibonacci Number
1 – is a Fibonacci Number
2 – is a Fibonacci Number
3 – is a Fibonacci Number
4 – is a not Fibonacci Number
5 – is a Fibonacci Number
6 – is a not Fibonacci Number
8 – is a Fibonacci Number
12 – is a not Fibonacci Number
13 – is a Fibonacci Number
16 – is a not Fibonacci Number
21 – is a Fibonacci Number
34 – is a Fibonacci Number
55 – is a Fibonacci Number
89 – is a Fibonacci Number
144 – is a Fibonacci Number
233 – is a Fibonacci Number
377 – is a Fibonacci Number
610 – is a Fibonacci Number
987 – is a Fibonacci Number
1597 – is a Fibonacci Number
2584 – is a Fibonacci Number
4181 – is a Fibonacci Number
6765 – is a Fibonacci Number
10946 – is a Fibonacci Number
17711 – is a Fibonacci Number
28657 – is a Fibonacci Number
