cp's OEIS Frontend

A065188 "Greedy Queens" permutation of the positive integers.

%I A065188 #92 Jan 11 2022 12:35:20
%S A065188 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,
%T A065188 18,45,17,48,20,51,53,21,56,58,60,23,63,24,66,28,26,70,72,74,76,78,30,
%U A065188 32,82,84,86,33,89,34,92,38,36,96,98,100,102,40,105,107,42,110,43,113
%N A065188 "Greedy Queens" permutation of the positive integers.
%C A065188 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.
%C A065188 p(n) = k means that a queen appears in column n in row k. - _N. J. A. Sloane_, Aug 18 2016
%C A065188 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
%C A065188 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
%C A065188 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
%C A065188 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
%H A065188 Alois P. Heinz, <a href="/A065188/b065188.txt">Table of n, a(n) for n = 1..10000</a>
%H A065188 F. Michel Dekking, Jeffrey Shallit, and N. J. A. Sloane, <a href="https://doi.org/10.37236/8905">Queens in exile: non-attacking queens on infinite chess boards</a>, Electronic J. Combin., 27:1 (2020), #P1.52.
%H A065188 Matteo Fischetti and Domenico Salvagnin, <a href="https://www.researchgate.net/profile/Matteo_Fischetti/publication/322508723_Chasing_First_Queens_by_Integer_Programming/links/5a5cf3620f7e9b4f78396d0b/Chasing-First-Queens-by-Integer-Programming.pdf">Chasing First Queens by Integer Programming</a>, 2018.
%H A065188 Matteo Fischetti and Domenico Salvagnin, <a href="https://arxiv.org/abs/1907.08246">Finding First and Most-Beautiful Queens by Integer Programming</a>, arXiv:1907.08246 [cs.DS], 2019.
%H A065188 N. J. A. Sloane, <a href="/A065188/a065188.pdf">Scatterplot of first 100 terms</a>
%H A065188 N. J. A. Sloane, <a href="/A065188/a065188.txt">Table of n, a(n) for n = 1..50000</a> [Obtained using the Maple program of _Alois P. Heinz_]
%H A065188 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%F A065188 It would be nice to have a formula! - _N. J. A. Sloane_, Jun 30 2016
%F A065188 a(n) = A275895(n-1)-1. - _M. F. Hasler_, Jan 11 2022
%e A065188 The top left corner of the board is:
%e A065188   +------------------------
%e A065188   | Q x x x x x x x x x ...
%e A065188   | x x x Q x x x x x x ...
%e A065188   | x Q x x x x x x x x ...
%e A065188   | x x x x Q x x x x x ...
%e A065188   | x x Q x x x x x x x ...
%e A065188   | x x x x x x x x x Q ...
%e A065188   | x x x x x x x x x x ...
%e A065188   | x x x x x x x x x x ...
%e A065188   | x x x x x Q x x x x ...
%e A065188   | ...
%e A065188 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
%p A065188 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;
%p A065188 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;
%p A065188 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;
%p A065188 GreedyQueens := upto_n -> PM2PL(GreedyNonThreateningPermutation(upto_n,-1,-1),upto_n);GreedyQueens(256);
%p A065188 # From _Alois P. Heinz_, Aug 19 2016: (Start)
%p A065188 max_diagonal:= 3 * 100: # make this about 3*max number of terms
%p A065188 h:= proc() true end:   # horizontal line free?
%p A065188 v:= proc() true end:   # vertical   line free?
%p A065188 u:= proc() true end:   # up     diagonal free?
%p A065188 d:= proc() true end:   # down   diagonal free?
%p A065188 a:= proc() 0 end:      # for A065188
%p A065188 b:= proc() 0 end:      # for A065189
%p A065188 for t from 2 to max_diagonal do
%p A065188    if u(t) then
%p A065188       for j to t-1 do
%p A065188         i:= t-j;
%p A065188         if v(j) and h(i) and d(i-j) then
%p A065188           v(j),h(i),d(i-j),u(i+j):= false$4;
%p A065188           a(j):= i;
%p A065188           b(i):= j;
%p A065188           break
%p A065188         fi
%p A065188       od
%p A065188    fi
%p A065188 od:
%p A065188 seq(a(n), n=1..100); # this is A065188
%p A065188 seq(b(n), n=1..100); # this is A065189 # (End)
%t A065188 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 *)
%o A065188 (PARI) 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
%Y A065188 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.
%Y A065188 A065189 gives inverse permutation.
%Y A065188 See A199134, A275884, A275890, A275891, A275892 for information about the split of points below and above the diagonal.
%Y A065188 Cf. A269526.
%Y A065188 If we subtract 1 and change the offset to 0 we get A275895, A275896, A275893, A275894.
%Y A065188 Tracking at which squares along the successive antidiagonals the queens appear gives A275897 and A275898.
%Y A065188 Antidiagonal and diagonal indices give A276324 and A276325.
%K A065188 nonn
%O A065188 1,2
%A A065188 _Antti Karttunen_, Oct 19 2001