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: EASY
Tags: Mathematics

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):
	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, 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 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