A319476 a(n) is the minimum number of distinct distances between n non-attacking rooks on an n X n chessboard.

0, 1, 2, 2, 3, 5, 5, 6, 5, 7, 9, 7, 8, 11, 13, 9, 11, 14, 16, 17, 19, 21, 21, 14, 14, 16, 19, 16, 18, 21

Offset

1,3

Comments

a(n) <= n - 1, which is the number of distinct distances the rooks are placed along a diagonal.

Conjecture: a(n^2) = A047800(n-1) - 1. - Peter Kagey, Nov 02 2018

From Martin Fuller, May 02 2026: (Start)

Some results and questions about grid-based arrangements:

A square grid separated by (a,b) can fill the board iff |a^2+b^2-n| <= 1 and a,b are coprime (cf A008784). This is optimal for n=9..14 and others. Consider an n x n window into the infinite version of this grid:

* If n=a^2+b^2+1 then the window must contain a rook at each corner, and two opposite corners must be omitted on the board.

* If n=a^2+b^2 then any window can be used. Some may have fewer distances than others.

* If n=a^2+b^2-1 then the window must be placed with a rook just outside each corner.

A rectangular grid separated by (a,1) and (-1,a)*c can be used iff |(a^2+1)c-n| <= 1 and a,c are coprime. This is optimal for n=19..21. If n=(a^2+1)c+1 then two opposite corners must be omitted.

A rhomboid grid with diagonal symmetry can do better than n-1. Examples: n=7,8,15,23. What are the requirements for this pattern?

Are there any other patterns that can do better than n-1? (End)

Links

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

Martin Fuller, C++ program

Martin Fuller, Illustration of A319476 n=1..30

Giovanni Resta, Illustration of a(3)-a(14)

Example

For n = 7 a board with a(7) = 5 distinct distances is
  +---+---+---+---+---+---+---+
7 |   |   | * |   |   |   |   |
  +---+---+---+---+---+---+---+
6 |   |   |   |   |   | * |   |
  +---+---+---+---+---+---+---+
5 | * |   |   |   |   |   |   |
  +---+---+---+---+---+---+---+
4 |   |   |   | * |   |   |   |
  +---+---+---+---+---+---+---+.
3 |   |   |   |   |   |   | * |
  +---+---+---+---+---+---+---+
2 |   | * |   |   |   |   |   |
  +---+---+---+---+---+---+---+
1 |   |   |   |   | * |   |   |
  +---+---+---+---+---+---+---+
    A   B   C   D   E   F   G
The distances between pairs of points are:
1)   sqrt(10) (e.g., A5 to B2),
2) 2*sqrt(2)  (e.g., A5 to C7),
3) 4*sqrt(2)  (e.g., B2 to F6),
4) 2*sqrt(10) (e.g., A5 to G3), and
5)   sqrt(26) (e.g., A5 to F6).

Prog

(C++) // See Fuller link.

Crossrefs

Cf. A008404, A319476, A320575, A320576, A320448, A320573, A320574.

Sequence in context: A123575 A014200 A293522 * A140200 A289199 A378358

Adjacent sequences: A319473 A319474 A319475 * A319477 A319478 A319479

Keyword

nonn,more

Author

Peter Kagey, Oct 12 2018

Extensions

a(11)-a(14) from Giovanni Resta, Oct 17 2018

a(15)-a(25) from Bert Dobbelaere, Dec 30 2018

a(26)-a(30) from Martin Fuller, May 02 2026

Status

approved