A003022 - OEIS

%I M2540 #102 Jan 19 2023 08:52:14

%S 1,3,6,11,17,25,34,44,55,72,85,106,127,151,177,199,216,246,283,333,

%T 356,372,425,480,492,553,585

%N Length of shortest (or optimal) Golomb ruler with n marks.

%C 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 From _David W. Wilson_, Aug 17 2007: (Start)

%C 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 An optimal n-mark Golomb ruler has the smallest possible length (distance between the two end marks) for an n-mark ruler.

%C 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 Positions where A143824 increases (see also A227590). - _N. J. A. Sloane_, Apr 08 2016

%C From _Gus Wiseman_, May 17 2019: (Start)

%C 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:

%C    0: ()

%C    1: (1)

%C    3: (2,1)

%C    6: (2,3,1)

%C   11: (3,1,5,2)

%C   17: (4,2,3,7,1)

%C Representatives of corresponding Golomb rulers are:

%C   {0}

%C   {0,1}

%C   {0,2,3}

%C   {0,2,5,6}

%C   {0,3,4,9,11}

%C   {0,4,6,9,16,17}

%C (End)

%D CRC Handbook of Combinatorial Designs, 1996, p. 315.

%D A. K. Dewdney, Computer Recreations, Scientific Amer. 253 (No. 6, Jun), 1985, pp. 16ff; 254 (No. 3, March), 1986, pp. 20ff.

%D 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 Richard K. Guy, Unsolved Problems in Number Theory (2nd edition), Springer-Verlag (1994), Section C10.

%D A. Kotzig and P. J. Laufer, Sum triangles of natural numbers having minimum top, Ars. Combin. 21 (1986), 5-13.

%D 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)

%D Rhys Price Jones, Gracelessness, Proc. 10th S.-E. Conf. Combin., Graph Theory and Computing, 1979, pp. 547-552.

%D 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.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Anonymous, <a href="http://members.aol.com/golomb20">In Search Of The Optimal 20, 21 and 22 Mark Golomb Rulers</a>

%H A. K. Dewdney, <a href="/A003022/a003022.pdf">Computer Recreations</a>, Scientific Amer. 253 (No. 6, Jun), 1985, pp. 16ff; 254 (No. 3, March), 1986, pp. 20ff. [Annotated scanned copy]

%H Distributed.Net, <a href="http://www.distributed.net/ogr">Project OGR</a>

%H Kent Freeman, <a href="/A003022/a003022_2.pdf">Unpublished notes.</a> [Scanned copy]

%H Michael Geißer, Theresa Körner, Sascha Kurz, and Anne Zahn, <a href="https://arxiv.org/abs/2112.00444">Squares with three digits</a>, arXiv:2112.00444 [math.NT], 2021.

%H S. W. Golomb, <a href="/A003022/a003022_3.pdf">Letter to N. J. A. Sloane, 1972</a>.

%H A. Kotzig and P. J. Laufer, <a href="/A003022/a003022_1.pdf">Sum triangles of natural numbers having minimum top</a>, Ars. Combin. 21 (1986), 5-13. [Annotated scanned copy]

%H Joseph Malkevitch, <a href="http://www.ams.org/samplings/feature-column/fc-2012-01">Weird Rulers</a>.

%H G. Martin and K. O'Bryant, <a href="https://arxiv.org/abs/math/0408081">Constructions of generalized Sidon sets</a>, arXiv:math/0408081 [math.NT], 2004-2005.

%H L. Miller, <a href="http://www.cuug.ab.ca/~millerl/g3-records.html">Golomb Rulers</a>

%H K. O'Bryant, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/OBryant/obr3.html">Sets of Natural Numbers with Proscribed Subsets</a>, J. Int. Seq. 18 (2015) # 15.7.7

%H Ed Pegg, Jr., <a href="http://www.mathpuzzle.com/MAA/30-Rulers and Arrays/mathgames_11_15_04.html">Math Games: Rulers, Arrays, and Gracefulness</a>

%H B. Rankin, <a href="http://www.ee.duke.edu/~wrankin/golomb/golomb.html">Golomb Ruler Calculations</a>

%H W. Schneider, <a href="http://web.archive.org/web/2004/www.wschnei.de/number-theory/golomb-rulers.html">Golomb Rulers</a>

%H J. B. Shearer, <a href="http://www.research.ibm.com/people/s/shearer/grtab.html">Golomb ruler table</a>

%H J. B. Shearer, <a href="http://www.research.ibm.com/people/s/shearer/gropt.html">Table of Known Optimal Golomb Rulers</a>

%H J. B. Shearer, <a href="http://www.research.ibm.com/people/s/shearer/dtsopt.html">Difference Triangle Sets: Known optimal solutions</a>.

%H J. B. Shearer, <a href="http://www.research.ibm.com/people/s/shearer/dtslb.html">Difference Triangle Sets: Discoverers</a>

%H David Singmaster, David Fielker, N. J. A. Sloane, <a href="/A004116/a004116.pdf">Correspondence, August 1979</a>

%H N. J. A. Sloane, <a href="/A003022/a003022.gif">First few optimal Golomb rulers</a>

%H 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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GolombRuler.html">Golomb Ruler.</a>

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Golomb_ruler">Golomb ruler</a>

%H <a href="/index/Go#Golomb">Index entries for sequences related to Golomb rulers</a>

%F a(n) >= n(n-1)/2, with strict inequality for n >= 5 (Golomb). - _David W. Wilson_, Aug 18 2007

%e 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.

%t Min@@Total/@#&/@GatherBy[Select[Join@@Permutations/@Join@@Table[IntegerPartitions[i],{i,0,15}],UnsameQ@@ReplaceList[#,{___,s__,___}:>Plus[s]]&],Length] (* _Gus Wiseman_, May 17 2019 *)

%Y See A106683 for triangle of marks.

%Y Cf. A008404, A036501, A039953, A078106, A030873.

%Y 0-1-4-9-11 corresponds to 1-3-5-2 in A039953: 0+1+3+5+2=11

%Y A row or column of array in A234943.

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

%Y For first differences see A270813.

%Y Cf. A103295, A108917, A143823, A169942.

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

%K nonn,hard,nice,more

%O 2,2

%A _N. J. A. Sloane_

%E 425 sent by _Ed Pegg Jr_, Nov 15 2004

%E a(25), a(26) proved by OGR-25 and OGR-26 projects, added by _Max Alekseyev_, Sep 29 2010

%E a(27) proved by OGR-27, added by _David Consiglio, Jr._, Jun 09 2014

%E a(28) proved by OGR-28, added by _David Consiglio, Jr._, Jan 19 2023