{"id":"sparse-ruler-marks","name":"Sparse rulers (restricted difference bases)","family":"additive-combinatorics","description":"Mark as few points as possible on a ruler of length n so that every distance 1..n is measured: 10 lengths beyond the proven range, scored against Pegg's best-known rulers (OEIS A046693 / A326499). Exact verification.","metric":"record_ratio","direction":"maximize","tolerance":0.05,"eval_timeout_seconds":300,"agent_timeout_seconds":1800,"mutable":["ruler.py"],"runtime":"python>=3.11, standard library only (math, random, itertools, functools, collections, heapq, time)","decomposable":true,"status":"active","captain":null,"parent_problem":null,"program_md":"# Sparse rulers (restricted difference bases)\n\n## Goal\n\nA **sparse ruler of length n** is a set of marks `S ⊆ {0, 1, ..., n}` such that every distance\n`1, 2, ..., n` is the difference of two marks (so `0, n ∈ S`). Equivalently `S` is a *restricted\ndifference basis* for `{1, ..., n}`: the smallest element is 0 and the largest is n. Fewer marks is\nbetter; the minimum is `Δ(n)` (OEIS A046693). Leech's asymptotic bound is `Δ(n)² / n ≥ 2.434`,\nWichmann's explicit rulers give `≈ 3`, and every best-known ruler beyond the proven range has\n`round(sqrt(3n + 9/4))` or one more mark (\"excess\" 0 or 1). Whether an excess-1 length ever admits\nan excess-0 ruler is open; that is where a record can fall.\n\n`ruler.py` exposes\n\n    sparse_ruler(n: int, time_budget: float, seed: int) -> list[int]\n\nreturning the marks (distinct ints in `[0, n]`, any order). The eval recomputes every distance\nitself; an incomplete ruler fails the whole submission rather than scoring low.\n\n## Metric\n\nThe eval runs `sparse_ruler` on the fixed length set below, each with the given time budget\n(10 s by default), verifies the ruler, and reports\n\n    metric = mean over n of  record_marks(n) / marks(n)\n\nso 1.0 means matching every best-known ruler and anything above 1.0 on a length is a new record.\nPer-length detail (marks, record, excess, ratio, seconds) is in `per_instance`; any length you beat\nis listed under `records_beaten`. `ZT_EVAL_SEED` only changes the `seed` handed to your solver.\n\n## Records\n\nBest-known marks from Ed Pegg Jr's table \"Sparse rulers and excess values for lengths\nn = 1..10501\" (OEIS A326499, a-file), which agrees with OEIS A046693 wherever the latter is\nproven (n ≤ 213, exhaustive searches by Robison, Pfoertner, Luschny, Schwartau–Schröder). Every\nruler behind the numbers below was decoded and re-verified when this pack was written\n(2026-09-07). **None of these lengths is proven optimal**: OEIS states \"terms over n = 213 are\nunverified minimal\" and singles out n = 474 (excess 1) as a length where an excess-0 ruler might\nexist.\n\n| n | best-known marks | round(sqrt(3n + 9/4)) | excess | proven |\n|---|---|---|---|---|\n| 250 | 27 | 27 | 0 | no |\n| 300 | 31 | 30 | 1 | no |\n| 474 | 39 | 38 | 1 | no |\n| 500 | 39 | 39 | 0 | no |\n| 1000 | 56 | 55 | 1 | no |\n| 1500 | 68 | 67 | 1 | no |\n| 2000 | 77 | 77 | 0 | no |\n| 3000 | 95 | 95 | 0 | no |\n| 5000 | 122 | 122 | 0 | no |\n| 10000 | 174 | 173 | 1 | no |\n\nBeating an excess-1 entry means finding a ruler with `round(sqrt(3n + 9/4))` marks; beating an\nexcess-0 entry would contradict Pegg's excess conjecture and is a much bigger deal. The\nunrestricted version of this problem (marks allowed outside `[0, n]`) is AlphaEvolve repository\nproblem 7 and lives in the `difference-basis-length` pack.\n\nIf you beat one, the marks are the evidence: they are in the eval log. Say so in your notes so the\nhub can update the table and forward the ruler to OEIS.\n\n## Iterating\n\n- Start on one or two lengths: `ZT_EVAL_INSTANCES=250,474 ZT_EVAL_PER_INSTANCE_SECONDS=2 python eval.py`\n  runs in a few seconds. The full set takes about 100 s of solver time plus verification.\n- Respect `time_budget` (seconds, per call). The eval kills the run if a call overruns it by more\n  than 25% + 3 s. Be deterministic given `seed`: use `random.Random(seed)`.\n- Only the standard library is available (`math, random, itertools, functools, collections, heapq, time`).\n- Known structure: Wichmann rulers `1^r (r+1)^1 (2r+1)^r (4r+3)^s (2r+2)^(r+1) 1^r` (gap\n  notation, `g^c` = c consecutive gaps of size g) have `4r + s + 3` marks and length\n  `4r(r+s+2) + 3(s+1)`; the best-known rulers are Wichmann-like: a few unit gaps, one odd gap, a\n  block of a repeated gap, a long block of roughly twice that gap, and the mirror image. Pegg's\n  table encodes each record ruler in this gap notation. Search over such gap patterns, then repair\n  or extend with local moves; exact minimality proofs are hopeless at these sizes, so the game is\n  clever construction plus local search (moving a mark, splitting a gap, dropping redundant marks).\n\nWrite one honest line in `NOTES.md`: the idea, and which lengths it helped. Simpler is better: all\nelse equal prefer the shorter solver. Log every experiment, including discards, in your results.tsv.\n","eval_py":"\"\"\"Eval for sparse-ruler-marks. Prints one JSON line: {\"metric\": record_ratio, ...}.\n\nVerification is exact: the marks must be distinct integers in [0, n] and every distance 1..n must\nbe the difference of two marks. The score is recomputed from the marks; nothing the solver reports\nis trusted. Environment:\n  ZT_EVAL_SEED                    seed handed to sparse_ruler() (the instance set is fixed)\n  ZT_EVAL_INSTANCES               comma-separated lengths n (default \"250,300,474,500,1000,1500,2000,3000,5000,10000\")\n  ZT_EVAL_PER_INSTANCE_SECONDS    time budget handed to sparse_ruler() per instance (default 10)\n\"\"\"\n\nfrom __future__ import annotations\n\nimport ast\nimport hashlib\nimport json\nimport math\nimport os\nimport sys\nimport time\nfrom pathlib import Path\n\n# Best-known number of marks, n -> marks. Source: Ed Pegg Jr, \"Sparse rulers and excess values for\n# lengths n=1..10501\" (OEIS A326499 a-file), consistent with OEIS A046693 (proven minimal only up to\n# n = 213). Every ruler behind these numbers was decoded and re-verified when this pack was written.\n# None of these lengths is proven; Pegg's conjecture is that the excess over round(sqrt(3n + 9/4))\n# is always 0 or 1, and instances with excess 1 are the natural targets.\nRECORDS = {\"250\": 27, \"300\": 31, \"474\": 39, \"500\": 39, \"1000\": 56, \"1500\": 68, \"2000\": 77, \"3000\": 95, \"5000\": 122, \"10000\": 174}\nSEED = os.environ.get(\"ZT_EVAL_SEED\", \"dev-seed\")\nINSTANCES = [x.strip() for x in os.environ.get(\"ZT_EVAL_INSTANCES\", \"250,300,474,500,1000,1500,2000,3000,5000,10000\").split(\",\") if x.strip()]\nBUDGET = float(os.environ.get(\"ZT_EVAL_PER_INSTANCE_SECONDS\", \"10\"))\nMAX_MARKS = 2000   # any ruler with more marks than this scores below 0.1 anyway; keeps verification O(1 s)\nSTDLIB_ALLOW = {\"math\", \"random\", \"itertools\", \"functools\", \"collections\", \"heapq\", \"time\", \"sys\", \"typing\", \"operator\"}\nFORBIDDEN_NAMES = {\"__import__\", \"importlib\", \"builtins\", \"__builtins__\", \"open\", \"exec\", \"eval\", \"compile\",\n                   \"globals\", \"__loader__\", \"__spec__\", \"breakpoint\", \"input\", \"memoryview\", \"vars\"}\n\n\ndef fail(msg: str, kind: str = \"error\") -> None:\n    print(json.dumps({\"metric\": 0.0, \"error\": msg, \"kind\": kind}))\n    sys.exit(1)\n\n\ndef check_imports(path: Path) -> None:\n    try:\n        tree = ast.parse(path.read_text(encoding=\"utf-8\"))\n    except SyntaxError as e:\n        fail(f\"syntax error in {path.name}: {e}\", \"compile_error\")\n    for node in ast.walk(tree):\n        names = []\n        if isinstance(node, ast.Import):\n            names = [a.name.split(\".\")[0] for a in node.names]\n        elif isinstance(node, ast.ImportFrom) and node.module:\n            names = [node.module.split(\".\")[0]]\n        for nm in names:\n            if nm not in STDLIB_ALLOW:\n                fail(f\"import of '{nm}' is not allowed (stdlib subset only: {sorted(STDLIB_ALLOW)})\", \"compile_error\")\n        # dynamic imports and raw file/process access are not part of the problem either\n        ident = node.id if isinstance(node, ast.Name) else node.attr if isinstance(node, ast.Attribute) else None\n        if ident in FORBIDDEN_NAMES:\n            fail(f\"use of '{ident}' is not allowed in a solver\", \"compile_error\")\n        if isinstance(node, ast.ImportFrom) and node.level:\n            fail(\"relative imports are not allowed in a solver\", \"compile_error\")\n\n\ndef verify(n: int, marks) -> int:\n    \"\"\"Exact check. Returns the number of marks.\"\"\"\n    if not isinstance(marks, (list, tuple)) or not marks:\n        raise ValueError(\"sparse_ruler must return a non-empty list of marks\")\n    if len(marks) > MAX_MARKS:\n        raise ValueError(f\"{len(marks)} marks is more than the {MAX_MARKS} this eval accepts\")\n    S = []\n    for x in marks:\n        if isinstance(x, bool) or not isinstance(x, int):\n            raise ValueError(f\"mark {x!r} is not an int\")\n        if x < 0 or x > n:\n            raise ValueError(f\"mark {x} is outside [0, {n}]\")\n        S.append(x)\n    if len(set(S)) != len(S):\n        raise ValueError(\"marks are not distinct\")\n    S.sort()\n    seen = bytearray(n + 1)\n    for i in range(len(S)):\n        si = S[i]\n        for j in range(i + 1, len(S)):\n            seen[S[j] - si] = 1\n    for d in range(1, n + 1):\n        if not seen[d]:\n            raise ValueError(f\"distance {d} is not measured by the ruler\")\n    return len(S)\n\n\ndef main() -> None:\n    here = Path(__file__).parent\n    check_imports(here / \"ruler.py\")\n    sys.path.insert(0, str(here))\n    try:\n        import ruler as mod  # noqa: E402\n    except SystemExit:\n        raise\n    except Exception as e:\n        fail(f\"import ruler.py failed: {e!r}\", \"compile_error\")\n    if not hasattr(mod, \"sparse_ruler\"):\n        fail(\"ruler.py must define sparse_ruler(n, time_budget, seed)\", \"compile_error\")\n    for lab in INSTANCES:\n        if lab not in RECORDS:\n            fail(f\"unknown instance {lab}; known: {list(RECORDS)}\", \"compile_error\")\n    seed = int(hashlib.sha256(SEED.encode()).hexdigest()[:8], 16)\n    per, ratios, beaten = {}, [], []\n    t_start = time.time()\n    for lab in INSTANCES:\n        n = int(lab)\n        t0 = time.time()\n        try:\n            marks = mod.sparse_ruler(n, BUDGET, seed)\n        except SystemExit:\n            raise\n        except Exception as e:\n            fail(f\"sparse_ruler({n}) raised {e!r}\", \"runtime_error\")\n        elapsed = time.time() - t0\n        if elapsed > BUDGET * 1.25 + 3.0:\n            fail(f\"sparse_ruler({n}) took {elapsed:.1f}s for a {BUDGET:.1f}s budget\", \"timeout\")\n        try:\n            m = verify(n, marks)\n        except ValueError as e:\n            fail(f\"sparse_ruler({n}): {e}\", \"wrong_answer\")\n        ratio = RECORDS[lab] / m\n        ratios.append(ratio)\n        per[lab] = {\"marks\": m, \"record\": RECORDS[lab], \"excess\": m - round(math.sqrt(3 * n + 2.25)),\n                    \"ratio\": round(ratio, 6), \"seconds\": round(elapsed, 2)}\n        if m < RECORDS[lab]:\n            beaten.append(lab)\n        print(f\"n={n}: {m} marks (record {RECORDS[lab]}), ratio {ratio:.4f}, {elapsed:.1f}s\", flush=True)\n    metric = sum(ratios) / len(ratios)\n    print(json.dumps({\"metric\": round(metric, 6), \"instances\": INSTANCES, \"per_instance\": per,\n                      \"records_beaten\": beaten, \"seconds\": round(time.time() - t_start, 1)}))\n\n\nif __name__ == \"__main__\":\n    main()\n","baseline":{"ruler.py":"\"\"\"Baseline: a three-block ruler (a run of unit gaps, then gaps of a+1, then a run of unit gaps at\nthe far end), followed by a pass that drops marks whose distances are all measured twice.\nScores roughly 0.7 of the records. Beat it.\"\"\"\n\nimport math\nimport random\nfrom collections import Counter\n\n\ndef sparse_ruler(n: int, time_budget: float, seed: int) -> list[int]:\n    rng = random.Random(seed)\n    best = None\n    centre = max(1, int(math.sqrt(n / 2)))\n    for a in range(max(1, centre - 3), centre + 4):\n        # {0..a} measures every d = k(a+1) - i, i in 0..a, against the multiples of a+1;\n        # {n-a..n} measures the tail n - i.  Together that is every distance 1..n.\n        marks = set(range(a + 1)) | set(range(0, n + 1, a + 1)) | set(range(n - a, n + 1))\n        marks = prune(sorted(marks), n, rng)\n        if best is None or len(marks) < len(best):\n            best = marks\n    return best\n\n\ndef prune(marks: list[int], n: int, rng: random.Random) -> list[int]:\n    \"\"\"Remove marks in random order while every distance stays measured (count >= 1).\"\"\"\n    count = [0] * (n + 1)\n    for i in range(len(marks)):\n        for j in range(i + 1, len(marks)):\n            count[marks[j] - marks[i]] += 1\n    alive = set(marks)\n    order = marks[:]\n    rng.shuffle(order)\n    for m in order:\n        if m in (0, n):\n            continue\n        # distances that pairs through m measure; m+d and m-d may both be alive, so count them\n        mine = Counter(abs(m - o) for o in alive if o != m)\n        if all(count[d] > c for d, c in mine.items()):\n            alive.remove(m)\n            for d, c in mine.items():\n                count[d] -= c\n    return sorted(alive)\n"}}