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: Well, this morning, I headed on over to Slashdot and read that OGR-22 and OGR-23 have apparently been solved. It looks like OGR-24 will be attempted using the facilities of distributed.net . This effort has come a long way since I was working on OGR-19 back in 1993. Wow.


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