Revision History for A004137
(Underlined text is an addition;
strikethrough text is a deletion.)
Showing entries 1-10
| older changes
|
|
|
|
#97 by Michael De Vlieger at Sat Oct 14 23:46:31 EDT 2023
|
|
|
|
#96 by Jon E. Schoenfield at Sat Oct 14 22:53:10 EDT 2023
|
|
|
Discussion
|
Sat Oct 14
| 23:46
| Michael De Vlieger: Yes since not in a game concept.
|
|
|
|
#95 by Jon E. Schoenfield at Sat Oct 14 22:51:27 EDT 2023
|
| COMMENTS
|
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.
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.
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, Feb 28 2005
|
| LINKS
|
D. Beutner and H. Harborth, <a href="https://doi.org/10.1007/BF03322754">Graceful labelings of Nearly Complete Graphs</a>, Results Math. 41 (2002) 34-39.
L. Egidi and G. Manzini, <, <a href="http://www.di.unipmn.it/TechnicalReports/TR-INF-2011-06-01-UNIPMN.pdf">Spaced seeds design using perfect rulers</a>, Tech. Rep. CS Department Universita del Piemonte Orientale, June 2011.
Peter Luschny, <a href="http://www.luschny.de/math/rulers/prulers.html">Perfect Rulers.</</a>>.
Peter Luschny, <a href="http://www.luschny.de/math/rulers/optimalconjecture.html">Wichmann Rulers.</</a>>.
Klaus Nagel, <a href="http://www.luschny.de/math/rulers/kamm.txt">Evaluation of perfect rulers.</</a> C program.
David Singmaster, David Fielker, N. J. A. Sloane, <a href="/A004116/a004116.pdf">Correspondence, August 1979</a>>.
M. Wald & N. J. A. Sloane, <a href="/A005318/a005318_3.pdf">Correspondence and Attachment, 1987</a>>.
Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GracefulGraph.html">Graceful Graph.</</a>>.
|
| FORMULA
|
na(n) = n*(n-1)/2 = - A212661(n)+a(n). - Kellen Myers, Jun 06 2016
|
| EXAMPLE
|
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 it is conjectured by _Peter P. Luschny _ that it is impossible to improve beatupon Wichmann's construction for finding optimal rulers of bigger lengths.
|
| EXTENSIONS
|
Terms 79,..,,...,123 from Peter Luschny, Feb 28 2005, with verification by an independent program written by Klaus Nagel. Using this program _Hugo Pfoertner _ found the next term , 138.
Using this program _Hugo Pfoertner _ found further evidence for the conjectured term a(21)=153, Feb 23 2005.
Terms a(21) ... ) .. a(24) proved by exhaustive search by Arch D. Robison, Hugo Pfoertner, Nov 01 2013
|
| STATUS
|
approved
editing
|
|
|
Discussion
|
Sat Oct 14
| 22:53
| Jon E. Schoenfield: “beat” -> “improve upon” okay?
|
|
|
|
#94 by Alois P. Heinz at Wed Oct 04 12:13:57 EDT 2023
|
|
|
|
#93 by Michel Marcus at Wed Oct 04 12:12:51 EDT 2023
|
|
|
|
#92 by Michel Marcus at Wed Oct 04 12:12:46 EDT 2023
|
| COMMENTS
|
If the conjecture is true that an optimal ruler with more than 12 segments is a Wichmann ruler thanthen the sequence continues 232, 251, 270, 289, 308, 327, ... - Peter Luschny, Oct 09 2011 [updated to take the verifications of Robison into account, Oct 01 2015]
|
| LINKS
|
D. Beutner, and H. Harborth, <a href="https://doi.org/10.1007/BF03322754">Graceful labelings of Nearly Complete Graphs</a>, Results Math. 41 (2002) 34-39
|
| STATUS
|
approved
editing
|
|
|
|
#91 by Hugo Pfoertner at Mon Jul 03 11:28:16 EDT 2023
|
|
|
|
#90 by Hugo Pfoertner at Mon Jul 03 11:27:50 EDT 2023
|
| EXTENSIONS
|
Terms 79,..,123 from Peter Luschny, Feb 28 2005, with verification by an independent program written by _Klaus Nagel (nagel.klaus(AT)t-online.de). _. Using this program Hugo Pfoertner found the next term 138.
|
| STATUS
|
approved
editing
|
|
|
|
#89 by R. J. Mathar at Tue Apr 26 07:22:23 EDT 2022
|
|
|
|
#88 by R. J. Mathar at Tue Apr 26 07:22:14 EDT 2022
|
| REFERENCES
|
G. S. Bloom and S. W. Golomb, Numbered complete graphs, unusual rulers, and assorted applications. Theory and Applications of Graphs, Lecture Notes in Math. 642, (1978), 53-65.
I. Redéi and A. Rényi, On the representation of integers 1, 2, ..., n by differences, Mat. Sbornik 24 (1949), 385-389 (Russian).
|
| LINKS
|
D. Beutner, H. Harborth, <a href="https://doi.org/10.1007/BF03322754">Graceful labelings of Nearly Complete Graphs</a>, Results Math. 41 (2002) 34-39
G. S. Bloom and S. W. Golomb, <a href="https://doi.org/10.1007/BFb0070364">Numbered complete graphs, unusual rulers, and assorted applications</a>, Theory and Applications of Graphs, Lecture Notes in Math. 642, (1978), 53-65.
I. Redéi and A. Rényi, <a href="http://mi.mathnet.ru/eng/msb5985">On the representation of integers 1, 2, ..., n by differences</a>, Mat. Sbornik 24 (1949), 385-389 (Russian).
|
| STATUS
|
approved
editing
|
|
|
|
|