fibonacci_functions.py

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

"""
fibonacci_functions.py

Checks some formulas on Fibonacci function and sums.

:license: GPLv3 --- Copyright (C) 2021 Olivier Pirson
:author: Olivier Pirson --- http://www.opimedia.be/
:version: October 9, 2021
"""

import sys

from typing import Callable


def f(k: int, alpha: int, beta: int) -> int:
    """
    Returns f(k).

    Where f is such that:
    f(0) = alpha
    f(1) = beta
    forall n: f(n + 2) = f(n + 1) + f(n)
    """
    assert k >= 0

    f_i = alpha  # f(i)
    f_i_1 = beta  # f(i + 1)
    for _ in range(k):
        f_i, f_i_1 = f_i_1, f_i_1 + f_i

    return f_i


def fibo(k: int) -> int:
    """
    Returns the number of Fibonacci F_k.

    https://oeis.org/A000045
    """
    if k < 0:
        return fibo(-k) * (-1)**(1 - k % 2)

    f_i_1 = 1  # F_{i-1}
    f_i = 0  # F_i
    for _ in range(k):
        f_i_1, f_i = f_i, f_i + f_i_1

    return f_i


def lucas(k: int) -> int:
    """
    Returns the number of Lucas L_k.

    https://oeis.org/A000032
    """
    if k < 0:
        return fibo(-k) * (-1)**(1 - k % 2)

    l_i_1 = -1  # L_{i-1}
    l_i = 2  # L_i
    for _ in range(k):
        l_i_1, l_i = l_i, l_i + l_i_1

    return l_i


def sum_f(k: int, f: Callable[[int], int]) -> int:
    """Returns f(0) + ... + f(k - 1)."""
    assert k >= 0

    s = 0
    for i in range(k):
        s += f(i)

    return s


def s(k: int, alpha: int, beta: int) -> int:
    """Returns f(0, alpha, beta) + ... + f(k - 1, alpha, beta)."""
    assert k >= 0

    return f(k + 1, alpha, beta) - beta


def main() -> None:
    """Checks by assertions."""
    assert fibo(-5) == 5
    assert fibo(-4) == -3
    assert fibo(-3) == 2
    assert fibo(-2) == -1
    assert fibo(-1) == 1
    assert fibo(0) == 0
    assert fibo(1) == 1
    assert fibo(2) == 1
    assert fibo(3) == 2
    assert fibo(4) == 3
    assert fibo(5) == 5

    assert lucas(0) == 2
    assert lucas(1) == 1
    assert lucas(2) == 3
    assert lucas(3) == 4
    assert lucas(4) == 7
    assert lucas(5) == 11

    max_i = (int(sys.argv[1]) if len(sys.argv) > 1
             else 100)

    for i in range(max_i + 1):
        fibo_i_m1 = fibo(i - 1)
        fibo_i = fibo(i)
        fibo_i_p1 = fibo(i + 1)

        assert fibo_i_p1 == fibo_i + fibo_i_m1

        assert fibo_i == f(i, 0, 1)
        assert fibo_i_p1 == f(i, 1, 1)
        assert fibo_i_m1 == f(i, 1, 0)

        assert lucas(i) == f(i, 2, 1)

        assert sum_f(i, lambda n: 1) == i
        assert sum_f(i, lambda n: n) == (i - 1) * i // 2

        assert sum_f(i, fibo) == fibo_i_p1 - 1

        assert f(i, 0, 0) == 0
        assert f(i, 1, 1) == fibo_i_p1
        assert f(i, 1, 0) == fibo_i_m1

        assert sum_f(i, lambda k: s(k, 0, 1)) == f(i + 2, 0, 1) - (i + 1)

        assert sum_f(i, lambda k: s(k, 1, 0)) == f(i + 2, 1, 0) - 1
        assert sum_f(i, lambda k: s(k, 1, 0)) == sum_f(i, fibo)

        for alpha in range(-10, 11):
            assert sum_f(i, lambda k: f(k, alpha, 0)) == f(i + 1, alpha, 0)

            for beta in range(-10, 11):
                assert f(0, alpha, beta) == alpha
                assert f(1, alpha, beta) == beta
                assert f(2, alpha, beta) == alpha + beta
                assert f(3, alpha, beta) == alpha + beta * 2
                assert f(4, alpha, beta) == alpha * 2 + beta * 3
                assert f(5, alpha, beta) == alpha * 3 + beta * 5

                assert f(i, alpha, beta) == alpha * fibo_i_m1 + beta * fibo_i

                sum_by_f = f(i + 1, alpha, beta) - beta

                assert sum_f(i, lambda k: f(k, alpha, beta)) == sum_by_f
                assert s(i, alpha, beta) == sum_by_f
                assert (sum_f(i, lambda k: s(k, alpha, beta)) ==
                        f(i + 2, alpha, beta) - alpha - beta * (i + 1))


if __name__ == '__main__':
    main()