

A099155


Maximum length of a simple path with no chords in the ndimensional hypercube, also known as snakeinthebox problem.


4




OFFSET

1,2


COMMENTS

Some confusion seems to exist in the distinction between nsnakes and ncoils. Earlier papers and also A000937 used "snake" to mean a closed path, which is called ncoil 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 ndimensional hypercube.
After 50, lower bounds on the next terms are 97, 186, 358, 680, 1260.  Darren Casella (artdeco42(AT)yahoo.com), Mar 04 2005
For current records see Potter link.
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 97length snakes are currently published.  W. D. Potter (potter(AT)uga.edu), Feb 24 2009


REFERENCES

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. 791798 (2010). [Shows a(8) >= 98.  N. J. A. Sloane, Apr 06 2014]
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.
F. Harary, J. P. Hayes and H. J. Wu, A survey of the theory of hypercube graphs, Comput. Math. Applic., 15 (1988) 277289.
Patric R. J. Östergård and V. H. Pettersson, Exhaustive Search for SnakeintheBox Codes, Preprint, 2014; http://users.tkk.fi/~pat/papers/snake.pdf. [Shows a(8)=98.  N. J. A. Sloane, Apr 06 2014] [Broken link]
Gilles Zémor, "An upper bound on the size of the snakeinthebox", Combinatorica 17.2 (1997): 287298.


LINKS

Table of n, a(n) for n=1..8.
David Allison, Daniel Paulusma, New Bounds for the SnakeintheBox Problem, arXiv:1603.05119 [math.CO], 16 Jun 2016.
D. A. Casella and W. D. Potter, New Lower Bounds for the Snakeinthebox Problem: Using Evolutionary Techniques to Hunt for Snakes.
K. J. Kochut, SnakeInTheBox Codes for Dimension 7, Journal of Combinatorial Mathematics and Combinatorial Computing, Vol. 20, pp. 175185, 1996.
Patric R. J. Östergård, Ville H. Pettersson, Exhaustive Search for SnakeintheBox Codes, Graphs and Combinatorics 31, 10191028 (2015).
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 SnakeintheBox problem.
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. 421426, Austin, Texas, 1994.
Dayanand S. Rajan, Anil M. Shende, Maximal and Reversible Snakes in Hypercubes.


EXAMPLE

a(3)=4: Path of a longest 3snake starts at 000 and then visits 100 101 111 011.
a(4)=7: Path of a longest 4snake: 0000 1000 1010 1110 0110 0111 0101 1101.
See figures 1 and 2 in RajanShende.


CROSSREFS

Cf. A000937 = length of maximum ncoil.
Sequence in context: A017995 A251654 A303059 * A262267 A068031 A293314
Adjacent sequences: A099152 A099153 A099154 * A099156 A099157 A099158


KEYWORD

hard,more,nonn


AUTHOR

Hugo Pfoertner, Oct 11 2004


EXTENSIONS

a(8) from Patric R. J. Östergård and V. H. Pettersson (2014).  N. J. A. Sloane, Apr 06 2014


STATUS

approved



