A275895 "Greedy Queens" permutation of the nonnegative integers.

0, 2, 4, 1, 3, 8, 10, 12, 14, 5, 7, 18, 6, 21, 9, 24, 26, 28, 30, 11, 13, 34, 36, 38, 40, 15, 17, 44, 16, 47, 19, 50, 52, 20, 55, 57, 59, 22, 62, 23, 65, 27, 25, 69, 71, 73, 75, 77, 29, 31, 81, 83, 85, 32, 88, 33, 91, 37, 35, 95, 97, 99, 101, 39, 104, 106, 41, 109, 42, 112, 43, 115, 117, 119, 45, 122

Offset

0,2

Comments

This permutation is produced by a simple greedy algorithm: starting from the top left corner of an infinite chessboard placed in the fourth quadrant of the plane, walk along successive antidiagonals and place a queen in the first available position where it is not threatened by any of the existing queens. In other words, this permutation satisfies the condition that p(i+d) <> p(i)+-d for all i and d >= 1.

The rows and columns are indexed starting at 0. p(n) = k means that a queen appears in column n in row k. - N. J. A. Sloane, Aug 18 2016

All of A065188 (same for positive integers), A065189, A199134, A275884 should really have started at 0 rather than 1. Then the graph of A065188, for example, would be comparable with the graph of A002251.

That this is a permutation of the nonnegative integers follows from the proof in A269526 that every row and every column in that array is a permutation of the positive integers. In particular, every row and every column contains a 0 (which translates to a queen in the present sequence). - N. J. A. Sloane, Dec 10 2017

Links

N. J. A. Sloane, Table of n, a(n) for n = 0..9999

F. Michel Dekking, Jeffrey Shallit, and N. J. A. Sloane, Queens in exile: non-attacking queens on infinite chess boards, Electronic J. Combin., 27:1 (2020), #P1.52.

N. J. A. Sloane, Table of n, a(n) for n = 0..49999

Formula

a(n) = A065188(n+1)-1.

Crossrefs

Cf. A065188 (same for positive integers), A065189 (it's inverse), A199134 (indices of a(n) < n), A275884 (complement), A275894 (same for "nonnegative", i.e., this sequence), A275896 (same for A065189), A002251 (Wythoff pairs).

Sequence in context: A230505 A366062 A208526 * A369292 A158613 A360859

Adjacent sequences: A275892 A275893 A275894 * A275896 A275897 A275898

Keyword

nonn

Author

N. J. A. Sloane, Aug 23 2016

Status

approved