A099155 -id:A099155 - cp's OEIS frontend

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

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

			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;

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.

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.

Cf. A099155, length of maximum n-snake.

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

A331968 Maximum number of unit squares of a snake-like polyomino in an n X n square box.

Original entry on oeis.org

1, 3, 7, 11, 17, 24, 33, 42, 53, 64, 77, 92, 107, 123, 142, 162, 182

Offset: 1

Alain Goupil, Feb 02 2020

These are similar to the snake-in-the-box problem for the hypercube Q_n (See A099155).
The number of solutions is given by A331986(n).
Equivalently, a(n) is the maximum number of vertices in a path without chords in the n X n grid graph. A path without chords is an induced subgraph that is a path.
These numbers are part of the result of a computer program that counts the snake-like polyominoes in a rectangle of given size b X h by their length.
a(16) >= 161.

			For n=4, the maximum length of a snake-like polyomino that fits in a square of side 4 is 11 and there are 84 such snakes.
Maximum-length snakes for n = 1 to 4 are shown below.
   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.
Alain Goupil, Illustration of initial terms
Eric Weisstein's World of Mathematics, Grid Graph

Main diagonal of A360917.

Cf. A099155, A047838, A122224, A331986, A332920, A332921, A357357, A357359.

a(n) >= A047838(n+1).
For n > 2: a(n) >= 2*floor(n/3)*(2n-3*floor(n/3)-2)+5. - Elijah Beregovsky, May 11 2020
a(n) <= (2*n*(n+1)-1)/3. - Elijah Beregovsky, Nov 09 2020
a(n) = 2*n^2/3 + O(n) (Beluhov 2023). - Pontus von Brömssen, Jan 30 2023

a(15) from Andrew Howroyd, Feb 04 2020

a(16)-a(17) from Yi Yang, Oct 03 2022

A331986 Number of snake-like polyominoes with the maximum possible number of unit squares in an n X n square.

Original entry on oeis.org

1, 4, 8, 84, 56, 136, 52, 216, 16, 1504, 2352, 1152, 1344, 123216, 82432, 11008, 308992

Offset: 1

Alain Goupil, Feb 03 2020

The maximum possible number of unit squares is given by A331968(n).
Equivalently, a(n) is the number of maximum length paths without chords in the n X n grid graph. A path without chords is an induced subgraph that is a path.
For n > 1, a(n) is a multiple of 4 since a solution can have at most one symmetry considering rotations and reflections. - Andrew Howroyd, Feb 04 2020

			For n = 4 the number of snake-like polyominoes with 11 cells is 84.

Eric Weisstein's World of Mathematics, Grid Graph

Main diagonal of A360916.
Cf. A331968, A059525 (connected induced subgraphs), A099155.
Cf. A332920 (non-isomorphic snakes), A332921 (symmetric snakes).

a(15) from Andrew Howroyd, Feb 04 2020

a(16)-a(17) from Yi Yang, Oct 03 2022

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

Original entry on oeis.org

0, 1, 2, 3, 6, 9, 13, 20, 30

Offset: 0

Pontus von Brömssen, Oct 06 2022

Wikipedia, Fibonacci cube.

Cf. A099155, A357620.

a(n) >= A357620(n) - 2.

A357499 Triangle read by rows: T(n,k) is the length of the longest induced path in the n-dimensional hypercube, such that the end points of the path are at Hamming distance k, 0 <= k <= n.

Original entry on oeis.org

0, 0, 1, 0, 1, 2, 0, 1, 4, 3, 0, 1, 6, 7, 4, 0, 1, 12, 13, 12, 11, 0, 1, 26, 25, 24, 25, 24

Offset: 0

Pontus von Brömssen, Oct 01 2022

			Triangle begins:
  n\k| 0  1  2  3  4  5  6
  ---+--------------------
   0 | 0
   1 | 0  1
   2 | 0  1  2
   3 | 0  1  4  3
   4 | 0  1  6  7  4
   5 | 0  1 12 13 12 11
   6 | 0  1 26 25 24 25 24

Wikipedia, Snake-in-the-box.

Cf. A099155 (row maxima), A357360 (main diagonal).

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

Original entry on oeis.org

0, 1, 1, 2, 3, 6, 11, 18

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. A099155, A357619, A358356, A358357.

a(n) >= A358356(n) - 2.

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

Original entry on oeis.org

1, 1, 2, 4, 10, 22

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. A099155, A357619, A358355, A358358.

a(n) >= A358358(n)-2. Equality holds for 3 <= n <= 7.

For n > 2, a(n) <= (2^(n-2)*n-1)/(n-1)-1. - Elijah Beregovsky, Dec 22 2022

A330079 Number of n-step self-avoiding walks starting at the origin that are restricted to the boundary walls of the first octant of the cubic lattice.

Original entry on oeis.org

1, 3, 9, 27, 75, 213, 585, 1623, 4425, 12123, 32883, 89415, 241557, 653649, 1760427, 4747005, 12754593, 34301463, 91990575, 246880023, 661075149, 1771199169, 4736741853, 12673587057, 33856816431, 90482953989, 241499070195, 644781165933, 1719559634451, 4587222964881, 12225165127887

Offset: 0

Francois Alcover, Nov 30 2019

These are walks in the first octant of the cubic lattice, never leaving the three walls forming the octant. The walls are the sets of points (x>=0, y>=0, z=0), (x>=0, y=0, z>=0), and (x=0, y>=0, z>=0) with (x,y,z) in Z^3.

Francois Alcover, 14-step walk
Francois Alcover, nodejs script

Cf. A001411, A001412.

The "snake in the box" problem (A000937, A099155) has a similar flavor. - N. J. A. Sloane, Dec 01 2019

a(18)-a(25) Scott R. Shannon, Aug 17 2020

a(26)-a(30) from Bert Dobbelaere, Oct 28 2023

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

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A331968 Maximum number of unit squares of a snake-like polyomino in an n X n square box.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A331986 Number of snake-like polyominoes with the maximum possible number of unit squares in an n X n square.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Formula

A357499 Triangle read by rows: T(n,k) is the length of the longest induced path in the n-dimensional hypercube, such that the end points of the path are at Hamming distance k, 0 <= k <= n.

Views

Author

Keywords

Examples

Links

Crossrefs

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

Views

Author

Keywords

Links

Crossrefs

Formula

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

Views

Author

Keywords

Links

Crossrefs

Formula

A330079 Number of n-step self-avoiding walks starting at the origin that are restricted to the boundary walls of the first octant of the cubic lattice.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula