login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A099155 Maximum length of a simple path with no chords in the n-dimensional hypercube, also known as snake-in-the-box problem. 1
1, 2, 4, 7, 13, 26, 50, 98 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

Some confusion seems to exist in the distinction between n-snakes and n-coils. Earlier papers and also A000937 used "snake" to mean a closed path, which is called n-coil 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 n-dimensional 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 97-length snakes are currently published. - W. D. Potter (potter(AT)uga.edu), Feb 24 2009

REFERENCES

Carlson, B.P., Hougen, D.F.: Phenotype feedback genetic algorithm operators for heuristic encoding of snakes within hypercubes. In: Proc. 12th Annu. Conf. Genetic and Evolutionary Computation, pp. 791-798 (2010). [Shows a(8) >= 98. - N. J. A. Sloane, Apr 06 2014]

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.

F. Harary, J. P. Hayes and H. J. Wu, A survey of the theory of hypercube graphs, Comput. Math. Applic., 15 (1988) 277-289.

P. R. J. Ostergard and V. H. Pettersson, Exhaustive Search for Snake-in-the-Box Codes, Preprint, 2014; http://users.tkk.fi/~pat/papers/snake.pdf. [Shows a(8)=98. - N. J. A. Sloane, Apr 06 2014]

Ville Pettersson, Graph Algorithms for Constructing and Enumerating Cycles and Related Structures, Preprint 2015, https://aaltodoc.aalto.fi/bitstream/handle/123456789/17688/isbn9789526063652.pdf?sequence=1

ZĂ©mor, Gilles. "An upper bound on the size of the snake-in-the-box." Combinatorica 17.2 (1997): 287-298.

LINKS

Table of n, a(n) for n=1..8.

D. A. Casella and W. D. Potter, New Lower Bounds for the Snake-in-the-box Problem: Using Evolutionary Techniques to Hunt for Snakes.

K. J. Kochut, Snake-In-The-Box Codes for Dimension 7, Journal of Combinatorial Mathematics and Combinatorial Computing, Vol. 20, pp. 175-185, 1996

Potter, W. D., A list of current records for the Snake-in-the-Box 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. 421-426, Austin, Texas, 1994

Dayanand S. Rajan, Anil M. Shende, Maximal and Reversible Snakes in Hypercubes.

EXAMPLE

a(3)=4: Path of a longest 3-snake starts at 000 and then visits 100 101 111 011.

a(4)=7: Path of a longest 4-snake: 0000 1000 1010 1110 0110 0111 0101 1101.

See figures 1 and 2 in Rajan-Shende.

CROSSREFS

Cf. A000937 = length of maximum n-coil.

Sequence in context: A103204 A017995 A251654 * 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 P. R. J. Ostergard and V. H. Pettersson (2014). - N. J. A. Sloane, Apr 06 2014

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 20 16:25 EST 2018. Contains 299380 sequences. (Running on oeis4.)