A357499 -id:A357499 - cp's OEIS frontend

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

Hugo Pfoertner, Oct 11 2004

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

			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.

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.

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.
Randall Munroe, Snake-in-the-Box Problem, xkcd Web Comic #3125, Aug 06 2025.
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 (2002).
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.

Cf. A000937 = length of maximum n-coil.

Row maxima of A357499.

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

A357360 Maximum length of an induced path (or chordless path or snake path) between two antipodal nodes of the n-dimensional hypercube.

Original entry on oeis.org

0, 1, 2, 3, 4, 11, 24

Offset: 0

Pontus von Brömssen, Sep 25 2022

The length is defined as the number of edges along the path, so the number of nodes of the longest path is a(n)+1.

			For n <= 4, the only induced paths between two antipodal nodes are the shortest paths, so a(n) = n.
For n = 5, a longest induced path is 00000 - 10000 - 11000 - 11100 - 01100 - 01110 - 00110 - 00111 - 00011 - 10011 - 11011 - 11111, so a(5) = 11.

Cf. A099155 (the ends of the path does not have to be antipodal), A357234 (paths between opposite corners of a square grid).

Main diagonal of A357499.

a(n) <= A099155(n).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions