A275884 -id:A275884 - cp's OEIS frontend

A275894 a(n) = A275884(n+1) - 1.

0, 1, 2, 5, 6, 7, 8, 11, 13, 15, 16, 17, 18, 21, 22, 23, 24, 27, 29, 31, 32, 34, 35, 36, 38, 40, 43, 44, 45, 46, 47, 50, 51, 52, 54, 56, 59, 60, 61, 62, 64, 65, 67, 69, 71, 72, 73, 75, 78, 80, 81, 82, 83, 86, 87, 88, 91, 92, 93, 95, 96, 97, 99, 102, 104, 105, 106, 108, 109, 111, 113, 114, 117, 118, 120

Offset: 0

N. J. A. Sloane, Aug 23 2016

nonn

A065188, A065189, A199134, and 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.
From Michel Dekking, Jun 24 2023: (Start)
It is the other way around: the sequence A002251 should have offset 1. This is very logical as the sequence A002251 is defined as the swapping of the sequences L = A000201, U = A001950, two sequences which both have offset 1.
The sequence A002251 already occurs in the OEIS with offset 1 as row 1 in sequence A054081.
(End)

N. J. A. Sloane, Table of n, a(n) for n = 0..30900
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.

Cf. A065188, A065189, A199134, A275884, A275893, A002251.

A275886 Lengths of runs of successive terms in A275884.

Original entry on oeis.org

3, 4, 1, 1, 4, 4, 1, 1, 2, 3, 1, 1, 5, 3, 1, 1, 4, 2, 1, 1, 3, 1, 1, 4, 3, 3, 3, 1, 1, 3, 2, 1, 2, 2, 2, 4, 2, 2, 4, 1, 1, 4, 1, 1, 3, 2, 3, 1, 1, 4, 3, 3, 4, 3, 3, 1, 1, 4, 4, 3, 1, 1, 5, 2, 2, 4, 1, 2, 2, 1, 3, 2, 1, 1, 4, 4, 1, 1, 4, 2, 3, 2, 1, 3, 2, 3, 2, 3, 3, 3, 2, 2, 2, 1, 3, 2, 3, 3, 2, 1, 3

Offset: 1

N. J. A. Sloane, Aug 18 2016

nonn

N. J. A. Sloane, Table of n, a(n) for n = 1..14001

Cf. A065188, A199134, A275884, A275885.

A275888 First differences of A275884.

Original entry on oeis.org

1, 1, 3, 1, 1, 1, 3, 2, 2, 1, 1, 1, 3, 1, 1, 1, 3, 2, 2, 1, 2, 1, 1, 2, 2, 3, 1, 1, 1, 1, 3, 1, 1, 2, 2, 3, 1, 1, 1, 2, 1, 2, 2, 2, 1, 1, 2, 3, 2, 1, 1, 1, 3, 1, 1, 3, 1, 1, 2, 1, 1, 2, 3, 2, 1, 1, 2, 1, 2, 2, 1, 3, 1, 2, 1, 2, 1, 1, 1, 3, 1, 3, 1, 2, 1, 1, 1, 2, 3, 2, 1, 1, 1, 3, 2, 2, 1, 1, 2, 1, 2

Offset: 1

N. J. A. Sloane, Aug 18 2016

nonn

Weak conjecture: a(n) <= 4. Does a 5 ever appear?

Suppose we think of (a(n)) as a sequence of words, each with exactly one 3, that 3 being at the end. Then, it becomes 113, 1113, 221113, 1113, 221211223, .... Empirical evidence suggests that there are exactly 156 possible words. These words range in length from 2 to 26, and all of them appear by n = 109000, with no new words showing up between n = 109000 and n = 618033989. Five of these 156 words contain a 4, and 63 of these words are faithful in the sense that they are always followed by a specific word, at least up to n = 618033989. For details, see "Observations about A275888" in the links below. - Boon Suan Ho, Oct 31 2023

Boon Suan Ho, Table of n, a(n) for n = 1..110000 (first 30900 terms from N. J. A. Sloane)
Boon Suan Ho, Observations about A275888

Cf. A275884.

A065188 "Greedy Queens" permutation of the positive integers.

Original entry on oeis.org

1, 3, 5, 2, 4, 9, 11, 13, 15, 6, 8, 19, 7, 22, 10, 25, 27, 29, 31, 12, 14, 35, 37, 39, 41, 16, 18, 45, 17, 48, 20, 51, 53, 21, 56, 58, 60, 23, 63, 24, 66, 28, 26, 70, 72, 74, 76, 78, 30, 32, 82, 84, 86, 33, 89, 34, 92, 38, 36, 96, 98, 100, 102, 40, 105, 107, 42, 110, 43, 113

Offset: 1

Antti Karttunen, Oct 19 2001

nonn

This permutation is produced by a simple greedy algorithm: starting from the top left corner, walk along each successive antidiagonal of an infinite chessboard 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.
p(n) = k means that a queen appears in column n in row k. - N. J. A. Sloane, Aug 18 2016
That this is a permutation 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 1 (which translates to a queen in the present sequence). - N. J. A. Sloane, Dec 10 2017
The graph of this sequence shows two straight lines of respective slope equal to the Golden Ratio A001622, Phi = 1+phi = (sqrt(5)+1)/2 and phi = 1/Phi = (sqrt(5)-1)/2. - M. F. Hasler, Jan 13 2018
One has a(42) = 28 and a(43) = 26. Such irregularities make it difficult to get an explicit formula. They would not occur if the squares on the antidiagonals had been checked for possible positions starting from the opposite end, so as to ensure that the subsequences corresponding to the points on either line would both be increasing. Then one would have that a(n-1) is either round(n*phi)+1 or round(n/phi)+1. (The +-1's could all be avoided if the origin were taken as a(0) = 0 instead of a(1) = 1.) Presently most values are such that either round(n*phi) or round(n/phi) does not differ by more than 1 from a(n-1)-1, except for very few exceptions of the above form (a(42) being the first of these). - M. F. Hasler, Jan 15 2018
Equivalently, a(n) is the least positive integer not occurring earlier and so that |a(n)-a(k)| <> |n-k| for all k < n; i.e., fill the first quadrant column by column with lowest possible peaceful queens. - M. F. Hasler, Jan 11 2022

			The top left corner of the board is:
  +------------------------
  | Q x x x x x x x x x ...
  | x x x Q x x x x x x ...
  | x Q x x x x x x x x ...
  | x x x x Q x x x x x ...
  | x x Q x x x x x x x ...
  | x x x x x x x x x Q ...
  | x x x x x x x x x x ...
  | x x x x x x x x x x ...
  | x x x x x Q x x x x ...
  | ...
which illustrates p(1)=1, p(2)=3, p(3)=5, p(4)=2, etc. - _N. J. A. Sloane_, Aug 18 2016, corrected Aug 21 2016

Alois P. Heinz, Table of n, a(n) for n = 1..10000
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.
Matteo Fischetti and Domenico Salvagnin, Chasing First Queens by Integer Programming, 2018.
Matteo Fischetti and Domenico Salvagnin, Finding First and Most-Beautiful Queens by Integer Programming, arXiv:1907.08246 [cs.DS], 2019.
N. J. A. Sloane, Scatterplot of first 100 terms
N. J. A. Sloane, Table of n, a(n) for n = 1..50000 [Obtained using the Maple program of _Alois P. Heinz_]
Index entries for sequences that are permutations of the natural numbers

A065185 gives the associated p(i)-i delta sequence. A065186 gives the corresponding permutation for "promoted rooks" used in Shogi, A065257 gives "Quintal Queens" permutation.
A065189 gives inverse permutation.
See A199134, A275884, A275890, A275891, A275892 for information about the split of points below and above the diagonal.
Cf. A269526.
If we subtract 1 and change the offset to 0 we get A275895, A275896, A275893, A275894.
Tracking at which squares along the successive antidiagonals the queens appear gives A275897 and A275898.
Antidiagonal and diagonal indices give A276324 and A276325.

SquareThreatened := proc(a,i,j,upto_n,senw,nesw) local k; for k from 1 to i do if a[k,j] > 0 then RETURN(1); fi; od; for k from 1 to j do if a[i,k] > 0 then RETURN(1); fi; od; if 1 = i and 1 = j then RETURN(0); fi; for k from 1 to `if`((-1 = senw),min(i,j)-1,senw) do if a[i-k,j-k] > 0 then RETURN(1); fi; od; for k from 1 to `if`((-1 = nesw),i-1,nesw) do if a[i-k,j+k] > 0 then RETURN(1); fi; od; for k from 1 to `if`((-1 = nesw),j-1,nesw) do if a[i+k,j-k] > 0 then RETURN(1); fi; od; RETURN(0); end;
GreedyNonThreateningPermutation := proc(upto_n,senw,nesw) local a,i,j; a := array(1..upto_n,1..upto_n); for i from 1 to upto_n do for j from 1 to upto_n do a[i,j] := 0; od; od; for j from 1 to upto_n do for i from 1 to j do if 0 = SquareThreatened(a,i,(j-i+1),upto_n,senw,nesw) then a[i,j-i+1] := 1; fi; od; od; RETURN(eval(a)); end;
PM2PL := proc(a,upto_n) local b,i,j; b := []; for i from 1 to upto_n do for j from 1 to upto_n do if a[i,j] > 0 then break; fi; od; b := [op(b),`if`((j > upto_n),0,j)]; od; RETURN(b); end;
GreedyQueens := upto_n -> PM2PL(GreedyNonThreateningPermutation(upto_n,-1,-1),upto_n);GreedyQueens(256);
# From Alois P. Heinz, Aug 19 2016: (Start)
max_diagonal:= 3 * 100: # make this about 3*max number of terms
h:= proc() true end:   # horizontal line free?
v:= proc() true end:   # vertical   line free?
u:= proc() true end:   # up     diagonal free?
d:= proc() true end:   # down   diagonal free?
a:= proc() 0 end:      # for A065188
b:= proc() 0 end:      # for A065189
for t from 2 to max_diagonal do
   if u(t) then
      for j to t-1 do
        i:= t-j;
        if v(j) and h(i) and d(i-j) then
          v(j),h(i),d(i-j),u(i+j):= false$4;
          a(j):= i;
          b(i):= j;
          break
        fi
      od
   fi
od:
seq(a(n), n=1..100); # this is A065188
seq(b(n), n=1..100); # this is A065189 # (End)

Fold[Function[{a, n}, Append[a, 2 + LengthWhile[Differences@ Union@ Apply[Join, MapIndexed[Select[#2 + #1 {-1, 0, 1}, # > 0 &] & @@ {n - First@ #2, #1} &, a]], # == 1 &]]], {1}, Range[2, 70]] (* Michael De Vlieger, Jan 14 2018 *)

A065188_first(N, a=List(), u=[0])={for(n=1,N, for(x=u[1]+1,oo, setsearch(u,x) && next; for(i=1,n-1, abs(x-a[i])==n-i && next(2)); u=setunion(u,[x]); while(#u>1 && u[2]==u[1]+1, u=u[^1]); listput(a,x); break));a} \\ M. F. Hasler, Jan 11 2022

It would be nice to have a formula! - N. J. A. Sloane, Jun 30 2016

a(n) = A275895(n-1)-1. - M. F. Hasler, Jan 11 2022

A199134 Indices of Greedy Queens (see A065188) below main diagonal.

Original entry on oeis.org

4, 5, 10, 11, 13, 15, 20, 21, 26, 27, 29, 31, 34, 38, 40, 42, 43, 49, 50, 54, 56, 58, 59, 64, 67, 69, 71, 75, 77, 78, 80, 85, 86, 90, 91, 95, 99, 101, 102, 104, 108, 111, 113, 116, 117, 120, 123, 128, 129, 132, 133, 136, 141, 143, 144, 146, 151, 152, 154, 156, 160

Offset: 1

Wouter Meeussen, Nov 04 2011

nonn

The word "below" in the definition is somewhat ambiguous. More precisely, this is the list of n such that A065188(n) < n. - N. J. A. Sloane, Aug 18 2016

For Greedy Queens that do not attack along antidiagonals, the analogous sequence of indices is A026352.

			Greedy Queens take positions (1,1) (2,3) (3,5) (4,2) (5,4) (6,9) ... and the 4th and 5th are below the main diagonal, so a(1)=4 and a(2)=5.

N. J. A. Sloane, Table of n, a(n) for n = 1..19098

Cf. A065188, A026352, A275893 (another version).
A275884 is the complementary sequence.
For runs see A275885, A275886.

<2+Floor[k*GoldenRatio],And[l>3+Floor[k/GoldenRatio],l

A275895 "Greedy Queens" permutation of the nonnegative integers.

Original entry on oeis.org

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

N. J. A. Sloane, Aug 23 2016

nonn

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

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

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

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

A275885 Lengths of runs of successive terms in A199134.

Original entry on oeis.org

2, 2, 1, 1, 2, 2, 1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 1, 2, 2, 1, 1, 2, 2, 2, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 1, 2, 1, 2, 2, 1, 1, 1, 2, 1, 2, 1, 1, 1, 2

Offset: 1

N. J. A. Sloane, Aug 18 2016

nonn

Weak conjecture: all terms are 1, 2 or 3. The first 3 appears at n = 1390. There is no 4 in the first 14000 terms. Does a 4 ever appear?

N. J. A. Sloane, Table of n, a(n) for n = 1..14000

Cf. A065188, A199134, A275884, A275886, A275888.

A275893 a(n) = A199134(n+1)-1.

Original entry on oeis.org

3, 4, 9, 10, 12, 14, 19, 20, 25, 26, 28, 30, 33, 37, 39, 41, 42, 48, 49, 53, 55, 57, 58, 63, 66, 68, 70, 74, 76, 77, 79, 84, 85, 89, 90, 94, 98, 100, 101, 103, 107, 110, 112, 115, 116, 119, 122, 127, 128, 131, 132, 135, 140, 142, 143, 145, 150, 151, 153, 155, 159, 162, 166, 168, 170, 171, 176, 177

Offset: 0

N. J. A. Sloane, Aug 23 2016

nonn

All of A065188, 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.

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

Cf. A065188, A065189, A199134, A275884, A275894, A002251.

A275896 a(n) = A065189(n+1)-1.

Original entry on oeis.org

0, 3, 1, 4, 2, 9, 12, 10, 5, 14, 6, 19, 7, 20, 8, 25, 28, 26, 11, 30, 33, 13, 37, 39, 15, 42, 16, 41, 17, 48, 18, 49, 53, 55, 21, 58, 22, 57, 23, 63, 24, 66, 68, 70, 27, 74, 76, 29, 79, 77, 31, 84, 32, 85, 89, 34, 90, 35, 94, 36, 98, 100, 38, 103, 101, 40, 107, 110, 112, 43, 115, 44, 119, 45, 116, 46

Offset: 0

N. J. A. Sloane, Aug 23 2016

nonn

All of A065188, 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.

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

Cf. A065188, A065189, A199134, A275884, A275894, A275895, A002251.

A294428 Terms of A065188 that are below the main diagonal.

Original entry on oeis.org

2, 4, 6, 8, 7, 10, 12, 14, 16, 18, 17, 20, 21, 23, 24, 28, 26, 30, 32, 33, 34, 38, 36, 40, 42, 43, 44, 46, 47, 50, 49, 52, 54, 55, 57, 59, 61, 62, 65, 64, 67, 68, 69, 71, 75, 73, 77, 79, 81, 80, 83, 85, 87, 88, 91, 90, 93, 95, 94, 97, 99, 101, 103, 104

Offset: 1

N. J. A. Sloane, Nov 06 2017, based on an email from Don Knuth, Oct 31 2017

nonn

This gives another way to view A199134. In fact, a(n) = A065188(A199134(n)).

N. J. A. Sloane, Table of n, a(n) for n = 1..19000

Cf. A065188, A199134, A275884, A294428.

cp's OEIS Frontend

A275894 a(n) = A275884(n+1) - 1.

Views

Author

Keywords

Comments

Links

Crossrefs

A275886 Lengths of runs of successive terms in A275884.

Views

Author

Keywords

Links

Crossrefs

A275888 First differences of A275884.

Views

Author

Keywords

Comments

Links

Crossrefs

A065188 "Greedy Queens" permutation of the positive integers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A199134 Indices of Greedy Queens (see A065188) below main diagonal.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A275895 "Greedy Queens" permutation of the nonnegative integers.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A275885 Lengths of runs of successive terms in A199134.

Views

Author

Keywords

Comments

Links

Crossrefs

A275893 a(n) = A199134(n+1)-1.

Views

Author

Keywords

Comments

Links

Crossrefs

A275896 a(n) = A065189(n+1)-1.

Views

Author

Keywords

Comments

Links

Crossrefs

A294428 Terms of A065188 that are below the main diagonal.

Views

Author

Keywords

Comments

Links

Crossrefs