from functools import cache
from typing import Optional


def fib(max_n: int) -> list[int]:
    a, b = 1, 2
    xs = [a]
    while b <= max_n:
        xs.append(b)
        a, b = b, a + b
    return xs


FIBS = fib(10**18)


@cache
def zgo(rem: int, i: int, count: int) -> Optional[int]:
    if rem == 0:
        return count
    if rem < 0 or rem < FIBS[i]:
        return None

    r1 = zgo(rem - FIBS[i], i + 2, count + 1)
    if r1:
        return r1
    return zgo(rem, i + 1, count)


@cache
def z(n: int) -> int:
    return zgo(n, 0, 0) or 0


def zsum(n: int) -> int:
    return sum(z(i) for i in range(1, n))


def zxsgo(rem: int, i: int, xs: list[int]) -> Optional[list]:
    if rem == 0:
        return xs
    if rem < 0 or rem < FIBS[i]:
        return None

    r1 = zxsgo(rem - FIBS[i], i + 2, xs + [FIBS[i]])
    if r1:
        return r1
    return zxsgo(rem, i + 1, xs)


def zxs(n: int) -> Optional[list]:
    return zxsgo(n, 0, [])


@cache
def zsumr(n: int) -> int:
    if n == 1:
        return 0
    if n == 2:
        return 1
    if n in FIBS:
        fib_i = FIBS.index(n)
        a, b = FIBS[fib_i - 2], FIBS[fib_i - 1]
        # print(f"zsumr({a})={zsumr(a)} zsumr({b})={zsumr(b)} {b - a}")
        res = 0

        # Zeckendorf sum up the previous fibonacci
        res += zsumr(b)

        # Zeckendorf sum up to the pervious previous fibonacci. This works because
        # if we look at the Zeckendorf representations between two fibonaccis it is
        # always a combination of the previous fibonacci plus the representations
        # starting from zero. Since we cannot use the previous fibonacci because of
        # the *nonconsecutive* requirement, it has to be the second previous.
        res += zsumr(a)

        # However, then for all the zsumr(a) terms we considered, that fibonacci
        # a was not part of the count, so we have to add it:
        res += n - b

        return res

    for fib_i, fib in enumerate(FIBS):
        if fib > n:
            break
    else:
        assert False
    fib_i -= 1
    b = FIBS[fib_i]  # fib before n

    res = 0
    res += zsumr(b)  # Zeckendorf up to previous fib
    res += zsumr(n - b)  # Zeckendorf from b to n without last term
    res += n - b  # account for last term
    return res


def euler_297():
    assert zsumr(3) == 2
    assert zsumr(5) == 5
    assert zsumr(13) == 20
    assert zsumr(89) == 235
    assert zsumr(100) == 261
    assert zsumr(10**6) == 7894453

    assert z(1) == 1
    assert z(5) == 1
    assert z(14) == 2
    assert z(100) == 3
    return zsumr(10**17)


if __name__ == "__main__":
    solution = euler_297()
    print(f"e297.py: {solution}")
    assert solution == 2252639041804718029