Golomb Ruler

Author

Eric W. Weisstein
February 27, 2005

This notebook downloaded from http://mathworld.wolfram.com/notebooks/Combinatorics/GolombRuler.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/GolombRuler.html.

©2005 Wolfram Research, Inc. except for portions noted otherwise

Code

DifferenceEncoding[l_]:=-Subtract@@@Partition[l,2,1]
DistanceEncoding[l_]:=FoldList[Plus,0,l]

Different Encodings

DifferenceEncoding[{0,1,3,7}]

DistanceEncoding[{1,2,4}]

Enumeration

golomb[1]:={{0}}
golomb[2]:={{0,1}}
golomb[3]:={{0,1,3}}
golomb[4]:={{0,1,4,6}}
golomb[5]:={{0,1,4,9,11},{0,3,4,9,11}}
golomb[6]:={{0,1,4,10,12,17},{0,1,4,10,15,17},{0,3,5,9,16,17},{0,4,6,9,16,17}}
golomb[7]:={{0,1,4,10,18,23,25},{0,2,3,10,16,21,25},{0,2,6,9,14,24,25},{0,1,7,11,20,23,25},{0,3,4,12,18,23,25}}
golomb[8]:={{0,1,4,9,15,22,32,34}}
golomb[9]:={{0,3,9,17,19,32,39,43,44}}
golomb[10]:={{0,1,6,10,23,26,34,41,53,55}}
golomb[11]:={{0,1,4,13,28,33,47,54,64,70,72},{0,1,9,19,24,31,52,56,58,69,72}}
golomb[12]:={{0,2,6,24,29,40,43,55,68,75,76,85}}
golomb[13]:={{0,7,8,17,21,36,47,63,69,81,101,104,106}}
golomb[14]:={{0,5,28,38,41,49,50,68,75,92,107,121,123,127}}
golomb[15]:={{0,6,7,15,28,40,51,75,89,92,94,121,131,147,151}}
golomb[16]:={{0,1,4,11,26,32,56,68,76,115,117,134,150,163,168,177}}
golomb[17]:={{0,5,7,17,52,56,67,80,81,100,122,138,159,165,168,191,199}}
golomb[18]:={{0,2,10,22,53,56,82,83,89,98,130,148,153,167,188,192,205,216}}
golomb[19]:={{0,4,13,15,42,56,59,77,93,116,126,138,146,174,214,221,240,245,246}}
golomb[20]:={{0,24,30,43,55,71,75,89,104,125,127,162,167,189,206,215,272,275,282,283}}
golomb[21]:={{0,4,23,37,40,48,68,78,138,147,154,189,204,238,250,251,256,277,309,331,333}}
golomb[22]:={{0,1,9,14,43,70,106,122,124,128,159,179,204,223,253,263,270,291,330,341,353,356}}
golomb[23]:={{0,6,22,24,43,56,95,126,137,146,172,173,201,213,258,273,281,306,311,355,365,369,372}}
golomb[24]:={{0,9,33,37,38,97,122,129,140,142,152,191,205,208,252,278,286,326,332,353,368,384,403,425}}
golomb[25]:=
{{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}}

Map[Length,golomb/@Range[2,25],{2}]

Map[Last,golomb/@Range[2,25],{2}]

Table Order

Table[golomb[n],{n,8}]//ColumnForm

Canonical Order

Table[First[Sort[{#,Reverse[Last[#]-#]}]]&/@golomb[n],{n,8}]//ColumnForm

Table[
Sort/@Abs[Subtract@@@#&/@(Subsets[#,{2}]&/@golomb[n])],{n,10}]//ColumnForm

A003022

Max/@Table[
Sort/@Abs[Subtract@@@#&/@(Subsets[#,{2}]&/@golomb[n])],{n,23}]

A036501

Length/@Table[
Sort/@Abs[Subtract@@@#&/@(Subsets[#,{2}]&/@golomb[n])],{n,23}]

Table[
Length/@Sort/@Abs[Subtract@@@#&/@(Subsets[#,{2}]&/@golomb[n])],{n,23}]

First/@%

Graphics

Golomb[l_List,off_List:{0,0}]:=Module[{pairs=Sort[KSubsets[l,2],OrderedQ[Abs[Subtract@@@{#1,#2}]]&],i},
{
{Yellow,Polygon[off+#&/@{{0,0},{Max[l],0},{Max[l],1},{0,1}}]},
Line[off+#&/@{{0,0},{Max[l],0},{Max[l],1},{0,1},{0,0}}],
{{Brown,Line[{off+{#,0},off+{#,.8}}]},Text[#,off+{#,-.15}]}&/@l,
Table[{
Line[off+#&/@Flatten[Outer[List,pairs[[i]],{1+.2i}],1]],
Text[Abs[Subtract@@pairs[[i]]],off+{#,1+.2i}]&/@{-.2,Max[l]+.2}
},{i,Length[pairs]}]
}
]

3 and 4 Marks

Show[Graphics[{
Golomb[golomb[3][[1]]],
Golomb[golomb[4][[1]],{4,0}]
},AspectRatio->Automatic],PlotRange->All]

6 Marks

Show[Graphics[{
Golomb[golomb[6][[1]]]
}],PlotRange->All]

Show[Graphics[{
Golomb[golomb[6][[2]]]
}],PlotRange->All]

Show[Graphics[{
Golomb[golomb[6][[3]]]
}],PlotRange->All]

Show[Graphics[{
Golomb[golomb[6][[4]]]
}],PlotRange->All]