## Recognizing Fibonacci Numbers

### April 20, 2018

We have a simple exercise for a Friday afternoon:

Write a program that determines if an input number

nis 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.

Advertisements

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

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

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]

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

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

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.

A Haskell version.

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

codepad link –

http://codepad.org/8dlred0k

Python Code —>

import math

num = input()

num = float(num)

n1 = 5

numnum – 4n2 = 5

numnum + 4def checksqr(N): #function for perfect sqaure

r1 = checksqr(n1)

r2 = checksqr(n2)

if(r1 ==0) or (r2==0):

print(“Fibonacci”)

else:

print(“Not Fibonacci”)

In Ruby using simple method.

Outputs:

0 ✅

1 ✅

2 ✅

3 ✅

4 ❌

5 ✅

6 ❌

7 ❌

8 ✅

9 ❌

10 ❌

11 ❌

12 ❌

13 ✅

14 ❌

15 ❌

16 ❌

17 ❌

18 ❌

19 ❌

20 ❌

21 ✅

Here’s a solution in C using GMP.

Example Usage: