

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 nelement set of integers between 0 and a(n), the sums of pairs (of not necessarily distinct elements) of which are distinct.
An nmark Golomb ruler has a unique integer distance between any pair of marks and thus measures n(n1)/2 distinct integer distances.
An optimal nmark Golomb ruler has the smallest possible length (distance between the two end marks) for an nmark ruler.
A perfect nmark Golomb ruler has length exactly n(n1)/2 and measures each distance from 1 to n(n1)/2. (End)
Also the smallest m such that there exists a lengthn 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. 2337 of R. C. Read, editor, Graph Theory and Computing. Academic Press, NY, 1972.
Richard K. Guy, Unsolved Problems in Number Theory (2nd edition), SpringerVerlag (1994), Section C10.
A. Kotzig and P. J. Laufer, Sum triangles of natural numbers having minimum top, Ars. Combin. 21 (1986), 513.
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. 299322. Academic Press, London,1971. MR0316269 (47 #4817)
Rhys Price Jones, Gracelessness, Proc. 10th S.E. Conf. Combin., Graph Theory and Computing, 1979, pp. 547552.
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. 136147.
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(n1)/2, with strict inequality for n >= 5 (Golomb).  David W. Wilson, Aug 18 2007


EXAMPLE

a(5)=11 because 014911 (0271011) resp. 034911 (027811) are shortest: there is no b0b1b2b3b4 with different distances bibj and max. bibj < 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

014911 corresponds to 1352 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 OGR25 and OGR26 projects, added by Max Alekseyev, Sep 29 2010


STATUS

approved



