Sparse rulers (restricted difference bases)

# Sparse rulers (restricted difference bases) ## Goal A **sparse ruler of length n** is a set of marks `S ⊆ {0, 1, ..., n}` such that every distance `1, 2, ..., n` is the difference of two marks (so `0, n ∈ S`). Equivalently `S` is a *restricted difference basis* for `{1, ..., n}`: the smallest element is 0 and the largest is n. Fewer marks is better; the minimum is `Δ(n)` (OEIS A046693). Leech's asymptotic bound is `Δ(n)² / n ≥ 2.434`, Wichmann's explicit rulers give `≈ 3`, and every best-known ruler beyond the proven range has `round(sqrt(3n + 9/4))` or one more mark ("excess" 0 or 1). Whether an excess-1 length ever admits an excess-0 ruler is open; that is where a record can fall. `ruler.py` exposes sparse_ruler(n: int, time_budget: float, seed: int) -> list[int] returning the marks (distinct ints in `[0, n]`, any order). The eval recomputes every distance itself; an incomplete ruler fails the whole submission rather than scoring low. ## Metric The eval runs `sparse_ruler` on the fixed length set below, each with the given time budget (10 s by default), verifies the ruler, and reports metric = mean over n of record_marks(n) / marks(n) so 1.0 means matching every best-known ruler and anything above 1.0 on a length is a new record. Per-length detail (marks, record, excess, ratio, seconds) is in `per_instance`; any length you beat is listed under `records_beaten`. `ZT_EVAL_SEED` only changes the `seed` handed to your solver. ## Records Best-known marks from Ed Pegg Jr's table "Sparse rulers and excess values for lengths n = 1..10501" (OEIS A326499, a-file), which agrees with OEIS A046693 wherever the latter is proven (n ≤ 213, exhaustive searches by Robison, Pfoertner, Luschny, Schwartau–Schröder). Every ruler behind the numbers below was decoded and re-verified when this pack was written (2026-09-07). **None of these lengths is proven optimal**: OEIS states "terms over n = 213 are unverified minimal" and singles out n = 474 (excess 1) as a length where an excess-0 ruler might exist. | n | best-known marks | round(sqrt(3n + 9/4)) | excess | proven | |---|---|---|---|---| | 250 | 27 | 27 | 0 | no | | 300 | 31 | 30 | 1 | no | | 474 | 39 | 38 | 1 | no | | 500 | 39 | 39 | 0 | no | | 1000 | 56 | 55 | 1 | no | | 1500 | 68 | 67 | 1 | no | | 2000 | 77 | 77 | 0 | no | | 3000 | 95 | 95 | 0 | no | | 5000 | 122 | 122 | 0 | no | | 10000 | 174 | 173 | 1 | no | Beating an excess-1 entry means finding a ruler with `round(sqrt(3n + 9/4))` marks; beating an excess-0 entry would contradict Pegg's excess conjecture and is a much bigger deal. The unrestricted version of this problem (marks allowed outside `[0, n]`) is AlphaEvolve repository problem 7 and lives in the `difference-basis-length` pack. If you beat one, the marks are the evidence: they are in the eval log. Say so in your notes so the hub can update the table and forward the ruler to OEIS. ## Iterating - Start on one or two lengths: `ZT_EVAL_INSTANCES=250,474 ZT_EVAL_PER_INSTANCE_SECONDS=2 python eval.py` runs in a few seconds. The full set takes about 100 s of solver time plus verification. - Respect `time_budget` (seconds, per call). The eval kills the run if a call overruns it by more than 25% + 3 s. Be deterministic given `seed`: use `random.Random(seed)`. - Only the standard library is available (`math, random, itertools, functools, collections, heapq, time`). - Known structure: Wichmann rulers `1^r (r+1)^1 (2r+1)^r (4r+3)^s (2r+2)^(r+1) 1^r` (gap notation, `g^c` = c consecutive gaps of size g) have `4r + s + 3` marks and length `4r(r+s+2) + 3(s+1)`; the best-known rulers are Wichmann-like: a few unit gaps, one odd gap, a block of a repeated gap, a long block of roughly twice that gap, and the mirror image. Pegg's table encodes each record ruler in this gap notation. Search over such gap patterns, then repair or extend with local moves; exact minimality proofs are hopeless at these sizes, so the game is clever construction plus local search (moving a mark, splitting a gap, dropping redundant marks). Write one honest line in `NOTES.md`: the idea, and which lengths it helped. Simpler is better: all else equal prefer the shorter solver. Log every experiment, including discards, in your results.tsv.