In [21]:
import numpy as np

# a class for finding the last Fibonacci number efficiently
# this consumes a lot of memory if the queried number is large
class Fibonacci:

def __init__(self):
self.arr = [0, 1]

def find_previous(self, n):
if n > self.arr[-1]:
while n > self.arr[-1]:
self.arr.append(self.arr[-1] + self.arr[-2])

# using side='right' so that if n is Fibonacci, we return n
return self.arr[np.searchsorted(self.arr, n, side='right') - 1]

def show(self):
print(self.arr)

In [26]:
fibo = Fibonacci()
print('the Fibonacci number before 30 is', fibo.find_previous(30))
print('the Fibonacci number before 21 is', fibo.find_previous(21))
print('the Fibonacci number before 20 is', fibo.find_previous(20))
print('all Fibonacci numbers in the list:')
fibo.show()

the Fibonacci number before 30 is 21
the Fibonacci number before 21 is 21
the Fibonacci number before 20 is 13
all Fibonacci numbers in the list:
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

In [31]:
def find_representation(n):
prev_fibo = fibo.find_previous(n)
if prev_fibo == n:
# n is Fibonacci number
return [0, n]
else:
return [prev_fibo] + find_representation(n - prev_fibo)

In [43]:
def verify_result(n):
repre = find_representation(n)
# sort result for pretty-printing
repre.sort()
the_sum = np.sum(repre)
# format output for the right hand side
the_rhs = '+'.join(map(repr, repre))
print('{}={} (the sum is {})'.format(n, the_rhs, the_sum))

In [49]:
verify_result(1)
verify_result(21)
verify_result(30)
verify_result(1000)
verify_result(10000)
verify_result(30000)
verify_result(300000)

1=0+1 (the sum is 1)
21=0+21 (the sum is 21)
30=0+1+8+21 (the sum is 30)
1000=0+13+987 (the sum is 1000)
10000=0+2+5+34+610+2584+6765 (the sum is 10000)
30000=0+34+89+233+987+28657 (the sum is 30000)
300000=0+2+8+34+89+377+987+2584+6765+17711+75025+196418 (the sum is 300000)

In [51]:
print('Fibonacci numbers in the list now:')
fibo.show()

Fibonacci numbers in the list now:
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811]

In [ ]: