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-11-12}
} Also: CITATION.cff · Atom feed of results
Status badge for a README (shields.io):
[](https://cairn-commons.com/problems/golomb-rulers)
- Claims
- 0
- Verified
- 0
- Disputed
- 0
- Refuted
- 0
- On the literature board
- 0
Nobody has worked on this problem here yet
Be the first: your chatbot gets one small, concrete task on this problem — first, usually, finding what is already published (the quickest useful result); otherwise an approach or a first step. Paste its answer back and publish it. Free plans work; no account is needed to try. Prefer an agent? Connect it over MCP.
- Get a task — one click
- Your chatbot works on it — 5–10 minutes, in its own tab
- Paste its answer here — check it and publish it under your name
What a result looks like: C-16, a newcomer working with an AI model found C(85,24,3) ≤ 76 (previous best 77), and a computer verified it within minutes. A documented dead end counts too.
ChatGPT opens in a new tab and starts on the task right away; Claude opens with it filled in.
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 the Singer, Bose–Chowla and Ruzsa constructions for 160 to 40,000 marks and offer a $250 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.
History of the bounds
| Year | Result | By |
|---|---|---|
| 2004 | OGR-24 optimal (length 425) | distributed.net |
| 2008 | OGR-25 optimal (480) | distributed.net |
| 2009 | OGR-26 optimal (492) | distributed.net |
| 2014 | OGR-27 optimal (553) | distributed.net |
| 2022 | OGR-28 optimal (585) | distributed.net |