"""JAM 5, line 3 instrument (founder, testing Grok's LINE 2 proposal):
first-return-time distribution to state(n; L, M) = (n mod M,
Q(n-L+1..n) mod M), the same descriptor as THE COLLISION LADDER. A
"return" is any n whose exact state was seen at some earlier n' < n;
the gap n - n' (using the MOST RECENT prior sighting, a standard
recurrence-time definition) is one sample. Under a naive IID-uniform
null over the K = M^(L+1) nominal states, the expected number of
returns in a walk of length N is ~ N^2/(2K) - astronomically below 1
for L>=8 at N=2,000,000 (birthday horizon ~10^9-10^20, per the prior
probe). So: ANY return observed for L>=8 at this N is itself direct,
cheap evidence against naive uniformity - it would mean Q's walk
occupies a far smaller EFFECTIVE support than the nominal state
count, detectable without approaching the full collision horizon.
Zero returns is the null-consistent (uninformative) outcome, honestly
reported as such - it does not distinguish "large effective support"
from "just not enough steps yet."""

N_MAX = 2_000_000
WINDOWS = [(6, 54), (8, 108), (10, 162), (12, 324), (14, 486)]


def build_q(n_max: int):
    Q = [0] * (n_max + 1)
    Q[1] = 1
    if n_max >= 2:
        Q[2] = 1
    for n in range(3, n_max + 1):
        Q[n] = Q[n - Q[n - 1]] + Q[n - Q[n - 2]]
    return Q


def return_times(Q, n_max: int, L: int, M: int):
    last_seen = {}
    gaps = []
    for n in range(L, n_max + 1):
        key = (n % M,) + tuple(Q[n - L + 1: n + 1][i] % M for i in range(L))
        if key in last_seen:
            gaps.append(n - last_seen[key])
        last_seen[key] = n
    return gaps


def main():
    print("building Q(1..%d) ..." % N_MAX)
    Q = build_q(N_MAX)
    print("\n L |   M |   states K   | expected returns (N^2/2K) | observed returns | gap stats")
    for L, M in WINDOWS:
        K = M ** (L + 1)
        expected = (N_MAX ** 2) / (2.0 * K)
        gaps = return_times(Q, N_MAX, L, M)
        if gaps:
            gaps_sorted = sorted(gaps)
            mean_g = sum(gaps) / len(gaps)
            med_g = gaps_sorted[len(gaps_sorted) // 2]
            print(" %2d | %3d | %11.3e | %24.2e | %16d | mean=%.0f median=%d min=%d max=%d"
                  % (L, M, K, expected, len(gaps), mean_g, med_g, gaps_sorted[0], gaps_sorted[-1]))
        else:
            print(" %2d | %3d | %11.3e | %24.2e | %16d | (none - null-consistent, uninformative)"
                  % (L, M, K, expected, 0))
    print("\nHonest reading: for L>=8 the naive-uniform expected return count is")
    print("far below 1; ANY observed return is evidence the effective state support")
    print("is much smaller than M^(L+1). Zero returns proves nothing either way -")
    print("it is exactly what both 'huge effective support' and 'just need more N'")
    print("would also produce.")


if __name__ == "__main__":
    main()