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.

0, 4, 6, 8, 14, 26, 48, 96

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• nice
• hard
• more

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

Examples

			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;
		

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. A. Casella and W. D. Potter, New Lower Bounds for the Snake-in-the-box Problem: Using Evolutionary Techniques to Hunt for Snakes.
• 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]
• Ville Pettersson, Graph Algorithms for Constructing and Enumerating Cycles and Related Structures, Preprint 2015.
• W. D. Potter, A list of current records for the Snake-in-the-Box problem. [Archived version.]
• Eric Weisstein's World of Mathematics, Snake.
• Wikipedia, Snake-in-the-box.

Crossrefs

Cf. A099155, length of maximum n-snake.

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