A000217 and the Chess board

About A000217 and the Chess board

"Imagine a board made of squares (like a Chess board) where one of its squares is completely surrounded by square shaped layers made of adjacent squares. 8*A000217(n)=A033996(n) counts the total number of squares required in order to apply n layers".

"Consider a board (like a Chess board) made of small identical squares, and rectangles composed from those squares. Imagine a rectangle is surrounded in order to hide all its visible sides by applying a layer made with adjacent squares whose width is 1 square. Consider this algorithm: "Hide all visible sides on each square from the input shape (either a rectangle or any set of applied layers) by placing new squares at adjacent positions alternatively avoiding the diagonals (if desired)". A bigger rectangle is obtained if the diagonals were included when building such layer (although they are unnecessary if the goal were strictly using the least possible number of squares). Now consider the total number of required squares in order to complete the application of n layers, 4*A000217(n) counts the difference between avoiding or not the diagonals".

By counting individually the squares per layer when avoiding diagonals, the formula is: 2*(Width+Height)+4*(Layers-1).

In other hand,

By counting individually the squares per layer when including diagonals, the formula is: 2*(Width+Height)+4*(2*Layers-1).

If we subtract both formulas and take summation over "Layers" from 1 to n, the final result after simplifying is 4*A000217.

The following algorithm allows to count for both ways of application the total number of required squares, if a vector containing the sizes of the rectangle and the number of layers to apply are specified. By "full" we mean here to include or not the diagonals ("1" for "Yes", and "0" for "No") due the fact for a practical implementation it implies a search, and some comparisons are omitted or not.

(Begin)

0) Let be "v" a vector with two positive components, "n" a positive integer,
and "full" a flag (zero for false, any other value for true). Input validation
here is implicit.

1.1) Define "A" and assign it the sum of the components
     of "v" plus two.

1.2) Define "B" and assign it twice the sum of the components
     of "v" plus "n*(n+1)" adding this last term only if "full" is true.

1.3) Define "Z".

1.4) Define "C" as the parity of "A"
     ("C" is either zero for even "A", or the unit for odd "A").

2) If "n" is "1" then return "B".

3) Subtract "C" from "A", then divide by 2 and assign the
   result to "A".

4) Assign to "Z" the arithmetic sum: "A+n-2".

5) Return the result of evaluating the expression: "B+2*(Z-A+1)*(Z+A+C)".

(End)

A PARI-GP direct implementation of this algorithm is:

requiredSquaresCountPerAppliedLayers(v,n,full=0)={
  if((#v==2)&&(v[1]>0)&&(v[2]>0),
    if(n<=0,return(0));
    my(A=2+vecsum(v),B=2*(vecsum(v)+(!!full)*n*(n+1)),Z);
    my(C=A%2);
    if(n==1,return(B));
    A-=C;
    A/=2;
    Z=A+n-2;
    return(B+2*(Z-A+1)*(Z+A+C))
    ,
    return(-1) /* Error. The given vector "v" doesn't represent a rectangle.
                         It must contain only two positive integers */
  )
}

Cite this page as

R. J. Cano, A000217_and_the_Chess_board. — From the On-Line Encyclopedia of Integer Sequences® (OEIS®) wiki.Available at https://oeis.org/wiki/A000217_and_the_Chess_board