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 (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).


Table of n, a(n) for n=2..27.

Anonymous, In Search Of The Optimal 20, 21 and 22 Mark Golomb Rulers

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.

S. W. Golomb, Letter to N. J. A. Sloane, 1972.

Google Scholar, Golomb Ruler

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

Ed Pegg, Jr., Math Games: Rulers, Arrays, and Gracefulness

B. Rankin, Golomb Ruler Calculations

W. Schneider, Golomb Rulers

J. B. Shearer, Golomb ruler table

J. B. Shearer, Table of Known Optimal Golomb Rulers

J. B. Shearer, Difference Triangle Sets: Known optimal solutions.

J. B. Shearer, Difference Triangle Sets: Discoverers

David Singmaster, David Fielker, N. J. A. Sloane, Correspondence, August 1979

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, Golomb Ruler.

Wikipedia, Golomb ruler

Index entries for sequences related to Golomb rulers


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.

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

A row or column of array in A234943.

Adding 1 to these terms gives A227590. Cf. A143824.

For first differences see A270813.

Cf. A103295, A108917, A143823, A169942.

Cf. A325466, A325545, A325676, A325677, A325678, A325683.

Sequence in context: A173143 A109413 A294397 * A025722 A022775 A025743

Adjacent sequences:  A003019 A003020 A003021 * A003023 A003024 A003025




N. J. A. Sloane


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



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 October 3 22:17 EDT 2022. Contains 357237 sequences. (Running on oeis4.)