"""JAM 4 probe: can a finite local descriptor predict Q ignition?

The Table chose L=6 and M=54 but did not yet specify whether "residues"
means residues of Q itself or of the half-integral error e(n)=Q(n)-n/2.
This instrument checks both natural readings on Hofstadter Q's realized
trajectory.  It can refute either descriptor by an opposite-outcome
collision; absence of a collision is finite survival, never a proof that
the descriptor is a predictive quotient.
"""


K_MAX = 20
N = 3 * (1 << K_MAX)
M = 54
L = 6


q = [0] * (N + 1)
q[1] = q[2] = 1
for n in range(3, N + 1):
    a = n - q[n - 1]
    b = n - q[n - 2]
    if not (1 <= a < n and 1 <= b < n):
        raise RuntimeError(("Q became undefined", n, a, b))
    q[n] = q[a] + q[b]


generation_outcome = {}
seed_start = {}
for k in range(2, K_MAX + 1):
    midpoint = 3 * (1 << k)
    target = midpoint // 2
    starts = [
        n
        for n in range(max(1, midpoint // 2), midpoint - 1)
        if q[n] == target and q[n + 1] == target
    ]
    generation_outcome[k] = bool(starts)
    seed_start[k] = starts[0] if starts else None


def generation_of(n: int) -> int:
    k = 2
    while 3 * (1 << k) <= n:
        k += 1
    return k


def q_descriptor(n: int, k: int) -> tuple[int, ...]:
    midpoint = 3 * (1 << k)
    phase = (midpoint - n) % M
    suffix = tuple(q[j] % M for j in range(n - L + 1, n + 1))
    return (phase, *suffix)


def error_descriptor(n: int, k: int) -> tuple[int, ...]:
    midpoint = 3 * (1 << k)
    phase = (midpoint - n) % M
    # 2e is integral, so "e mod 54" is represented exactly modulo 108.
    suffix = tuple((2 * q[j] - j) % (2 * M) for j in range(n - L + 1, n + 1))
    return (phase, *suffix)


def first_opposite_outcome_collision(descriptor):
    successful = {}
    for n in range(L, N):
        k = generation_of(n)
        if k > K_MAX:
            break
        key = descriptor(n, k)
        if generation_outcome[k]:
            successful.setdefault(key, n)
        elif key in successful:
            return successful[key], n, key
    return None


q_collision = first_opposite_outcome_collision(q_descriptor)
error_collision = first_opposite_outcome_collision(error_descriptor)


print("Q total through", N)
for k in range(2, K_MAX + 1):
    print(
        "k=%2d midpoint=%7d outcome=%s seed=%s"
        % (
            k,
            3 * (1 << k),
            generation_outcome[k],
            seed_start[k],
        )
    )
print("\nD_Q = ((midpoint-n) mod 54, last six Q values mod 54)")
print("opposite-outcome collision:", q_collision)
print("\nD_e = ((midpoint-n) mod 54, last six doubled-errors mod 108)")
print("opposite-outcome collision:", error_collision)
assert q_collision is None
assert error_collision is None
print("\nVERDICT: both candidate descriptors survive through k=20.")
print("This is COMPUTED finite survival, not a predictive-quotient proof.")