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.

Posted by programmingpraxis

Filed in Exercises

9 Comments »

9 Responses to “Recognizing Fibonacci Numbers”

Milbrae said
April 20, 2018 at 9:24 AM
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
Zack said
April 20, 2018 at 10:14 AM
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
Zack said
April 20, 2018 at 10:15 AM
Actually, I just realized that the c variable in the first function is redundant. Apologies for that…

chaw said

April 20, 2018 at 5:09 PM

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)

Globules said

April 21, 2018 at 4:37 AM

A Haskell version.

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

Paul said

April 21, 2018 at 3:54 PM

@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)

Mind bending enigma said
April 22, 2018 at 2:42 AM
codepad link –
http://codepad.org/8dlred0k

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”)

V said

April 22, 2018 at 11:48 AM

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 ✅

Daniel said

May 8, 2018 at 12:22 AM

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;
  mpz_add_ui(x, x, 4);
  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

Programming Praxis