Golomb Ruler
In mathematics, a Golomb ruler, named for Solomon W. Golomb and discovered independently by Sidon and Babcock, is a set of marks at integer positions along an imaginary ruler such that no two pairs of marks are the same distance apart. The number of marks on the ruler is its order, and the largest distance between two of its marks is its length. Translation and reflection of a Golomb ruler are considered trivial, so the smallest mark is customarily put at 0 and the next mark at the smaller of its two possible values.
There is no requirement that a Golomb ruler can measure all distances up to its length, but if it does, it is called a perfect Golomb ruler. It has been proven that no perfect Golomb ruler exists for five or more marks. A Golomb ruler is optimal if no shorter Golomb ruler of the same order exists. Creating Golomb rulers is easy, but finding the optimal Golomb rulers for a specified order is computationally very challenging. Distributed.net has completed distributed massively parallel searches for optimal order-24 and order-25 Golomb rulers, confirming the suspected candidates.
One practical use of Golomb rulers is in the design of phased array radio antennas such as radio telescopes. Antennas in an [0,1,4,6] Golomb ruler configuration can often be seen at cell sites.
Currently, the complexity of finding optimal Golomb rulers of arbitrary length n is unknown, but it is believed to be an NP-hard problem.