cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-2 of 2 results.

A331968 Maximum number of unit squares of a snake-like polyomino in an n X n square box.

Original entry on oeis.org

1, 3, 7, 11, 17, 24, 33, 42, 53, 64, 77, 92, 107, 123, 142, 162, 182
Offset: 1

Views

Author

Alain Goupil, Feb 02 2020

Keywords

Comments

These are similar to the snake-in-the-box problem for the hypercube Q_n (See A099155).
The number of solutions is given by A331986(n).
Equivalently, a(n) is the maximum number of vertices in a path without chords in the n X n grid graph. A path without chords is an induced subgraph that is a path.
These numbers are part of the result of a computer program that counts the snake-like polyominoes in a rectangle of given size b X h by their length.
a(16) >= 161.

Examples

			For n=4, the maximum length of a snake-like polyomino that fits in a square of side 4 is 11 and there are 84 such snakes.
Maximum-length snakes for n = 1 to 4 are shown below.
   X    X X    X X X    X X X X
        X      X   X    X     X
               X   X    X     X
                        X   X X

Links

Crossrefs

Main diagonal of A360917.
Cf. A099155, A047838, A122224, A331986, A332920, A332921, A357357, A357359.

Formula

a(n) >= A047838(n+1).
For n > 2: a(n) >= 2*floor(n/3)*(2n-3*floor(n/3)-2)+5. - Elijah Beregovsky, May 11 2020
a(n) <= (2*n*(n+1)-1)/3. - Elijah Beregovsky, Nov 09 2020
a(n) = 2*n^2/3 + O(n) (Beluhov 2023). - Pontus von Brömssen, Jan 30 2023

Extensions

a(15) from Andrew Howroyd, Feb 04 2020
a(16)-a(17) from Yi Yang, Oct 03 2022

A357358 Length of the longest induced cycle in the n X n torus grid graph.

Original entry on oeis.org

6, 8, 15, 20, 28, 40, 48, 58, 73, 88, 104, 126
Offset: 3

Views

Author

Pontus von Brömssen, Sep 25 2022

Keywords

Comments

It is somewhat unclear how a(2) should be defined. If the 2 X 2 torus grid graph is considered to have multiple edges we have a(2) = 2 (a double edge between two nodes makes a 2-cycle), otherwise a(2) = 4.

Examples

			Longest induced cycles for 3 <= n <= 8:
  X . X   X . . X   X . X . X   X X X . . .   X . X . X . X   X . X . X X . X
  X X .   X X . .   X . X X .   X . X X X .   X . X . X X .   X . X X . X X .
  . X X   . X X .   X X . X .   X X . . X .   X . X X . X .   X X . X X . X .
          . . X X   . X . X X   . X . . X X   X X . X . X .   . X X . X . X X
                    . X X . X   . X X X . X   . X . X . X X   X . X . X X . X
                                . . . X X X   . X . X X . X   X . X X . X X .
                                              . X X . X . X   X X . X X . X .
                                                              . X X . X . X X

Links

Crossrefs

Cf. A000937, A297669, A357357, A357359.

Formula

a(n) ~ 2*n^2/3.
a(n) <= A357359(n) + 1.

Extensions

a(9)-a(12) from Elijah Beregovsky, Dec 11 2022
a(13)-a(14) from Elijah Beregovsky, Dec 13 2022
Showing 1-2 of 2 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.