|
|
A003022
|
|
Length of shortest (or optimal) Golomb ruler with n marks.
(Formerly M2540)
|
|
49
|
|
|
1, 3, 6, 11, 17, 25, 34, 44, 55, 72, 85, 106, 127, 151, 177, 199, 216, 246, 283, 333, 356, 372, 425, 480, 492, 553, 585
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
2,2
|
|
COMMENTS
|
a(n) is the least integer such that there is an n-element set of integers between 0 and a(n), the sums of pairs (of not necessarily distinct elements) of which are distinct.
An n-mark Golomb ruler has a unique integer distance between any pair of marks and thus measures n(n-1)/2 distinct integer distances.
An optimal n-mark Golomb ruler has the smallest possible length (distance between the two end marks) for an n-mark ruler.
A perfect n-mark Golomb ruler has length exactly n(n-1)/2 and measures each distance from 1 to n(n-1)/2. (End)
Also the smallest m such that there exists a length-n composition of m for which every restriction to a subinterval has a different sum. Representatives of compositions for the first few terms are:
0: ()
1: (1)
3: (2,1)
6: (2,3,1)
11: (3,1,5,2)
17: (4,2,3,7,1)
Representatives of corresponding Golomb rulers are:
{0}
{0,1}
{0,2,3}
{0,2,5,6}
{0,3,4,9,11}
{0,4,6,9,16,17}
(End)
|
|
REFERENCES
|
CRC Handbook of Combinatorial Designs, 1996, p. 315.
A. K. Dewdney, Computer Recreations, Scientific Amer. 253 (No. 6, Jun), 1985, pp. 16ff; 254 (No. 3, March), 1986, pp. 20ff.
S. W. Golomb, How to number a graph, pp. 23-37 of R. C. Read, editor, Graph Theory and Computing. Academic Press, NY, 1972.
Richard K. Guy, Unsolved Problems in Number Theory (2nd edition), Springer-Verlag (1994), Section C10.
A. Kotzig and P. J. Laufer, Sum triangles of natural numbers having minimum top, Ars. Combin. 21 (1986), 5-13.
Miller, J. C. P., Difference bases. Three problems in additive number theory. Computers in number theory (Proc. Sci. Res. Council Atlas Sympos. No. 2, Oxford, 1969), pp. 299--322. Academic Press, London,1971. MR0316269 (47 #4817)
Rhys Price Jones, Gracelessness, Proc. 10th S.-E. Conf. Combin., Graph Theory and Computing, 1979, pp. 547-552.
Ana Salagean, David Gardner and Raphael Phan, Index Tables of Finite Fields and Modular Golomb Rulers, in Sequences and Their Applications - SETA 2012, Lecture Notes in Computer Science. Volume 7280, 2012, pp. 136-147.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
A. K. Dewdney, Computer Recreations, Scientific Amer. 253 (No. 6, Jun), 1985, pp. 16ff; 254 (No. 3, March), 1986, pp. 20ff. [Annotated scanned copy]
|
|
FORMULA
|
a(n) >= n(n-1)/2, with strict inequality for n >= 5 (Golomb). - David W. Wilson, Aug 18 2007
|
|
EXAMPLE
|
a(5)=11 because 0-1-4-9-11 (0-2-7-10-11) resp. 0-3-4-9-11 (0-2-7-8-11) are shortest: there is no b0-b1-b2-b3-b4 with different distances |bi-bj| and max. |bi-bj| < 11.
|
|
MATHEMATICA
|
Min@@Total/@#&/@GatherBy[Select[Join@@Permutations/@Join@@Table[IntegerPartitions[i], {i, 0, 15}], UnsameQ@@ReplaceList[#, {___, s__, ___}:>Plus[s]]&], Length] (* Gus Wiseman, May 17 2019 *)
|
|
CROSSREFS
|
0-1-4-9-11 corresponds to 1-3-5-2 in A039953: 0+1+3+5+2=11
A row or column of array in A234943.
|
|
KEYWORD
|
nonn,hard,nice,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
a(25), a(26) proved by OGR-25 and OGR-26 projects, added by Max Alekseyev, Sep 29 2010
|
|
STATUS
|
approved
|
|
|
|