%I A003022 M2540
%S A003022 1,3,6,11,17,25,34,44,55,72,85,106,127,151,177,199,216,246,283,333,356,
%T A003022 372,425
%N A003022 Length of shortest (or optimal) Golomb ruler with n marks.
%C A003022 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.
%C A003022 Comments from David W. Wilson (davidwwilson(AT)comcast.net), Aug 17 2007: 
               (Start)
%C A003022 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.
%C A003022 An optimal n-mark Golomb ruler has the smallest possible length (distance 
               between the two end marks) for an n-mark ruler.
%C A003022 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)
%C A003022 Comment from Ed Pegg, Jr. (ed(AT)mathpuzzle.com), Aug 17 2007: If you're 
               looking for something practical, which can measure any distance, 
               you need a "sparse ruler". David Fowler has studied these (see link 
               below).
%D A003022 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%D A003022 CRC Handbook of Combinatorial Designs, 1996, p. 315.
%D A003022 A. K. Dewdney, Computer Recreations, Scientific Amer. 253 (No. 6, Jun), 
               1985, pp. 16ff; 254 (No. 3, March), 1986, pp. 20ff.
%D A003022 S. W. Golomb, How to number a graph, pp. 23-37 of R. C. Read, editor, 
               Graph Theory and Computing. Academic Press, NY, 1972.
%D A003022 A. Kotzig and P. J. Laufer, Sum triangles of natural numbers having minimum 
               top, Ars. Combin. 21 (1986), 5-13.
%H A003022 Anonymous, <a href="http://members.aol.com/golomb20">In Search Of The 
               Optimal 20, 21 and 22 Mark Golomb Rulers</a>
%H A003022 Distributed.Net, <a href="http://www.distributed.net/ogr">Project OGR</
               a>
%H A003022 Google Scholar, <a href="http://scholar.google.com/scholar?q=golomb+ruler">
               Golomb Ruler</a>
%H A003022 G. Martin and K. O'Bryant, <a href="http://arXiv.org/abs/math.NT/0408081">
               Constructions of generalized Sidon sets</a>
%H A003022 L. Miller, <a href="http://www.cuug.ab.ca/~millerl/g3-records.html">Golomb 
               Rulers</a>
%H A003022 Ed Pegg, Jr., <a href="http://www.maa.org/editorial/mathgames/mathgames_11_15_04.html">
               Golomb Rulers</a>
%H A003022 B. Rankin, <a href="http://www.ee.duke.edu/~wrankin/golomb/golomb.html">
               Golomb Ruler Calculations</a>
%H A003022 W. Schneider, <a href="http://www.wschnei.de/number-theory/golomb-rulers.html">
               Golomb Rulers</a>
%H A003022 J. B. Shearer, <a href="http://www.research.ibm.com/people/s/shearer/
               grtab.html">Golomb ruler table</a>
%H A003022 J. B. Shearer, <a href="http://www.research.ibm.com/people/s/shearer/
               gropt.html">Table of Known Optimal Golomb Rulers</a>
%H A003022 N. J. A. Sloane, <a href="a3022.gif">First few optimal Golomb rulers</
               a>
%H A003022 D. Vanderschel et al., <a href="http://members.aol.com/golomb20/">In 
               Search Of The Optimal 20, 21 and 22 Mark Golomb Rulers</a>
%H A003022 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
               GolombRuler.html">Link to a section of The World of Mathematics.</
               a>
%H A003022 Wikipedia, <a href="http://en.wikipedia.org/wiki/Golomb_ruler">Golomb 
               ruler</a>
%H A003022 <a href="Sindx_Go.html#Golomb">Index entries for sequences related to 
               Golomb rulers</a>
%F A003022 a(n) >= n(n-1)/2, with strict inequality for n >= 5 (Golomb). - David 
               W Wilson (davidwwilson(AT)comcast.net), Aug 18 2007
%e A003022 a(4)=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
%Y A003022 See A106683 for triangle of marks.
%Y A003022 Cf. A008404, A036501, A039953, A078106, A030873.
%Y A003022 0-1-4-9-11 corresponds to 1-3-5-2 in A039953: 0+1+3+5+2=11
%Y A003022 Sequence in context: A025735 A023601 A109413 this_sequence A025722 A022775 
               A025743
%Y A003022 Adjacent sequences: A003019 A003020 A003021 this_sequence A003023 A003024 
               A003025
%K A003022 nonn,hard,nice
%O A003022 2,2
%A A003022 N. J. A. Sloane (njas(AT)research.att.com).
%E A003022 425 sent by Ed Pegg, Jr., Nov 15 2004.