A361154 Consider the square grid with cells {(x,y), x, y >= 0}; label the cells by downwards antidiagonals with nonnegative integers so that cells which are a knight's move apart have different labels; always choose smallest possible label.

0, 0, 0, 1, 0, 1, 1, 2, 2, 1, 0, 1, 2, 1, 0, 0, 0, 2, 2, 0, 0, 1, 0, 3, 1, 3, 0, 1, 1, 1, 2, 4, 4, 2, 1, 1, 0, 1, 2, 3, 0, 3, 2, 1, 0, 0, 0, 2, 2, 0, 0, 2, 2, 0, 0, 1, 0, 3, 3, 1, 0, 1, 3, 3, 0, 1, 1, 1, 2, 3, 1, 2, 2, 1, 3, 2, 1, 1, 0, 1, 2, 3, 0, 1, 2, 1, 0, 3, 2, 1, 0

Offset: 0

Author

N. J. A. Sloane, Mar 07 2023, based on an email from Jodi Spitz, Mar 07 2023

Keywords

• nonn
• tabl

Comments

This can also be described as the lexicographically earliest sequence read by downwards antidiagonals in which knight-adjacent cells have distinct labels. [The direction of the diagonals has to be specified, because it can make a difference - as for example if "knight" is replaced by "bishop", when one gets the non-symmetric array A060510.]

Theorem (Spitz): a(n) <= 4. Proof. True at the start, and then by induction, since when labeling a cell there are at most four existing cells that affect it.

Examples

			The initial antidiagonals are:
  0,
  0, 0,
  1, 0, 1,
  1, 2, 2, 1,
  0, 1, 2, 1, 0,
  0, 0, 2, 2, 0, 0,
  1, 0, 3, 1, 3, 0, 1,
  1, 1, 2, 4, 4, 2, 1, 1,
  0, 1, 2, 3, 0, 3, 2, 1, 0,
  0, 0, 2, 2, 0, 0, 2, 2, 0, 0,
  1, 0, 3, 3, 1, 0, 1, 3, 3, 0, 1,
  1, 1, 2, 3, 1, 2, 2, 1, 3, 2, 1, 1,
  0, 1, 2, 3, 0, 1, 2, 1, 0, 3, 2, 1, 0,
...
		

References

• Jodi Spitz, Email to N. J. A. Sloane, Mar 07 2023

Links

• Rémy Sigrist, Table of n, a(n) for n = 0..10010
• Rémy Sigrist, Initial corner of grid showing first 15 antidiagonals. [Different labels have different colors: 0 = red, 1 = orange, etc.]
• Rémy Sigrist, Initial corner of grid showing cells (x, y) with x, y <= 80 [0 = red, 1 = orange, 2 = yellow, 3 = green, 4 = cyan]
• Rémy Sigrist, PARI program

Crossrefs

Cf. A060510, A308884.

Programs

PARI

See Links section.

Formula

The colors appear to follow an obvious pattern. For example, the red (0) squares appear to be exactly the squares at (4*i + d, 4*j + e), for i and j >= 0, d and e = 0 or 1. The blue (4) squares appear to be exactly the squares at (4*k, 4*k - 1) and (4*k - 1, 4*k), for k >= 1. - N. J. A. Sloane, Mar 07 2023

Extensions

Data corrected by Rémy Sigrist, Mar 07 2023