Golomb Ruler Calculations

My Masters work was in the area of application of distributed computing techniques for the calculation of numerical sequences known as Golomb Rulers. The search for these sequences involves massive amounts of computer time and is akin to prime number searches.

The end results of my research is that I discovered the shortest sequence (referred to as the optimum ruler) containing 19 marks. I also verified the correctness for the 17 and 18 mark rulers, which were previously discovered but unpublished.

And, for the curious, here are the rulers!!!!!


17 Mark Ruler: [0,8,31,34,40,61,77,99,118,119,132,143,147,182,192,194,199]
18 Mark Ruler: [0,11,24,28,49,63,68,86,118,127,133,134,160,163,194,206,214,216]
19 Mark Ruler: [0,4,13,15,42,56,59,77,93,116,126,138,146,174,214,221,240,245,246]

If you want to learn the lurid details of Golomb Rulers, then a condensed version of my Master's Thesis is available (sorry, no HTML yet). The source code listings that were originally included in my thesis have been omitted from this document.

Or you can view a much shorter paper that covers our methods and results.

I am making the source code discussed in my thesis available. This is the distributed version of the code, and requires PVM to run. There is also the original sequential code originally written by David McCracken that I based my code upon.

Well, it just goes to show that the world, or in this case the Internet, never stands still. David Vanderschel, Mark Garry, David Landgren, Rick Niles and a host of others have discovered the optimum 20 and 21 mark rulers. The solution was computed in a distributed method using collaboration over the Internet. The group has a Web Page that describes this monumental effort. Congrats for all who were involved!

Update (April 2011): it looks the search for OGR-25 and OGR-26 have been completed by the distributed.net group. The search for OGR-27 has begun and is using a much more efficient tree pruning algorithm. The project homepage is Here


Please report problems to
Bill Rankin wrankin@ee.duke.edu