def hofstadter_q(limit: int) -> list[int]:
    q = [0] * (limit + 1)
    q[1] = q[2] = 1

    for n in range(3, limit + 1):
        a = n - q[n - 1]
        b = n - q[n - 2]

        assert 1 <= a < n
        assert 1 <= b < n

        q[n] = q[a] + q[b]

    return q


q = hofstadter_q(1600)

print("k  midpoint  target  plateau_start  plateau_length")

plateaus = []

for k in range(2, 10):
    midpoint = 3 * 2**k
    target = midpoint // 2

    start = midpoint
    while start > 1 and q[start - 1] == target:
        start -= 1

    length = midpoint - start
    plateaus.append((k, midpoint, target, start, length))

    print(k, midpoint, target, start, length)


# The smaller plateau needed by the prospective k=9 plateau survives intact.
assert q[762:768] == [384] * 6
print("\nk=9 lower fuel:")
for n in range(762, 768):
    print(n, q[n])


# Once two upper values equal C, the recurrence reduces to
# Q(n) = 2*Q(n-C). Check every genuinely propagated cell at k=2..8.
propagated_cells = 0

for k, midpoint, target, start, length in plateaus:
    if k == 9:
        continue

    for n in range(start + 2, midpoint):
        assert q[n - 1] == target
        assert q[n - 2] == target
        assert q[n] == 2 * q[n - target] == target
        propagated_cells += 1

print("\npropagated cells checked:", propagated_cells)


# Show the failed k=9 ignition.
print("\nk=9 ignition region:")

for n in range(1528, 1537):
    if n < 1530:
        print(n, q[n])
        continue

    a = n - q[n - 1]
    b = n - q[n - 2]

    print(
        n,
        "Q(n) =", q[n],
        "addresses =", (a, b),
        "summands =", (q[a], q[b]),
    )

assert q[1528] == 732
assert q[1529] == 735
assert q[795] == 417
assert q[798] == 408
assert q[1530] == 825