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

Author

Pontus von Brömssen, Jan 27 2025

Keywords

• nonn
• tabf
• more

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.

Examples

			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.
		

Links

• 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.

Crossrefs

Cf. A000105, A246521, A380598.

Formula

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