A000937 -id:A000937 - 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

A357357 Length of the longest induced cycle in the n X n grid graph.

Original entry on oeis.org

0, 4, 8, 12, 16, 20, 32, 40, 50, 62, 76, 90, 104, 120, 140, 160, 180

Offset: 1

Pontus von Brömssen, Sep 25 2022

			For 2 <= n <= 6, a longest induced cycle is the one going around the border of the grid, so a(n) = 4*(n-1).
Longest induced cycles for 6 <= n <= 8:
  X X X X X X   X X X X X X X   X X X X X X X X
  X . . . . X   X . . . . . X   X . . . . . . X
  X . . . . X   X . X X X . X   X . X X X . X X
  X . . . . X   X . X . X . X   X . X . X . X .
  X . . . . X   X . X . X . X   X . X . X . X X
  X X X X X X   X . X . X . X   X . X . X . . X
                X X X . X X X   X . X . X . . X
                                X X X . X X X X

Nikolai Beluhov, Snake paths in king and knight graphs, arXiv:2301.01152 [math.CO], 2023.
Elijah Beregovsky, Illustration of initial terms.
Eric Weisstein's World of Mathematics, Grid Graph.
Wikipedia, Induced path.

Main diagonal of A360915.

Cf. A000937, A297664, A331968, A357358, A360914 (number of longest induced cycles).

a(n) <= A331968(n)+1.

a(n) = 2*n^2/3 + O(n) (Beluhov 2023). - Pontus von Brömssen, Jan 30 2023

a(9)-a(12) from Elijah Beregovsky, Nov 24 2022
a(13) from Elijah Beregovsky, Nov 25 2022
a(14)-a(17) from Andrew Howroyd, Feb 26 2023

A357620 Length of longest induced cycle (or chordless cycle) in the n-Fibonacci cube graph.

Original entry on oeis.org

0, 0, 0, 4, 4, 10, 14, 18, 30, 46

Offset: 0

Pontus von Brömssen, Oct 06 2022

Wikipedia, Fibonacci cube.
Wikipedia, Induced path.

Cf. A000937, A297668, A357619.

a(n) <= A357619(n) + 2.

a(9) from Elijah Beregovsky, Dec 03 2022

A358356 Maximum length of an induced cycle (or chordless cycle) in the n-halved cube graph.

Original entry on oeis.org

0, 0, 3, 4, 5, 8, 12, 20

Offset: 1

Pontus von Brömssen, Nov 12 2022

Eric Weisstein's World of Mathematics, Halved Cube Graph.
Wikipedia, Halved cube graph.
Wikipedia, Induced path.

Cf. A000937, A357620, A358355, A358358.

a(n) <= A358355(n)+2.

A358358 Maximum length of an induced cycle (or chordless cycle) in the n-folded cube graph.

Original entry on oeis.org

0, 3, 4, 6, 12, 24

Offset: 2

Pontus von Brömssen, Nov 12 2022

Eric Weisstein's World of Mathematics, Folded Cube Graph.
Wikipedia, Folded cube graph.
Wikipedia, Induced path.

Cf. A000937, A357620, A358356, A358357.

a(n) <= A358357(n)+2. Equality holds for 3 <= n <= 7.

A361149 Number of chordless cycles in the n-hypercube graph Q_n.

Original entry on oeis.org

0, 0, 1, 10, 224, 22176, 149137552

Offset: 0

Eric W. Weisstein, Mar 03 2023

Eric Weisstein's World of Mathematics, Chordless Cycle
Eric Weisstein's World of Mathematics, Hypercube Graph

Cf. A000937.

a(6) from Pontus von Brömssen, Apr 17 2023

A289424 a(n) = length of longest circuit code K(n,3).

Original entry on oeis.org

0, 4, 6, 8, 10, 16, 24, 36

Offset: 1

N. J. A. Sloane, Jul 06 2017

Kevin M. Byrnes, A new method for constructing circuit codes, Bull. ICA, 80 (2017), 40-60.

Cf. A000937, A289425, A289426.

A289425 a(n) = length of longest circuit code K(n,4).

Original entry on oeis.org

0, 4, 6, 8, 10, 12, 14, 22, 30, 46

Offset: 1

N. J. A. Sloane, Jul 06 2017

Kevin M. Byrnes, A new method for constructing circuit codes, Bull. ICA, 80 (2017), 40-60.

Cf. A000937, A289424, A289426.

A289426 a(n) = length of longest circuit code K(n,5).

Original entry on oeis.org

0, 4, 6, 8, 10, 12, 14, 16, 24, 28, 40

Offset: 1

N. J. A. Sloane, Jul 06 2017

Kevin M. Byrnes, A new method for constructing circuit codes, Bull. ICA, 80 (2017), 40-60.

Cf. A000937, A289424, A289425.

A357358 Length of the longest induced cycle in the n X n torus grid graph.

Original entry on oeis.org

6, 8, 15, 20, 28, 40, 48, 58, 73, 88, 104, 126

Offset: 3

Pontus von Brömssen, Sep 25 2022

It is somewhat unclear how a(2) should be defined. If the 2 X 2 torus grid graph is considered to have multiple edges we have a(2) = 2 (a double edge between two nodes makes a 2-cycle), otherwise a(2) = 4.

			Longest induced cycles for 3 <= n <= 8:
  X . X   X . . X   X . X . X   X X X . . .   X . X . X . X   X . X . X X . X
  X X .   X X . .   X . X X .   X . X X X .   X . X . X X .   X . X X . X X .
  . X X   . X X .   X X . X .   X X . . X .   X . X X . X .   X X . X X . X .
          . . X X   . X . X X   . X . . X X   X X . X . X .   . X X . X . X X
                    . X X . X   . X X X . X   . X . X . X X   X . X . X X . X
                                . . . X X X   . X . X X . X   X . X X . X X .
                                              . X X . X . X   X X . X X . X .
                                                              . X X . X . X X

Wikipedia, Induced path.

Cf. A000937, A297669, A357357, A357359.

a(n) ~ 2*n^2/3.

a(n) <= A357359(n) + 1.

a(9)-a(12) from Elijah Beregovsky, Dec 11 2022

a(13)-a(14) from Elijah Beregovsky, Dec 13 2022

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

A357357 Length of the longest induced cycle in the n X n grid graph.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions

A357620 Length of longest induced cycle (or chordless cycle) in the n-Fibonacci cube graph.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A358356 Maximum length of an induced cycle (or chordless cycle) in the n-halved cube graph.

Views

Author

Keywords

Links

Crossrefs

Formula

A358358 Maximum length of an induced cycle (or chordless cycle) in the n-folded cube graph.

Views

Author

Keywords

Links

Crossrefs

Formula

A361149 Number of chordless cycles in the n-hypercube graph Q_n.

Views

Author

Keywords

Links

Crossrefs

Extensions

A289424 a(n) = length of longest circuit code K(n,3).

Views

Author

Keywords

Links

Crossrefs

A289425 a(n) = length of longest circuit code K(n,4).

Views

Author

Keywords

Links

Crossrefs

A289426 a(n) = length of longest circuit code K(n,5).

Views

Author

Keywords

Links

Crossrefs

A357358 Length of the longest induced cycle in the n X n torus grid graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions