The OEIS is supported by the many generous donors to the OEIS Foundation.


(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003022 Length of shortest (or optimal) Golomb ruler with n marks.
(Formerly M2540)
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)
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.
From David W. Wilson, 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)
Positions where A143824 increases (see also A227590). - N. J. A. Sloane, Apr 08 2016
From Gus Wiseman, May 17 2019: (Start)
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:
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).
A. K. Dewdney, Computer Recreations, Scientific Amer. 253 (No. 6, Jun), 1985, pp. 16ff; 254 (No. 3, March), 1986, pp. 20ff. [Annotated scanned copy]
Distributed.Net, Project OGR
Kent Freeman, Unpublished notes. [Scanned copy]
Michael Geißer, Theresa Körner, Sascha Kurz, and Anne Zahn, Squares with three digits, arXiv:2112.00444 [math.NT], 2021.
A. Kotzig and P. J. Laufer, Sum triangles of natural numbers having minimum top, Ars. Combin. 21 (1986), 5-13. [Annotated scanned copy]
Joseph Malkevitch, Weird Rulers.
G. Martin and K. O'Bryant, Constructions of generalized Sidon sets, arXiv:math/0408081 [math.NT], 2004-2005.
L. Miller, Golomb Rulers
K. O'Bryant, Sets of Natural Numbers with Proscribed Subsets, J. Int. Seq. 18 (2015) # 15.7.7
W. Schneider, Golomb Rulers
J. B. Shearer, Golomb ruler table
David Singmaster, David Fielker, N. J. A. Sloane, Correspondence, August 1979
Eric Weisstein's World of Mathematics, Golomb Ruler.
Wikipedia, Golomb ruler
a(n) >= n(n-1)/2, with strict inequality for n >= 5 (Golomb). - David W. Wilson, Aug 18 2007
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.
Min@@Total/@#&/@GatherBy[Select[Join@@Permutations/@Join@@Table[IntegerPartitions[i], {i, 0, 15}], UnsameQ@@ReplaceList[#, {___, s__, ___}:>Plus[s]]&], Length] (* Gus Wiseman, May 17 2019 *)
See A106683 for triangle of marks.
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.
Adding 1 to these terms gives A227590. Cf. A143824.
For first differences see A270813.
Sequence in context: A173143 A109413 A294397 * A025722 A022775 A025743
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, Sep 29 2010
a(27) proved by OGR-27, added by David Consiglio, Jr., Jun 09 2014
a(28) proved by OGR-28, added by David Consiglio, Jr., Jan 19 2023

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 16 22:05 EDT 2024. Contains 371755 sequences. (Running on oeis4.)