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)

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]

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)

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

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)

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]