The OEIS mourns the passing of Jim Simons and is grateful to the Simons Foundation for its support of research in many branches of science, including the OEIS.
login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000937 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.
(Formerly M0995 N0373)
14
0, 4, 6, 8, 14, 26, 48, 96 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,2
COMMENTS
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.
a(7) was found by exhaustive search by Kochut.
Longest closed achordal path in n-dimensional hypercube.
After 48, lower bounds on the next terms are 96, 180, 344, 630, 1236. - Darren Casella (artdeco42(AT)yahoo.com), Mar 04 2005
REFERENCES
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. 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.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Gilles Zémor, "An upper bound on the size of the snake-in-the-box", Combinatorica 17.2 (1997): 287-298.
LINKS
David Allison, Daniel Paulusma, New Bounds for the Snake-in-the-Box Problem, arXiv:1603.05119 [math.CO], 16 Jun 2016.
Kevin M. Byrnes, A new method for constructing circuit codes, Bull. ICA, 80 (2017), 40-60.
D. W. Davies, Longest "separated" paths and loops in an N cube, IEEE Trans. Electron. Computers, 14 (1965), 261. [Annotated scanned copy]
Pavel G. Emelyanov, Agung Lukito, On the maximal length of a snake in hypercubes of small dimension Discrete Math. 218 (2000), no. 1-3, 51-59, [From N. J. A. Sloane, Feb 06 2012]
S. Hood, D. Recoskie, J. Sawada, D. Wong, Snakes, coils, and single-track circuit codes with spread k, J. Combin. Optim. 30 (1) (2015) 42-62, Table 1 (lower bounds for n<=17).
V. Klee, What is the maximum length of a d-dimensional snake?, Amer. Math. Monthly, 77 (1970), 63-65.
Krys J. Kochut, Snake-In-The-Box Codes for Dimension 7, Journal of Combinatorial Mathematics and Combinatorial Computing, Vol. 20, pp. 175-185, 1996.
Patric R. J. Östergård and Ville H. Pettersson, Exhaustive Search for Snake-in-the-Box Codes, Preprint, 2014, Journal Graphs and Combinatorics archive, Volume 31 Issue 4, July 2015, Pages 1019-1028.
Patric R. J. Östergård, Ville H. Pettersson, On the maximum length of coil-in-the-box codes in dimension 8, Discrete Applied Mathematics, 2014
K. G. Paterson, J. Tuliani, Some new circuit codes, IEEE Trans. Inform. Theory 44, 1305-1309 (1998). [Shows a(8)=96. - N. J. A. Sloane, Apr 06 2014]
Eric Weisstein's World of Mathematics, Snake.
Wikipedia, Snake-in-the-box.
EXAMPLE
a(4)=8: Path of a longest 4-coil: 0000 1000 1100 1110 0110 0111 0011 0001 0000. See Figure 1 in Kochut.
Solutions of lengths 4,6,8,14 and 26 in dimensions 2..6 from Arlin Anderson (starship1(AT)gmail.com):
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;
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;
CROSSREFS
Cf. A099155, length of maximum n-snake.
Sequence in context: A280227 A181978 A302636 * A138001 A239659 A154387
KEYWORD
nonn,nice,hard,more
AUTHOR
EXTENSIONS
Edited and extended by Hugo Pfoertner, Oct 13 2004
a(8) from Paterson and Tuliani (1998), according to Östergård and Ville (2014). - N. J. A. Sloane, Apr 06 2014
a(1) changed by Hugo Pfoertner, Aug 01 2015
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 21 00:58 EDT 2024. Contains 372720 sequences. (Running on oeis4.)