|
|
COMMENTS
| 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.
|
|
|
REFERENCES
| 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.
D. W. Davies, Longest "separated" paths and loops in an N cube, IEEE Trans. Electron. Computers, 14 (1965), 261.
Emelyanov, Pavel G.; and Lukito, Agung, 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]
V. Klee, What is the maximum length of a d-dimensional snake?, Amer. Math. Monthly, 77 (1970), 63-65.
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).
|
|
|
LINKS
| D. A. Casella and W. D. Potter, New Lower Bounds for the Snake-in-the-box Problem: Using Evolutionary Techniques to Hunt for Snakes.
Pavel Emelianov, Snake-in-the-box
Krys J. Kochut, Snake-In-The-Box Codes for Dimension 7, Journal of Combinatorial Mathematics and Combinatorial Computing, Vol. 20, pp. 175-185, 1996
Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.
|
|
|
EXAMPLE
| 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;
|
|
|
EXTENSIONS
| Edited and extended by Hugo Pfoertner (hugo(AT)pfoertner.org), Oct 13 2004
After 48, lower bounds on the next terms are 96, 180, 344, 630, 1236. - Darren Casella (artdeco42(AT)yahoo.com), Mar 04 2005
|
