

A000937


Length of longest simple cycle without chords in the ndimensional hypercube graph. Also called ncoil or closed nsnakeinthebox problem.
(Formerly M0995 N0373)


14




OFFSET

1,2


COMMENTS

This sequence actually gives the length of a longest closed chordless path in the ndimensional hypercube. To distinguish closed and open paths, newer terminology uses "ncoil" for closed and "nsnake" for open paths. See also A099155.
a(7) was found by exhaustive search by Kochut.
Longest closed achordal path in ndimensional hypercube.
After 48, lower bounds on the next terms are 96, 180, 344, 630, 1236.  Darren Casella (artdeco42(AT)yahoo.com), Mar 04 2005


REFERENCES

D. Casella and W. D. Potter, "New Lower Bounds for the Snakeinthebox 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 Snakeinthebox 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 snakeinthebox", Combinatorica 17.2 (1997): 287298.


LINKS

Eric Weisstein's World of Mathematics, Snake.


EXAMPLE

a(4)=8: Path of a longest 4coil: 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;


CROSSREFS

Cf. A099155, length of maximum nsnake.


KEYWORD

nonn,nice,hard,more


AUTHOR



EXTENSIONS

a(8) from Paterson and Tuliani (1998), according to Östergård and Ville (2014).  N. J. A. Sloane, Apr 06 2014


STATUS

approved



