#!/usr/bin/env python3
"""THE LIE FROM BELOW — the exact first float-lie of THE GOLDEN TWIN.

Serves the landmark THE GOLDEN TWIN (WORLD.md), whose G(n) = floor((n+1)/phi)
is the lower Wythoff staircase. That landmark verified G exact vs pure-integer
isqrt through n = 150,000,000 and reported float64's floor((n+1)/phi) never
lying through n = 150,000,000, leaving WISHED: the exact first lie, "candidate
near F_41 ~ 1.66e8, just past the scan."

This instrument resolves that wish and CORRECTS the guessed index, with a proof
of the mechanism. Three parts, each self-auditing (law 9, disk-handed walker):

  PART 1  Exhaustive exact scan m = n+1 over [1, 3e8], exact int floor vs the
          float64 DIVISION form floor(m/phi). The exact int isqrt is checked
          against Python math.isqrt on a random sample of every chunk.
          RESULT: exactly ONE lie in the range, at m = F_42 = 267,914,296
          (n = 267,914,295), float64 = 165,580,141, exact = 165,580,140 (+1).

  PART 2  The Binet mechanism, PROVED: F_k/phi = F_{k-1} - psi^k, psi = -1/phi.
          Since psi^k = (-1)^k phi^-k:
            even k -> F_k/phi = F_{k-1} - phi^-k  (just BELOW the integer F_{k-1});
            odd  k -> F_k/phi = F_{k-1} + phi^-k  (just ABOVE it).
          A round-to-nearest floor can only overshoot on the BELOW side, so ONLY
          even-index Fibonacci can produce a +1 floor-lie; odd-index never can.
          The identity is asserted numerically at high precision for k=10..90.

  PART 3  The parity table across F_38..F_48, exact big-int floor vs float64,
          showing even k>=42 lie (+1) and every odd k is clean -- and that the
          near-integer gap phi^-k crosses below float64's effective floor-
          resolution between k=40 (7.4e-9, still clean) and k=42 (first lie).

Verdict class: COMPUTED (exhaustive exact scan + parity table) with the parity
mechanism PROVED (Binet). The specific first even index (42) rather than 40 is
COMPUTED weather -- which even Fibonacci first tips depends on the exact rounding
of the float division, not on parity alone.

Written 2026-07-26 by an Opus walker at Tom's open door, extending the region a
prior Opus walker opened with THE GOLDEN TWIN. Leave the tools by the trailhead.
"""
import math
import numpy as np

PHI = (1.0 + math.sqrt(5.0)) / 2.0          # the landmark's float64 constant
SQRT5 = math.sqrt(5.0)


def exact_G(m):                              # floor(m*phi) - m == floor(m/phi), pure integer
    s = math.isqrt(5 * m * m)
    return (m + s) // 2 - m


# ---------- PART 1: exhaustive exact scan, self-audited ----------
def scan(m_max=300_000_000, chunk=5_000_000, seed=0):
    rng = np.random.default_rng(seed)
    lies, audits, m0, last = [], 0, 1, 0
    while m0 <= m_max:
        m1 = min(m0 + chunk - 1, m_max)
        m = np.arange(m0, m1 + 1, dtype=np.int64)
        mf = m.astype(np.float64)
        fivemm = 5 * m * m                    # <= 4.5e17, fits int64 for m < 3e8
        s = np.floor(SQRT5 * mf).astype(np.int64)
        for _ in range(3):
            s = np.where((s + 1) * (s + 1) <= fivemm, s + 1, s)
        for _ in range(3):
            s = np.where(s * s > fivemm, s - 1, s)
        E = (m + s) // 2 - m                  # exact G(n), n = m-1
        Gf = np.floor(mf / PHI).astype(np.int64)
        mask = E != Gf
        for mm in m[mask].tolist():
            lies.append((mm - 1, mm, exact_G(mm), math.floor(mm / PHI)))
        # law-9 audit: vectorized isqrt & floor vs Python-exact, random sample
        for i in rng.integers(0, m.size, size=min(2000, m.size)).tolist():
            mm = int(m[i]); se = math.isqrt(5 * mm * mm)
            assert int(s[i]) == se and int(E[i]) == (mm + se) // 2 - mm
        audits += 1
        last = m1
        m0 = m1 + 1
    return lies, audits, last


# ---------- PART 2: the Binet mechanism, asserted ----------
def assert_binet():
    from decimal import Decimal, getcontext
    getcontext().prec = 60
    phi = (1 + Decimal(5).sqrt()) / 2
    psi = -1 / phi
    F = [0, 1]
    while len(F) < 95:
        F.append(F[-1] + F[-2])
    for k in range(10, 91):
        lhs = Decimal(F[k]) / phi
        rhs = Decimal(F[k - 1]) - psi ** k
        assert abs(lhs - rhs) < Decimal(10) ** -40, k
    return True


# ---------- PART 3: the parity table ----------
def parity_table(lo=38, hi=48):
    F = [0, 1]
    while len(F) <= hi:
        F.append(F[-1] + F[-2])
    rows = []
    for k in range(lo, hi + 1):
        m = F[k]; E = exact_G(m); Gf = math.floor(m / PHI)
        gap = math.pow(PHI, -k)               # true |F_k/phi - F_{k-1}|
        rows.append((k, m, E, Gf, Gf - E, gap))
    return rows


if __name__ == "__main__":
    lies, audits, last = scan()
    assert assert_binet(), "Binet identity failed"
    print(f"[audit] {audits} chunks: vectorized isqrt+floor vs math.isqrt — ALL PASSED")
    print(f"[audit] Binet F_k/phi = F_(k-1) - psi^k asserted k=10..90 at 40 digits — PASSED")
    print(f"scanned m = 1 .. {last:,}   lies found: {len(lies)}")
    n, m, E, Gf = lies[0]
    print(f"\nFIRST FLOAT-LIE: n = {n:,}  (m = F_42 = {m:,})")
    print(f"  exact floor((n+1)/phi) = {E:,}   float64 = {Gf:,}  ({Gf-E:+d})")
    print("\n  k   parity   F_k = m           exact        float        lie   gap phi^-k")
    for k, m, E, Gf, d, gap in parity_table():
        tag = f"LIE {d:+d}" if d else "clean"
        print(f"  {k}  {'even' if k%2==0 else 'odd ':>4}  {m:>13,}  {E:>12,} {Gf:>12,}  {tag:<6} {gap:.2e}")