|
%I M0995 N0373 #85 Oct 01 2022 10:43:28
%S 0,4,6,8,14,26,48,96
%N Length of longest simple cycle without chords in the n-dimensional hypercube graph. Also called n-coil or closed n-snake-in-the-box problem.
%C This sequence actually gives the length of a longest closed chordless path in the n-dimensional hypercube. To distinguish closed and open paths, newer terminology uses "n-coil" for closed and "n-snake" for open paths. See also A099155.
%C a(7) was found by exhaustive search by Kochut.
%C Longest closed achordal path in n-dimensional hypercube.
%C After 48, lower bounds on the next terms are 96, 180, 344, 630, 1236. - Darren Casella (artdeco42(AT)yahoo.com), Mar 04 2005
%D D. Casella and W. D. Potter, "New Lower Bounds for the Snake-in-the-box Problem: Using Evolutionary Techniques to Hunt for Snakes". To appear in 18th International FLAIRS Conference, 2005.
%D D. Casella and W. D. Potter, "New Lower Bounds for the Snake-in-the-box Problem: Using Evolutionary Techniques to Hunt for Coils". Submitted to IEEE Conference on Evolutionary Computing, 2005.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D Gilles Zémor, "An upper bound on the size of the snake-in-the-box", Combinatorica 17.2 (1997): 287-298.
%H David Allison, Daniel Paulusma, <a href="https://arxiv.org/abs/1603.05119">New Bounds for the Snake-in-the-Box Problem</a>, arXiv:1603.05119 [math.CO], 16 Jun 2016.
%H Kevin M. Byrnes, <a href="https://arxiv.org/abs/1604.02755">A new method for constructing circuit codes</a>, Bull. ICA, 80 (2017), 40-60.
%H D. A. Casella and W. D. Potter, <a href="https://www.researchgate.net/publication/221439264_New_Lower_Bounds_for_the_Snake-in-the-Box_Problem_Using_Evolutionary_Techniques_to_Hunt_for_Snakes">New Lower Bounds for the Snake-in-the-box Problem: Using Evolutionary Techniques to Hunt for Snakes</a>.
%H D. W. Davies, <a href="/A000937/a000937.pdf">Longest "separated" paths and loops in an N cube</a>, IEEE Trans. Electron. Computers, 14 (1965), 261. [Annotated scanned copy]
%H Pavel G. Emelyanov, Agung Lukito, <a href="https://doi.org/10.1016/S0012-365X(99)00335-0">On the maximal length of a snake in hypercubes of small dimension</a> Discrete Math. 218 (2000), no. 1-3, 51-59, [From _N. J. A. Sloane_, Feb 06 2012]
%H S. Hood, D. Recoskie, J. Sawada, D. Wong, <a href="https://doi.org/10.1007/s10878-013-9630-z">Snakes, coils, and single-track circuit codes with spread k</a>, J. Combin. Optim. 30 (1) (2015) 42-62, Table 1 (lower bounds for n<=17).
%H V. Klee, <a href="http://www.jstor.org/stable/2316860">What is the maximum length of a d-dimensional snake?</a>, Amer. Math. Monthly, 77 (1970), 63-65.
%H Krys J. Kochut, <a href="http://cobweb.cs.uga.edu/~potter/CompIntell/kochut.pdf">Snake-In-The-Box Codes for Dimension 7</a>, Journal of Combinatorial Mathematics and Combinatorial Computing, Vol. 20, pp. 175-185, 1996.
%H Patric R. J. Östergård and Ville H. Pettersson, <a href="https://www.researchgate.net/publication/272030795_Exhaustive_Search_for_Snake-in-the-Box_Codes">Exhaustive Search for Snake-in-the-Box Codes</a>, Preprint, 2014, Journal Graphs and Combinatorics archive, Volume 31 Issue 4, July 2015, Pages 1019-1028.
%H Patric R. J. Östergård, Ville H. Pettersson, <a href="https://doi.org/10.1016/j.dam.2014.07.010">On the maximum length of coil-in-the-box codes in dimension 8</a>, Discrete Applied Mathematics, 2014
%H K. G. Paterson, J. Tuliani, <a href="https://doi.org/10.1109/18.669420">Some new circuit codes</a>, IEEE Trans. Inform. Theory 44, 1305-1309 (1998). [Shows a(8)=96. - _N. J. A. Sloane_, Apr 06 2014]
%H Ville Pettersson, <a href="https://aaltodoc.aalto.fi/handle/123456789/17688">Graph Algorithms for Constructing and Enumerating Cycles and Related Structures</a>, Preprint 2015.
%H W. D. Potter, <a href="https://web.archive.org/web/20200217135138/http://ai1.ai.uga.edu/sib/sibwiki/doku.php/records">A list of current records for the Snake-in-the-Box problem.</a> [Archived version.]
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Snake.html">Snake.</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Snake-in-the-box">Snake-in-the-box</a>.
%e a(4)=8: Path of a longest 4-coil: 0000 1000 1100 1110 0110 0111 0011 0001 0000. See Figure 1 in Kochut.
%e Solutions of lengths 4,6,8,14 and 26 in dimensions 2..6 from Arlin Anderson (starship1(AT)gmail.com):
%e 0 1 3 2; 0 1 3 7 6 4; 1 3 7 6 14 10 8; 0 1 3 7 6 14 10 26 27 25 29 21 20 16;
%e 0 1 3 7 6 14 10 26 27 25 29 21 53 37 36 44 40 41 43 47 63 62 54 50 48 16;
%Y Cf. A099155, length of maximum n-snake.
%K nonn,nice,hard,more
%O 1,2
%A _N. J. A. Sloane_
%E Edited and extended by _Hugo Pfoertner_, Oct 13 2004
%E a(8) from Paterson and Tuliani (1998), according to Östergård and Ville (2014). - _N. J. A. Sloane_, Apr 06 2014
%E a(1) changed by _Hugo Pfoertner_, Aug 01 2015
| 