A380597 Smallest side length of a square board on which Harary's generalized tic-tac-toe (or animal tic-tac-toe) for the free polyomino with binary code A246521(n+1) is a first-player win, or 0 if it is a draw for all board sizes.

1, 2, 3, 4, 4, 0, 5, 3, 7, 0, 0, 0, 7, 7, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

Offset

1,2

Comments

The only unknown value is a(45), corresponding to the "long N" hexomino. It has been suggested that a(45) = 15 and A380598(45) = 13.

Can be read as an irregular triangle, whose n-th row contains A000105(n) terms, n >= 1.

The number of free polyominoes of size k = 1, 2, ... for which the game is a first-player win is 1, 1, 2, 4, 3, x, 0, 0, ..., where x is 0 or 1 and all terms after x are 0.

Links

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

Brady Haran and Sophie Maclean, Snakey Hexomino, Numberphile video, 2025.

Wikipedia, Harary's generalized tic-tac-toe.

James Yolkowski, Tic-tac-toe.

Index entries for sequences related to polyominoes.

Index entries for sequences related to tic-tac-toe.

Formula

a(n) = 0 for all n >= 46.

Example

As an irregular triangle:
  1;
  2;
  3, 4;
  4, 0, 5, 3, 7;
  0, 0, 0, 7, 7, 6, 0, 0, 0, 0, 0, 0;
  ...
For n = 9, the polyomino with binary code A246521(9+1) = 75 is the straight tetromino. Generalized tic-tac-toe for this polyomino (i.e., 4 cells in a row, horizontally or vertically, are needed to win) is a draw for square boards of side length less than 7, but on a 7 X 7 board the first player can force a win in at most 8 moves, so a(9) = 7.

Crossrefs

Cf. A000105, A246521, A380598.

Sequence in context: A384895 A324156 A111362 * A134581 A099587 A172160

Adjacent sequences: A380594 A380595 A380596 * A380598 A380599 A380600

Keyword

nonn,tabf,more

Author

Pontus von Brömssen, Jan 27 2025

Status

approved