## Recognizing Fibonacci Numbers

### April 20, 2018

One approach is to enumerate the Fibonacci numbers until you reach the target, then compare:

(define (fibonacci? x) (if (< x 1) #f (let loop ((prev 1) (fib 1)) (if (< fib x) (loop fib (+ fib prev)) (= fib x)))))

> (fibonacci? 13) #t > (fibonacci? 15) #f

If you know number theory, you know that a number *n*is a Fibonacci number if and only if one of 5*n*² ± 4 is a perfect square:

(define (fibonacci? x) (let ((5xx (* 5 x x))) (or (square? (+ 5xx 4)) (square? (- 5xx 4)))))

> (fibonacci? 13) #t > (fibonacci? 15) #f

Isn’t number theory grand? You can run the program at https://ideone.com/XqUP3W

Advertisements

Pages: 1 2

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: