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