What this research found
A Golomb ruler places marks on a line so that no two pairs of marks are the same distance apart. Finding a short one is easy; proving that none is shorter means eliminating the entire space of shorter candidates, which is what a branch-and-bound search did here for every order from 2 to 11 marks. All ten proven lengths — 1, 3, 6, 11, 17, 25, 34, 44, 55, and 72 — match the published values in OEIS A003022, with order 11 settled after examining 13,677,172 candidate configurations in about 145 seconds.
- Optimality was certified for orders 2 through 11, giving lengths 1, 3, 6, 11, 17, 25, 34, 44, 55, and 72. All ten agree with OEIS A003022, which was consulted only after each search terminated rather than supplied as a target.
- Order 11 marks the ceiling for this single-threaded design. Proving its optimal length of 72, realised by the marks 0, 1, 4, 13, 28, 33, 47, 54, 64, 70, and 72, required 13,677,172 examined configurations and 145.339 seconds.
- The cost of proving optimality grows exponentially, multiplying by a geometric-mean factor of about 7.6 per order from 4 to 11, with a sharper 17-fold jump entering order 11. Node counts span roughly seven orders of magnitude over the range and runtimes about eight.
- Lower-bound pruning, which feeds each proven optimum into the next order's search, does most of the work. Switching it off raises the order-6 node count from 340 to 463, a 36% increase; removing symmetry breaking as well brings it to 481.
- Throughput declines from about 550,000 examined nodes per second at order 5 to 94,000 at order 11, because the arbitrary-precision difference mask widens as rulers lengthen and the feasibility test grows with recursion depth. Runtime consequently grows a little faster than node count.
How it was done
The solver worked upward from order 2, letting each proven optimum tighten the next search: the trailing marks of any Golomb ruler form a shorter Golomb ruler, so a partial ruler with several marks still to place cannot finish shorter than the known optimum for that many marks. A depth-first recursion placed marks left to right and tracked which pairwise differences were already spent in a single arbitrary-precision integer treated as a bitmask, reducing each feasibility test to a bit lookup. A reflection rule requiring the first gap to be smaller than the last discarded mirror-image rulers, and a greedy pass seeded the incumbent so that pruning was active from the first node. Every candidate placement that passed the feasibility test was counted, giving each optimality proof an explicit size, and each returned ruler was re-validated by a separate routine that recomputes all pairwise differences.
Data sources
- OEIS A003022 — published optimal (shortest) Golomb ruler lengths, used only as an after-the-fact check
Limitations
The solver is single-threaded and written in a high-level language, so its absolute runtimes are not competitive with optimised or parallel implementations, and its pruning bound omits the stronger partial-completion bounds that state-of-the-art solvers use to reach higher orders. Optimality is established only through order 11, whereas distributed volunteer searches have certified it up to order 28.
How this research was produced
K-Dense Web planned and ran this mathematics investigation end to end — gathering the sources, carrying out the analysis, producing the figures, and drafting the report. The full session transcript, including every intermediate step, is available to view.
