|
| |
|
|
A003022
|
|
Length of shortest (or optimal) Golomb ruler with n marks.
(Formerly M2540)
|
|
25
| |
|
|
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
(list; graph; refs; listen; history; 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.
Comments from David W. Wilson (davidwwilson(AT)comcast.net), Aug 17 2007: (Start)
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)
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).
|
|
|
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.
A. Kotzig and P. J. Laufer, Sum triangles of natural numbers having minimum top, Ars. Combin. 21 (1986), 5-13.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
| Anonymous, In Search Of The Optimal 20, 21 and 22 Mark Golomb Rulers
Distributed.Net, Project OGR
Google Scholar, Golomb Ruler
G. Martin and K. O'Bryant, Constructions of generalized Sidon sets
L. Miller, Golomb Rulers
Ed Pegg, Jr., Golomb Rulers
B. Rankin, Golomb Ruler Calculations
W. Schneider, Golomb Rulers
J. B. Shearer, Golomb ruler table
J. B. Shearer, Table of Known Optimal Golomb Rulers
N. J. A. Sloane, First few optimal Golomb rulers
D. Vanderschel et al., In Search Of The Optimal 20, 21 and 22 Mark Golomb Rulers
Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.
Wikipedia, Golomb ruler
Index entries for sequences related to Golomb rulers
|
|
|
FORMULA
| a(n) >= n(n-1)/2, with strict inequality for n >= 5 (Golomb). - David W Wilson (davidwwilson(AT)comcast.net), Aug 18 2007
|
|
|
EXAMPLE
| 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
|
|
|
CROSSREFS
| See A106683 for triangle of marks.
Cf. A008404, A036501, A039953, A078106, A030873.
0-1-4-9-11 corresponds to 1-3-5-2 in A039953: 0+1+3+5+2=11
Sequence in context: A023601 A173143 A109413 * A025722 A022775 A025743
Adjacent sequences: A003019 A003020 A003021 * A003023 A003024 A003025
|
|
|
KEYWORD
| nonn,hard,nice
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| 425 sent by Ed Pegg, Jr., Nov 15 2004.
a(25), a(26) proved by OGR-25 and OGR-26 projects, added by Max Alekseyev (maxale(AT)gmail.com), Sep 29 2010
|
| |
|
|
