A099155 Maximum length of a simple path with no chords in the n-dimensional hypercube, also known as snake-in-the-box problem.

0, 1, 2, 4, 7, 13, 26, 50, 98

Offset

0,3

Comments

Some confusion seems to exist in the distinction between n-snakes and n-coils. Earlier papers and also A000937 used "snake" to mean a closed path, which is called n-coil in newer notation, see Harary et al. a(8) is conjectured to be 97 by Rajan and Shende. [The true value, however, is 98. See Ostergard and Ville, 2014. - N. J. A. Sloane, Apr 06 2014]

Longest open achordal path in n-dimensional hypercube.

After 50, lower bounds on the next terms are 97, 186, 358, 680, 1260. - Darren Casella (artdeco42(AT)yahoo.com), Mar 04 2005

The length of the longest known snake (open path) in dimension 8 (as of December, 2009) is 98. It was found by B. Carlson (confirmed by W. D. Potter) and soon to be reported in the literature. Numerous 97-length snakes are currently published. - W. D. Potter (potter(AT)uga.edu), Feb 24 2009

References

B. P. Carlson, D. F. Hougen: Phenotype feedback genetic algorithm operators for heuristic encoding of snakes within hypercubes. In: Proc. 12th Annu. Conf. Genetic and Evolutionary Computation, pp. 791-798 (2010). [Shows a(8) >= 98. - N. J. A. Sloane, Apr 06 2014]

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.

Links

Table of n, a(n) for n=0..8.

David Allison, Daniel Paulusma, New Bounds for the Snake-in-the-Box Problem, arXiv:1603.05119 [math.CO], 16 Jun 2016.

D. A. Casella and W. D. Potter, New Lower Bounds for the Snake-in-the-box Problem: Using Evolutionary Techniques to Hunt for Snakes, 18th International FLAIRS Conference (2005).

F. Harary, J. P. Hayes and H. J. Wu, A survey of the theory of hypercube graphs, Comput. Math. Applic., 15 (1988) 277-289.

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 2 (lower bounds for n<=17)

K. 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, Ville H. Pettersson, Exhaustive Search for Snake-in-the-Box Codes, Graphs and Combinatorics 31, 1019-1028 (2015), shows a(8)=98.

Ville Pettersson, Graph Algorithms for Constructing and Enumerating Cycles and Related Structures, Doctoral Dissertation, 2015.

Potter, W. D., A list of current records for the Snake-in-the-Box problem. [Archived version.]

Potter, W. D., R. W. Robinson, J. A. Miller, K. J. Kochut and D. Z. Redys, Using the Genetic Algorithm to Find Snake In The Box Codes, Proceedings of the Seventh International Conference on Industrial & Engineering Applications of Artificial Intelligence and Expert Systems, pp. 421-426, Austin, Texas, 1994.

Dayanand S. Rajan, Anil M. Shende, Maximal and Reversible Snakes in Hypercubes.

Wikipedia, Snake-in-the-box.

Gilles Zémor, An upper bound on the size of the snake-in-the-box, Combinatorica 17.2 (1997): 287-298.

Example

a(3)=4: Path of a longest 3-snake starts at 000 and then visits 100 101 111 011.
a(4)=7: Path of a longest 4-snake: 0000 1000 1010 1110 0110 0111 0101 1101.
See figures 1 and 2 in Rajan-Shende.

Crossrefs

Cf. A000937 = length of maximum n-coil.

Row maxima of A357499.

Sequence in context: A017995 A251654 A303059 * A342764 A262267 A068031

Adjacent sequences: A099152 A099153 A099154 * A099156 A099157 A099158

Keyword

hard,more,nonn

Author

Hugo Pfoertner, Oct 11 2004

Extensions

a(8) from Patric R. J. Östergård and V. H. Pettersson (2014). - N. J. A. Sloane, Apr 06 2014

a(0) prepended by Pontus von Brömssen, Oct 02 2022

Status

approved