See https://algoritmim.co.il/interview-practice/fibonacci-sum/

fibinerator.py

class Fibinerator:
    def __init__(self, init_vals=(0, 1)):
        self._left, self._current = init_vals
        self._right = 0
        self.prev()
        self.prev()

    def next(self):
        self._left = self._current
        self._current = self._right
        self._right = self._left + self._current
        return self._current

    @property
    def current(self):
        return self._current

    def prev(self):
        self._right = self._current
        self._current = self._left
        self._left = self._right - self._current
        return self._current


def fibsum(n):
    fibi = Fibinerator()
    while fibi.next() <= n:
        pass
    result = 0
    remain = n
    while remain > 0:
        factor = remain // fibi.prev()
        result += factor
        remain -= factor * fibi.current
        if factor > 0:
            print(f'{factor} * {fibi.current}')
    return result


def _run_fibsum(n):
    print(f'fibsum({n}) == {fibsum(n)}')
    print('-' * 50)


def _test_fibinator(n):
    fibi = Fibinerator()
    assert [fibi.next() for _ in range(n)][:n - 1] == list(reversed([fibi.prev() for _ in range(n - 1)]))


if __name__ == '__main__':
    _test_fibinator(20)
    _run_fibsum(10)
    _run_fibsum(42)
    _run_fibsum(58)
    _run_fibsum(100)

  
# Output:
# =======
#
# 1 * 8
# 1 * 2
# fibsum(10) == 2
# --------------------------------------------------
# 1 * 34
# 1 * 8
# fibsum(42) == 2
# --------------------------------------------------
# 1 * 55
# 1 * 3
# fibsum(58) == 2
# --------------------------------------------------
# 1 * 89
# 1 * 8
# 1 * 3
# fibsum(100) == 3
# --------------------------------------------------