哥隆尺问题

哥隆尺問題（Golomb ruler），是如何在一把尺上劃分刻度，使所有刻度彼此之間的距離都不相同。刻度的數目稱為階，而兩個刻度間最長的距離為長度。對哥隆尺做平移或鏡像並不影響結果，因此習慣上將最小刻度設為 0 。

哥隆尺是由Sidon和Babcock各自独立发现，并且以数学家所羅門·格倫布的名字命名。

哥隆尺不需要能够測量到其自身長度為止的所有距离，如果能夠的话，稱為完美哥隆尺。已經证明不存在五階以上的完美哥隆尺。最優哥隆尺則是同一階中長度最短的哥隆尺。生成哥隆尺是简单的，但是找到一个指定階的最优哥隆尺是的一个有挑战性的计算项目。 

Distributed.net已经利用大規模分散式平行計算完成了对24階到27階最優哥隆尺的尋找。Distributed.net已於2014年2月開始尋找28階最優哥隆尺。

目前，尋找n階最優哥隆尺的複雜度是未知的，有人猜測這是NP困難問題。

已经发现的最优哥隆尺
下表列出了目前已知的最优哥隆尺。

参考资料

 
http://mathworld.wolfram.com/GolombRuler.html
http://www.research.ibm.com/people/s/shearer/grtab.html
http://www.distributed.net/ogr/

數論