Fibonacci numbers functions, such as fib to dec, dec to fib, dec to all possible fibs, explain fib. NON-RECURSIVE ONLY

Fibonacci.py

Fibonacci = str


def fib_by_index(n: int) -> int:
    """
    Calculates the n-th Fibonacci number. O(n)
    :param n: n-th Fibonacci number.
    :return: Fibonacci number VALUE
    """
    if n in [0, 1]:
        return n

    a, b = 0, 1

    for i in range(1, n):
        a, b = b, a + b

    return b


def dec_to_fib(n: int) -> Fibonacci:
    """
    Translates decimal n to fibonacci number
    :param n: Decimal number
    :return: fibonacci number
    """
    result = []
    i = 0
    prev = 0
    while True:
        if n <= 0:
            break

        next_n = fib_by_index(i)
        if next_n > n:
            index = i - 2
            if len(result) < index:
                result.extend('0' * index)
            result[-index] = '1'
            n -= prev
            i = 0
        prev = next_n
        i += 1
    return ''.join(result)


def fib_simplify(fib: Fibonacci) -> Fibonacci:
    """
    Simplifies fibonacci number
    :param fib: provided number
    :return: Simplified (or equal) fibonacci number
    """
    return fib.replace('100', '011', 1)


def fib_to_dec(fib: Fibonacci) -> int:
    """
    Translates fibonacci number to decimal
    :param fib: Fibonacci number
    :return: Decimal
    """
    res = 0
    for i in range(len(fib)):
        if fib[-i - 1] == '1':
            res += fib_by_index(i + 2)
    return res


def fib_explain(fib: Fibonacci) -> str:
    """
    Explains fibonacci number by returning sum of fibonacci elements
    :param fib: Fibonacci number
    :return: String of sum
    """
    res = []
    for i in range(len(fib)):
        if fib[-i - 1] == '1':
            res.append(fib_by_index(i + 2))
    return '+'.join(map(lambda x: str(x), reversed(sorted(res))))


def dec_to_fib_all(n: int) -> list[Fibonacci]:
    """
    Returns all possible fibonacci numbers for provided number
    :param n: Decimal provided number
    :return: All possible fibonacci numbers for provided number
    """
    res = []
    simplest = dec_to_fib(n)
    res.append(simplest)
    last = simplest
    while True:
        simplified = fib_simplify(last)
        if simplified == last:
            break
        res.append(simplified)
        last = simplified
    return res


if __name__ == '__main__':
    v = 83191  # Example value to convert

    for item in dec_to_fib_all(v):
        print(item, fib_explain(item))