## Recognizing Fibonacci Numbers

### April 20, 2018

We have a simple exercise for a Friday afternoon:

Write a program that determines if an input number n is a Fibonacci number.

Your task is to write a program that determines if a number is a Fibonacci number. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 9 Responses to “Recognizing Fibonacci Numbers”

1. Milbrae said

I found a nice hint here: https://www.geeksforgeeks.org/check-number-fibonacci-number/

```from math import sqrt

def issquare(n):
return int(sqrt(n))**2 == n

def isfib(n):
return issquare(5*n*n + 4) or issquare(5*n*n - 4)

if __name__ == "__main__":
data = [1,2,3,5,7,9,10,13,19,21,28,100]
for f in data:
print (str(f) + " -> Fibonacci = " + str(isfib(f)))
```

Sample output:
1 -> Fibonacci = True
2 -> Fibonacci = True
3 -> Fibonacci = True
5 -> Fibonacci = True
7 -> Fibonacci = False
9 -> Fibonacci = False
10 -> Fibonacci = False
13 -> Fibonacci = True
19 -> Fibonacci = False
21 -> Fibonacci = True
28 -> Fibonacci = False
100 -> Fibonacci = False

2. Zack said

Here is my implementation in Julia (not the best implementation but, hey, it’s Friday).

Functions:

function CreateFibonacciSequence(n::Int64)
if n == 1; return [n, n]; end
c = 3
Z = [1, 1]

``````while Z[end] < n
z = Z[end] + Z[end-1]
Z = vcat(Z, z)
end

return Z
``````

end

function IsFibonacci(n::Int64)
if n == 1; return true; end
F = CreateFibonacciSequence(n)
return F[end] == n
end

Testing:

IsFibonacci(14)
false

IsFibonacci(13)
true

IsFibonacci(1)
true

3. Zack said

Actually, I just realized that the c variable in the first function is redundant. Apologies for that…

4. chaw said

Here is a solution in standard (R7RS) Scheme that is similar to
@programmingpraxis’s solution but also works with the “negafibonacci”
extension of F_n for n < 0.

``` (import (scheme base) (scheme write) (only (srfi 1) iota every any) (srfi 8)) (define (perfect-square? n) (and (not (negative? n)) (integer? n) (receive (root rem) (exact-integer-sqrt n) (zero? rem)))) ;; This version works for x = F_n with n<0 as well. ;; For the reasoning, see the proof [Gessel, Ira (October 1972), ;; "Fibonacci is a Square", The Fibonacci Quarterly, 10 (4): 417-19]. (define (fib? x) (let ((t (* 5 (square x)))) (or (perfect-square? (+ t 4)) (and (>= x 0) (perfect-square? (- t 4)))))) ;;; Testing... ;; The n'th Pingala-Fibonaaci number, for integer n (including ;; extension to negative n). (define (fib n) (cond ((zero? n) 0) ((negative? n) ((if (even? n) - +) (fib (- n)))) (else (let loop ((i 1) (a 0) (b 1)) (if (>= i n) b (loop (+ i 1) b (+ a b))))))) (define (test) (and (every fib? (map fib (iota 21 -10))) (not (any fib? (map - (map fib (iota 10 -3 -2))))))) (display (test)) (newline) ```

5. Globules said

```import Math.NumberTheory.Powers.Squares (isSquare)
import Text.Printf (PrintfArg, printf)

-- True if and only if the argument is a Fibonacci number.  This test is from
-- the Wikipedia article on Fibonacci numbers.
isFib :: Integral a => a -> Bool
isFib n = let s = 5 * n * n in isSquare (s + 4) || isSquare (s - 4)

testIsFib :: (Integral a, PrintfArg a) => a -> IO ()
testIsFib n = printf "%-5s %d\n" (show \$ isFib n) n

main :: IO ()
main = do
mapM_ testIsFib [0 .. 13 :: Int]

-- http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibtable.html
let fib300 :: Integer
fib300 = 222232244629420445529739893461909967206666939096499764990979600
testIsFib fib300
testIsFib (fib300 + 1)
```
```\$ ./isfib
True  0
True  1
True  2
True  3
False 4
True  5
False 6
False 7
True  8
False 9
False 10
False 11
False 12
True  13
True  222232244629420445529739893461909967206666939096499764990979600
False 222232244629420445529739893461909967206666939096499764990979601
```
6. Paul said

@Milbrae: your implementation does not really work for for large numbers as issquare is not correct for large numbers. Fibonacci number 76 is 5527939700884757. For this number and (almost) all next numbers your method fails. If you use an issquare function based on an isqrt method for integer numbers, than it works. Below is an example:

```def isqrt(n):
if n < 0:
raise ValueError("x must be non-negative")
if n == 0:
return 0
x = 2 ** ((n.bit_length() - 1) // 2 + 1)    # x > sqrt(n)
y = x - 1
while y < x:
x = y
y = (x + n//x) // 2
return x

# Quadratic residues mod to filter out 99% of all cases
d64 = frozenset((0, 1, 4, 9, 16, 17, 25, 33, 36, 41, 49, 57))
d63 = frozenset((0, 1, 4, 7, 9, 16, 18, 22, 25, 28, 36, 37, 43, 46, 49, 58))
d25 = frozenset((0, 1, 4, 6, 9, 11, 14, 16, 19, 21, 24))
d31 = frozenset((0, 1, 2, 4, 5, 7, 8, 9, 10, 14, 16, 18, 19, 20, 25, 28))
d23 = frozenset((0, 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18))
d19 = frozenset((0, 1, 4, 5, 6, 7, 9, 11, 16, 17))
d17 = frozenset((0, 1, 2, 4, 8, 9, 13, 15, 16))
d11 = frozenset((0, 1, 3, 4, 5, 9))

def is_square(n):
return (n % 64 in d64 and n % 63 in d63 and n % 25 in d25 and
n % 31 in d31 and n % 23 in d23 and n % 19 in d19 and
n % 17 in d17 and n % 11 in d11 and isqrt(n)**2 == n)
```

Python Code —>

import math
num = input()
num = float(num)

n1 = 5numnum – 4
n2 = 5numnum + 4

def checksqr(N): #function for perfect sqaure

``````sq = math.sqrt(N)
flr = math.floor(sq)
res = sq - flr
return res
``````

r1 = checksqr(n1)
r2 = checksqr(n2)

if(r1 ==0) or (r2==0):
print(“Fibonacci”)
else:
print(“Not Fibonacci”)

8. V said

In Ruby using simple method.

```
def fib?(n)
return false if n < 0
return true if n == 0

prev = 0
curr = 1

loop do
temp = prev + curr
prev = curr
curr = temp
return true if curr == n
return false if curr > n
end
end

# Test

(0..21).each do |n|
r = fib?(n) ? "✅" : "❌"
puts "#{n} #{r}"
end

```

Outputs:

0 ✅
1 ✅
2 ✅
3 ✅
4 ❌
5 ✅
6 ❌
7 ❌
8 ✅
9 ❌
10 ❌
11 ❌
12 ❌
13 ✅
14 ❌
15 ❌
16 ❌
17 ❌
18 ❌
19 ❌
20 ❌
21 ✅

9. Daniel said

Here’s a solution in C using GMP.

```/* fibonacci.c */

// Build
//   \$ gcc -o fibonacci fibonacci.c -lgmp

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

#include <gmp.h>

bool calc_is_fibonacci(const mpz_t n) {
mpz_t x;
mpz_init(x);
mpz_set(x, n);
mpz_pow_ui(x, x, 2);
mpz_mul_ui(x, x, 5);
bool output = false;
output = mpz_perfect_square_p(x);
if (!output) {
mpz_sub_ui(x, x, 8);
output = mpz_perfect_square_p(x);
}
mpz_clear(x);
return output;
}

int main(int argc, char* argv[]) {
if (argc < 2) {
fprintf(stderr, "Usage: fibonacci <INT> [<INT> ...]\n");
return EXIT_FAILURE;
}
for (size_t i = 1; i < argc; ++i) {
mpz_t n;
mpz_init(n);
mpz_set_str(n, argv[i], 10);
bool is_fib = calc_is_fibonacci(n);
gmp_printf("%Zd,%d\n", n, is_fib);
mpz_clear(n);
}
return EXIT_SUCCESS;
}
```

Example Usage:

```\$ ./fibonacci {0..20}
0,1
1,1
2,1
3,1
4,0
5,1
6,0
7,0
8,1
9,0
10,0
11,0
12,0
13,1
14,0
15,0
16,0
17,0
18,0
19,0
20,0
```