fibonacci.py

View source code here on GitHub!

Includes

python.src.lib.fibonacci.fib() → Iterator[int]

This generator goes through the fibonacci sequence

python.src.lib.fibonacci.fib_by_3(start_index: int = 0) → Iterator[int]

This generator goes through the fibonacci sequence skipping by 3s. This works because:

F[n] = F[n-1]          + F[n-2]
F[n] = F[n-2] + F[n-3] + F[n-2]
F[n] = 2 * F[n-2]            + F[n-3]
F[n] = 2 * (F[n-3] + F[n-4]) + F[n-3]
F[n] = 3 * F[n-3] + 2 * F[n-4]
F[n] = 3 * F[n-3] + F[n-4] + F[n-5] + F[n-6]
F[n] = 4 * F[n-3]                   + F[n-6]

 1from typing import Iterator
 2
 3from .iters import consume
 4
 5
 6def fib() -> Iterator[int]:
 7    """This generator goes through the fibonacci sequence"""
 8    a, b = 0, 1
 9    while True:
10        yield b
11        a, b = b, a + b
12
13
14def fib_by_3(start_index: int = 0) -> Iterator[int]:
15    """This generator goes through the fibonacci sequence skipping by 3s. This works because:
16
17    .. code-block:: python
18
19      F[n] = F[n-1]          + F[n-2]
20      F[n] = F[n-2] + F[n-3] + F[n-2]
21      F[n] = 2 * F[n-2]            + F[n-3]
22      F[n] = 2 * (F[n-3] + F[n-4]) + F[n-3]
23      F[n] = 3 * F[n-3] + 2 * F[n-4]
24      F[n] = 3 * F[n-3] + F[n-4] + F[n-5] + F[n-6]
25      F[n] = 4 * F[n-3]                   + F[n-6]
26    """
27    orig = fib()
28    a = 0
29    consume(orig, start_index)
30    next(orig)  # start + 1
31    next(orig)  # start + 2
32    b = next(orig)  # start + 3
33    del orig
34    yield a
35    while True:
36        yield b
37        a, b = b, a + b * 4

Tags: python-iterator, fibonacci-number