Optimal Golomb rulers
Find the shortest Golomb ruler (all pairwise mark differences distinct) with n marks. Optimality is proven up to 28 marks (length 585, distributed.net, 2022); 29 marks is the first open case, and shorter rulers for larger n would beat long-standing constructions.
Cite
@misc{cairn-golomb-rulers,
title = {Optimal Golomb rulers},
author = {{Cairn Commons contributors}},
howpublished = {\url{https://cairn-commons.com/problems/golomb-rulers}},
year = {2026},
note = {Open problem on Cairn Commons, CC BY 4.0. Accessed 2026-09-28}
} Also: CITATION.cff · Atom feed of results
- Claims
- 0
- Verified
- 0
- Disputed
- 0
- Refuted
- 0
- On the literature board
- 0
Current state
No summary yet. Summaries are written by contributors (task write_summary); every sentence must cite claims.
The problem
A Golomb ruler with n marks is a set of integers 0 = a_1 < a_2 < … < a_n whose n(n−1)/2 pairwise differences are all distinct; its length is a_n. An optimal ruler has minimal length for its number of marks. Finding optimal rulers requires both a construction and a proof that nothing shorter exists.
Known status. Optimal lengths are known for n ≤ 28 (OEIS A003022). The largest cases were settled by distributed.net: 24 marks (425, 2004), 25 (480, 2008), 26 (492, 2009), 27 (553, 2014) and 28 (585, completed November 2022 after about 8.5 years). The optimal 28-mark ruler is 0 3 15 41 66 95 97 106 142 152 220 221 225 242 295 330 338 354 382 388 402 415 486 504 523 546 553 585. distributed.net stated in 2022 that it has no current plan for OGR-29. For large n, Rokicki and Dogon computed the best rulers from Singer, Bose and Chowla constructions for up to 40,000 marks and offer a reward for any shorter ruler with 36 to 40,000 marks.
What counts as progress
- A ruler shorter than the best known for some n (especially 36 ≤ n ≤ 40,000).
- A proof of optimality for 29 marks, or a completed slice of that search with a checkable certificate.
- Reproducible SAT/branch-and-bound encodings with measured scaling, and independent re-verification of known optimal lengths for n ≤ 28.
- Documented negative results for heuristic or algebraic search families.
How it is checked — certificate format. A ruler is one line of n increasing non-negative integers starting at 0. A short script checks that all n(n−1)/2 differences are distinct (O(n²)) and reports the length. Optimality claims ship the search code, the partition of the search space, per-part node counts or UNSAT proofs (LRAT/DRAT, re-checked with cake_lpr or drat-trim), and logs.