次数4、長さ6のゴロム定規。最短で完全である。 ゴロム定規 （ゴロムじょうぎ、英 : Golomb ruler ）とは、想像上の定規の上で一連の整数位置にマークを配置し、任意のマークの対の距離がどれをとっても等しくならないものをいう。ゴロム尺 とも。マーク数を「次数 (order)」、2つのマーク間の距離のうち最大の距離を「長さ (length)」という。ゴロム定規の平行移動と鏡映は自明と考えられる。そのため慣例として、最小のマークを0とし、その次のマークは2つの可能な値のうち小さいほうを取る。
ソロモン・ゴロム が名前の由来だが、Sidon （英語版 ） [ 1] [ 2]
ゴロム定規は、その長さまでの全ての距離を測定できる必要はないが、全ての距離を測定できるゴロム定規を「完全 (perfect)」ゴロム定規 (PGR) という。5個以上のマークのあるゴロム定規では、完全ゴロム定規が存在しないことが証明されている[ 3] OGR ) という。ゴロム定規を作るのは簡単だが、特定次数のゴロム定規を見つけるのは困難である。
特定次数における最短ゴロム定規の発見を分散コンピューティング を利用したプロジェクトとしてdistributed.net で進められている。distributed.netでは、次数24[ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10]
2009年から開始した次数27の最短ゴロム定規を探すプロジェクトは、予想では7年で発見できるとしていた[ 11] [ 12]
distributed.netは次数28の最短ゴロム定規を探索している。また、新たなアルゴリズムの改善策が見つかったため、以前ほど時間はかからないと予測している[ 13] [ 14]
最短ゴロム定規は、フェーズドアレイレーダー の設計、電波望遠鏡 の配置などに応用されている。
今のところ、n-次の最短ゴロム定規を求める問題の計算量は不明だが、NP困難 問題だと考えられている[ 3]
下表は、全ての既知の最短ゴロム定規である。マークの配置が表にあるものと逆のもの（対称型）は省く。
次数
長さ
マークの位置
1
0
0
2
1
0 1
3
3
0 1 3
4
6
0 1 4 6
5
11
0 1 4 9 11
6
17
0 1 4 10 12 17
7
25
0 1 4 10 18 23 25
8
34
0 1 4 9 15 22 32 34
9
44
0 1 5 12 25 27 35 41 44
10
55
0 1 6 10 23 26 34 41 53 55
11
72
0 1 4 13 28 33 47 54 64 70 72
12
85
0 2 6 24 29 40 43 55 68 75 76 85
13
106
0 2 5 25 37 43 59 70 85 89 98 99 106
14
127
0 4 6 20 35 52 59 77 78 86 89 99 122 127
15
151
0 4 20 30 57 59 62 76 100 111 123 136 144 145 151
16
177
0 1 4 11 26 32 56 68 76 115 117 134 150 163 168 177
17
199
0 5 7 17 52 56 67 80 81 100 122 138 159 165 168 191 199
18
216
0 2 10 22 53 56 82 83 89 98 130 148 153 167 188 192 205 216
19
246
0 1 6 25 32 72 100 108 120 130 153 169 187 190 204 231 233 242 246
20
283
0 1 8 11 68 77 94 116 121 156 158 179 194 208 212 228 240 253 259 283
21
333
0 2 24 56 77 82 83 95 129 144 179 186 195 255 265 285 293 296 310 329 333
22
356
0 1 9 14 43 70 106 122 124 128 159 179 204 223 253 263 270 291 330 341 353 356
23
372
0 3 7 17 61 66 91 99 114 159 171 199 200 226 235 246 277 316 329 348 350 366 372
24
425
0 9 33 37 38 97 122 129 140 142 152 191 205 208 252 278 286 326 332 353 368 384 403 425
25
480
0 12 29 39 72 91 146 157 160 161 166 191 207 214 258 290 316 354 372 394 396 431 459 467 480
26
492
0 1 33 83 104 110 124 163 185 200 203 249 251 258 314 318 343 356 386 430 440 456 464 475 487 492
27
553
0 3 15 41 66 95 97 106 142 152 220 221 225 242 295 330 338 354 382 388 402 415 486 504 523 546 553
28
585
0 3 15 41 66 95 97 106 142 152 220 221 225 242 295 330 338 354 382 388 402 415 486 504 523 546 553 585
