|
Search: id:A000937
|
|
|
| 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.
(Formerly M0995 N0373)
|
|
+0
4
|
| |
|
|
OFFSET
|
1,1
|
|
|
COMMENT
|
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.
V. Klee, What is the maximum length of a d-dimensional snake?, Amer. Math. Monthly, 77 (1970), 63-65.
|
|
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;
|
|
CROSSREFS
|
Cf. A099155, length of maximum n-snake.
Sequence in context: A049015 A005250 A039597 this_sequence A068902 A077569 A073935
Adjacent sequences: A000934 A000935 A000936 this_sequence A000938 A000939 A000940
|
|
KEYWORD
|
nonn,nice,hard
|
|
AUTHOR
|
njas
|
|
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
|
|
|
Search completed in 0.002 seconds
|
