%I A004137 M2526
%S A004137 0,1,3,6,9,13,17,23,29,36,43,50,58,68,79,90,101,112,123,138,153
%N A004137 Maximal number of edges in a graceful graph on n nodes.
%C A004137 A graph with e edges is 'graceful' if its nodes can be labeled with distinct 
               integers in {0,1,...,e} so that, if each edge is labeled with the 
               absolute difference between the labels of its endpoints, then the 
               e edges have the distinct labels 1, 2, ..., e.
%C A004137 Equivalently, maximum m for which there's a restricted difference basis 
               with respect to m with n elements. A 'difference basis w.r.t. m' 
               is a set of integers such that every integer from 1 to m is a difference 
               between two elements of the set. A 'restricted' difference basis 
               is one in which the smallest element is 0 and the largest is m.
%C A004137 a(n) is also the length of an optimal ruler with n marks. For definitions 
               see A103294. For example a(6)=13 is the length of the optimal rulers 
               with 6 marks, {[0, 1, 6, 9, 11, 13], [0, 2, 4, 7, 12, 13], [0, 1, 
               4, 5, 11, 13], [0, 2, 8, 9, 12, 13], [0, 1, 2, 6, 10, 13], [0, 3, 
               7, 11, 12, 13]}. Also n = 1 + A103298(a(n)) . - Peter Luschny (peter(AT)luschny.de) 
               Feb 28 2005
%D A004137 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%D A004137 J.-C. Bermond, Graceful graphs, radio antennae and French windmills, 
               pp. 18-37 of R. J. Wilson, editor, Graph Theory and Combinatorics. 
               Pitman, London, 1978.
%D A004137 J. Leech, On the representation of $1,2,\cdots,n$ by differences. J. 
               London Math. Soc. 31 (1956), 160-169.
%D A004137 J. C. P. Miller, Difference bases: Three problems in additive number 
               theory, pp. 299-322 of A. O. L. Atkin and B. J. Birch, editors, Computers 
               in Number Theory. Academic Press, NY, 1971.
%D A004137 B. Wichmann. A note on restricted difference bases. J. London Math.Soc. 
               38, 1962, 465-466
%H A004137 Klaus Nagel, <a href="http://home.t-online.de/home/nagel.klaus/kamm.c">
               Evaluation of perfect rulers.</a> C program.
%H A004137 Peter Luschny, <a href="http://www.luschny.de/math/rulers/prulers.html">
               Perfect Rulers.</a>
%H A004137 Peter Luschny, <a href="http://www.luschny.de/math/rulers/wichmannrulers.html">
               Optimal Wichmann Rulers.</a>
%H A004137 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
               GracefulGraph.html">Link to a section of The World of Mathematics.</
               a>
%e A004137 a(7)=17: Label the 7 nodes 0,1,8,11,13,15,17 and include all edges except 
               those from 8 to 15, from 13 to 15, from 13 to 17 and from 15 to 17. 
               {0,1,8,11,13,15,17} is a restricted difference basis w.r.t. 17.
%e A004137 a(21)=153 because there exists a complete ruler (i.e. one that can measure 
               every distance between 1 and 153) with marks [0,1,2,3,7,14,21,28,
               43,58,73,88,103,118,126,134,142,150,151,152,153] and no complete 
               ruler of greater length with the same number of marks can be found. 
               This ruler is of the type described by B. Wichmann and is conjectured 
               by P. Luschny that it is impossible to beat Wichmann's construction 
               for finding optimal rulers of bigger lengths.
%o A004137 See Klaus Nagel link.
%Y A004137 Cf. A103294, A103298, A103299, A103296, A102508.
%Y A004137 A080060 is an erroneous version of the sequence, given in Bermond's paper. 
               Cf. A005488.
%Y A004137 Sequence in context: A024190 A004116 A004129 this_sequence A080060 A004131 
               A032782
%Y A004137 Adjacent sequences: A004134 A004135 A004136 this_sequence A004138 A004139 
               A004140
%K A004137 nonn,nice,hard
%O A004137 1,3
%A A004137 N. J. A. Sloane (njas(AT)research.att.com), Simon Plouffe (simon.plouffe(AT)gmail.com)
%E A004137 Miller's paper gives these lower bounds for the 8 terms from a(15) to 
               a(22): 79,90,101,112,123,138,153,168.
%E A004137 Edited by Dean Hickerson (dean.hickerson(AT)yahoo.com), Jan 26 2003
%E A004137 Terms 79,..,123 from Peter Luschny (peter(AT)luschny.de), Feb 28 2005, 
               with verification by an independent program written by Klaus Nagel 
               (nagel.klaus(AT)t-online.de). Using this program Hugo Pfoertner (hugo(AT)pfoertner.org) 
               found the next term 138.
%E A004137 Using this program Hugo Pfoertner (hugo(AT)pfoertner.org) found further 
               evidence for the conjectured term a(21)=153, Feb 23 2005.