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

Author

Yang Hong, Oct 20 2021

Keywords

• nonn
• more

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

Examples

			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.

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