Function to check whether a number is a Fibonacci number or not?

Question

I've made a program which takes number of test cases as input and for each test case, it needs a number as input. Finally it checks whether the numbers you have entered are fibonacci numbers or not and prints accordingly. I've had no problems running it on my PC.But when i upload it to CodeChef.com(where i saw this quesion), it shows runtime error. Any help is appreciated and as i'm a noob my code might look lengthy ., any modifications are welcome.Thanks!

Here's my code:

def isperfect(n):
    import math
    if n < 0:
        print("No Solution")
        return False
    else:
        test = int(math.sqrt(n))
    return test*test == n
test_cases = int(input())
count = 0
store = []
while count < test_cases:
    x = int(input())
    store.append(x)
    count += 1
for each_item in store:
    assert isinstance(each_item, int)
    s1 = 5*each_item*each_item-4
    s2 = 5*each_item*each_item+4
    if(isperfect(s1) == True or isperfect(s2) == True):
        print("YES")
    else:
        print("NO")

Answer 1

This is the most elegant solution i've encountered:

def is_fibonacci(n):
    phi = 0.5 + 0.5 * math.sqrt(5.0)
    a = phi * n
    return n == 0 or abs(round(a) - a) < 1.0 / n

The code is not mine, was posted by @sven-marnach. The original post: check-input-that-belong-to-fibonacci-numbers-in-python

Answer 2

The runtime error is apparently due to an exception, but Codechef does not provide any more information. It could be various things including divide by zero, memory exhaustion, assertion failure, ...

Although your program works for many common numbers, it doesn't handle all the inputs that the Codechef constraints allow. In particular, the number to be tested can have up to 1000 digits in it. If you try a large input like a 1000-digit number, you'll find it fails. First it fails because of your assert isinstance(each_item, int); a number of 12 digits or more is not of type int. You can just remove the assertion. The next failure occurs because you are using the floating point sqrt routine, and that requires the integer to be converted into floating point. Python can handle very long integers, but the floating point representation is more limited in its precision, and cannot handle 1000 digit integer conversions. That's harder to fix, but can be done. See this ActiveState recipe for an all-integer solution for square root.

Answer 3

I've figured that this can be done by using Newton- Raphson method, i have replaced the code in the function isperfect() with Newton-Raphson formula code, removed assertion and it worked. Thanks for all your help.

Here's the final code:

def isperfect(n):
    x = n
    y = (x + n // x) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x*x == n
test_cases = int(input())
count = 0
store = []
while count < test_cases:
    x = int(input())
    store.append(x)
    count += 1
for each_item in store:
    s1 = 5*each_item*each_item-4
    s2 = 5*each_item*each_item+4
    if(isperfect(s1) == True or isperfect(s2) == True):
        print("YES")
    else:
        print("NO")

Answer 4

This is going to be a very efficient way of doing it.

In [65]:
import scipy.optimize as so
from numpy import *

In [66]:
def fib(n):
    s5=sqrt(5.)
    return sqrt(0.2)*(((1+s5)/2.)**n-((1-s5)/2.)**n)
def apx_fib(n):
    s5=sqrt(5.)
    return sqrt(0.2)*(0.5*(1+s5))**n
def solve_fib(f):
    _f=lambda x, y: (apx_fib(x)-y)**2
    return so.fmin_slsqp(_f,0., args=(f,),iprint=0)
def test_fib(fibn):
    if fibn<1:
        print 'No, it is not'
    else:
        n=int(round(solve_fib(fibn)))
        if int(round(fib(n)))==int(fibn):
            print 'Yes, it is. (%d)'%n
        else:
            print 'No, it is not'

In [67]:
asarray(fib(arange(1,20)), dtype='int64')
Out[67]:
array([   1,    1,    2,    3,    5,    8,   13,   21,   34,   55,   89,
        144,  233,  377,  610,  987, 1597, 2584, 4181])

In [68]:
test_fib(34)
Yes, it is. (9)

In [69]:
test_fib(4181)
Yes, it is. (19)

In [70]:
test_fib(4444)
No, it is not

Answer 5

Try this function:

def isfib(number):
    num1 = 1
    num2 = 1
    while True:
        if num2 <= number:
            if num2 == number:
                return True
            else:
                tempnum = num2
                num2 += num1
                num1 = tempnum
        else:
            return False

Here's how it works:

1. Set num1 and num2 to 0.
2. If num2 isn't less than or equal to the number return False.
3. If num2 is equal to the number return True.
4. Set add num1 to num2, set num1 to num2's original value and go back to step 2.

Answer 6

Fairly simple and efficient way of doing it

def isInFib(n):
    if n == 0: return False
    elif n == 1: return True
    else:
        A = 1
        B = 1
        FLIP = True
        while(True):
            new = A + B
            if new > n: return False
            elif new == n: return True
            else:
                if(FLIP):
                    A = new 
                    FLIP = not FLIP
                else:
                    B = new
                    FLIP = not FLIP

Explanation of Algorithm

I first check if my input is equal to 0 or 1, and return appropriate.

If my input is greater than 1, we go into the else, infinite loop.

A and B represent the last two previous numbers in the sequence. We add A and B to get new, the current Fibonacci number.

We check if new is equal to our input number, if that's true we return true, we are done and complete the function.

If it's greater, that means our number is not in the Fibonacci sequence, since we have surpassed it.

if it's less, we need to keep going! and this is where I think it get's confusing to explain. I want to set up A or B as my current fibonacci sequence number (new), but I have make sure that I keep switching between them, since I don't want one to get left behind. Fibonacci sequence takes the previous 2 numbers and adds them together. I want A and B to be my last two previous sums.

I'll use an example

1,1,2,3,5,8,13

A and B are initially 1. So new is equal to 2 first. I then check if I'm over my input number or equal to it. But if my input number is less. I want to keep going.

I want A to equal new (value = 2) then, before we get to our next iteration of the while loop. So that new will equal 2 + 1 as A + B on the next iteration.

But, then THE next iteration of the loop, I want to set B as 3, and I want to leave A being equal to 2. So I have to keep switching between putting the current fibonacci number I'm at, in A or B. And that's why I have the flip logic! It just keeps switching between True and False.

Answer 7

num=int(input("Enter a number : "))

n1=0
n2=1
i=1
    lst=[]
    lst.append(n1)
    lst.append(n2)

while i<num-1:
    n3=n1+n2
    n1=n2
    n2=n3
    lst.append(n3)
    i=i+1

for i in lst:
    if (num == i):
        print("Fibonacci number")
        break
else:
    print("Not fibonacci")

Answer 8

def isfib(number):
    num1 = 0
    num2 = 1
    while True:
        if num2 <= number:
            if num2 == number:
                return True
            else:
                tempnum = num2
                num2 += num1
                num1 = tempnum
        else:
            return False
n=int(input())
number=n
fibonacci=isfib(number)
if (fibonacci):
    print("true")
elif n==0:
    print("true")
else:
    print("false")