A348484 Maximum number of squares on an n X n chessboard such that no two are two steps apart horizontally or vertically.

1, 4, 5, 8, 13, 20, 25, 32, 41, 52

Offset

1,2

Comments

The sequence 1, 4, 5, 8, 13, ... with g.f. -x*(1 +2*x -2*x^2 +2*x^3 +x^4)/ ((1+x) *(x^2+1) *(x-1)^3) and a(n)= 2*a(n-1) -a(n-2) +a(n-4) -2*a(n-5) +a(n-6) is a lower bound for a(n) achieved by packing 2x2 squares with 1's and 2x2 squares with 0's in a checkerboard pattern into the chessboard. - R. J. Mathar, Dec 03 2022

Links

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

Formula

Conjectures:

a(n) = n^2/2 for n == 0 (mod 4).

a(n) = (n^2 + 1)/2 for n == 1 or 3 (mod 4).

a(n) = n^2/2 + 2 for n == 2 (mod 4).

Example

For n = 1, a(1) = (1^2 + 1)/2 = 1
  1
For n = 2, a(2) = (2^2)/2 + 2 = 4
  11
  11
For n = 3, a(3) = (3^2 + 1)/2 = 5
Starting here the solutions are not unique. We can mix 2X2 blocks from and S shapes along the diagonals.
  110
  110
  001
or
  110
  011
  001
For n = 4, a(4) = (4^2)/2 = 8
  1100
  1100
  0011
  0011
or
  1100
  0110
  0011
  1001
For n = 5, a(5) = (5^2 + 1)/2 = 13
  11001
  11001
  00110
  00110
  11001
or
  11001
  01100
  00110
  10011
  11001
For n = 6, a(6) = (6^6)/2 + 2 = 20
  110011
  110011
  001100
  001100
  110011
  110011

Crossrefs

Cf. A048716.

Sequence in context: A341420 A030978 A101948 * A087475 A019526 A242014

Adjacent sequences: A348481 A348482 A348483 * A348485 A348486 A348487

Keyword

nonn,more

Author

Yang Hong, Oct 20 2021

Status

approved