The Fibonacci numbers are the numbers in the following integer sequence (Fn):
>0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...

such as 
>F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1.

Given a number, say prod (for product), we search two Fibonacci numbers F(n) and F(n+1) verifying 
>F(n) * F(n+1) = prod.

Your function productFib takes an integer (prod) and returns
an array: 
```
[F(n), F(n+1), true] or {F(n), F(n+1), 1} or (F(n), F(n+1), True)
```
depending on the language if F(n) * F(n+1) = prod.

If you don't find two consecutive F(m) verifying `F(m) * F(m+1) = prod`you will return
```
[F(m), F(m+1), false] or {F(n), F(n+1), 0} or (F(n), F(n+1), False)
```
F(m) being the smallest one such as `F(m) * F(m+1) > prod`.


### Some Examples of Return:
(depend on the language)

```
productFib(714) # should return (21, 34, true), 
                # since F(8) = 21, F(9) = 34 and 714 = 21 * 34

productFib(800) # should return (34, 55, false), 
                # since F(8) = 21, F(9) = 34, F(10) = 55 and 21 * 34 < 800 < 34 * 55
-----
productFib(714) # should return [21, 34, true], 
productFib(800) # should return [34, 55, false], 
-----
productFib(714) # should return {21, 34, 1}, 
productFib(800) # should return {34, 55, 0},        
-----
productFib(714) # should return {21, 34, true}, 
productFib(800) # should return {34, 55, false}, 
```

### Note:

- You can see examples for your language in "Sample Tests".

Difficulty: introductory

Starter code:

def productFib(prod):
	

Solutions:
def productFib(prod):
  a, b = 0, 1
  while prod > a * b:
    a, b = b, a + b
  return [a, b, prod == a * b]

def productFib(prod):
    a,b = 0,1
    while a*b < prod:
        a,b = b, b+a
    return [a, b, a*b == prod]

def productFib(prod):
    a, b = 0, 1
    rez = 0
    while rez < prod:
        a, b = b, a + b
        rez = a*b
    return [a, b, rez == prod]

def productFib(prod):
    func = lambda a, b: func(b, a+b) if a*b < prod else [a, b, a*b == prod]
    return func(0, 1)

def productFib(prod):
    a, b = 0, 1
    while a*b < prod:
        a, b = b, a+b
    return [a, b, a*b == prod]

def productFib(prod, f1=0, f2=1):
    return [f1, f2, True] if prod == f1 * f2 else [f1, f2, False] if prod < f1 * f2 else productFib(prod, f2, f1+f2)

def productFib(prod):
    fib1, fib2 = 0, 1
    while prod > fib1*fib2:
        fib2, fib1 = fib1 + fib2, fib2
    return [fib1, fib2, prod == fib1*fib2]


def productFib(prod):
    num = 1
    prev = 0
    while prev * num < prod:
        temp = num + prev
        prev = num
        num = temp
    return [prev, num, prev * num == prod]

from bisect import *

def genProdFib():
    a,b = 0,1
    while 1:
        yield a*b,b
        a,b = b,a+b

GEN,PROD = genProdFib(), [(-1,0)]

def productFib(p):
    def formatOut(pp,b): return [pp//b, b, pp==p]
    
    if PROD[-1][0]>p:
        return formatOut(*PROD[bisect(PROD, (p,0))])
    
    while PROD[-1][0]<p:
        PROD.append(next(GEN))
    return formatOut(*PROD[-1])

def productFib(prod):
    for x, y in fib():
        if x * y == prod:
            return [x, y, True]
        elif x * y > prod:
            return [x, y, False]

def fib():
    a, b = 0, 1
    while True:
        yield a, b
        a, b = b, a + b

def productFib(prod):
    n,n_1 = 0,1
    while True:
        if n*n_1==prod:
            return [n, n_1, True]
        elif n*n_1>prod:
            return [n,n_1, False]
        else:
            n, n_1 = n_1, n_1+n

def productFib(prod):
    i = 0
    j = 1
    while i * j < prod:
        i, j = j, i+j
    return [ i, j, i*j == prod ]


from bisect import bisect_left
def productFib(prod, fib=[0,1], prods=[0]):
    while prods[-1] < prod:
        fib.append(fib[-2]+fib[-1])
        prods.append(fib[-2]*fib[-1])
    i = bisect_left(prods, prod)
    return [fib[i], fib[i+1], prods[i]==prod]

def productFib(prod):
    a = 0
    b = 1
    while a * b < prod:
        a, b = b, a+b
    return [a, b, a*b == prod]


def productFibAux(current, nxt, prod):
    res = []
    while (current * nxt < prod):
            k = nxt
            nxt = nxt + current
            current = k
    if (prod == current * nxt):
        return [current, nxt, True]
    else:
        return [current, nxt, False]
    return res

def productFib(prod):
    return productFibAux(0, 1, prod)


from itertools import dropwhile


def fib_gen():
    a, b = 0, 1
    while True:
        yield a, b
        a, b = b, a + b


def productFib(p):
    i = dropwhile(lambda x: x[0]*x[1]<p, fib_gen())
    a, b = next(i)
    
    return [a, b, a*b==p]


def productFib(prod):
        if prod==0:
              return [0,1,True]
        a=1
        b=1
        for i in range(1,prod+1):
                c = a+b
                if a*b==prod:
                       return [a,b,True]
                elif a*b>prod:
                        return [a,b,False]
                a=b
                b=c

def productFib(prod):
    nums = [0,1]
    i = 0
    status = True
    while status:
        if nums[i]*nums[i+1] <= prod:
            nums.append(nums[i]+nums[i+1])
            i+=1
        else:
            status = False
    i = 0
    while i < len(nums):
        if nums[i]*nums[i+1] == prod:
            return [nums[i],nums[i+1],True]
        elif prod in range(nums[i-1]*nums[i],nums[i]*nums[i+1]):
            return [nums[i],nums[i+1],False]
        i+=1