Skip to content

Instantly share code, notes, and snippets.

@orens
Created Apr 28, 2021
Embed
What would you like to do?
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
# --------------------------------------------------
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment