A065186 -id:A065186 - cp's OEIS frontend

A065188 "Greedy Queens" permutation of the positive integers.

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

A277618 Lexicographically earliest nonnegative sequence such that |a(n+1)-a(n)| is a prime number, and no number occurs twice; a(0) = 0.

Original entry on oeis.org

0, 2, 4, 1, 3, 5, 7, 9, 6, 8, 10, 12, 14, 11, 13, 15, 17, 19, 16, 18, 20, 22, 24, 21, 23, 25, 27, 29, 26, 28, 30, 32, 34, 31, 33, 35, 37, 39, 36, 38, 40, 42, 44, 41, 43, 45, 47, 49, 46, 48, 50, 52, 54, 51, 53, 55, 57, 59, 56, 58, 60, 62, 64, 61, 63, 65, 67, 69, 66, 68, 70, 72, 74, 71, 73, 75, 77, 79, 76, 78, 80, 82, 84, 81, 83, 85, 87, 89, 86, 88, 90

Offset: 0

Eric Angelini and M. F. Hasler, Oct 23 2016

A variant of A277616, which is defined in a similar way with squares > 1 instead of primes.

The steps a(n+1)-a(n) are either +2 or -3, after 10 terms we get a(n+10), and the first 10 terms are all numbers between 0 and 9: This sequence is obviously a permutation of the nonnegative integers, with a(n) = a(n-5) + 5 for all n > 5. The strictly positive variant (starting with a(1) = 1) is given by A065186.

Index entries for linear recurrences with constant coefficients, signature (1,0,0,0,1,-1).

Cf. A277616, A277617, A065186.

Table[n - 2 + Mod[n - 3, 5], {n, 0, 500}] (* Fred Patrick Doty, Aug 03 2020 *)

{u=[a=0];(chk(n)=(!#u||(n>u[1]&&!setsearch(u,n)))&&(u=setunion(u,[n]))&&!while(#u>1&&u[2]==u[1]+1,u=u[^1]));for(n=1,99,print1(a","); for(k=-primepi(a+!a-1),9e9, k||next; chk(a+sign(k)*prime(abs(k)))||next; a+=sign(k)*prime(abs(k));break))}

A277618(n,i=[0,2,4,1,3])=i[n%#i+1]+n\#i*#i

a(n) = a(n-5) + 5 for all n > 5.
a(n) = A065186(n+1) - 1.
G.f.: x*(2*x^4 + 2*x^3 - 3*x^2 + 2*x + 2)/(x^6 - x^5 - x + 1). - Chai Wah Wu, Mar 30 2023

Offset corrected by R. J. Mathar, Jun 19 2021

A065257 Quintal Queens permutation of N: double (mod 5) each digit (0->0, 1->2, 2->4, 3->1, 4->3) of the base-5 representation of n-1, add one.

Original entry on oeis.org

1, 3, 5, 2, 4, 11, 13, 15, 12, 14, 21, 23, 25, 22, 24, 6, 8, 10, 7, 9, 16, 18, 20, 17, 19, 51, 53, 55, 52, 54, 61, 63, 65, 62, 64, 71, 73, 75, 72, 74, 56, 58, 60, 57, 59, 66, 68, 70, 67, 69, 101, 103, 105, 102, 104, 111, 113, 115, 112, 114, 121, 123, 125, 122, 124, 106

Offset: 1

Antti Karttunen, Oct 26 2001

See comment at A065256.

Index entries for sequences that are permutations of the natural numbers

Inverse permutation: A065258. A065257[n] = A004515[n-1]+1. Cf. also A065186, A065188.

[seq(QuintalQueens1(j),j=1..125)]; QuintalQueens0 := n -> DoubleDigits(n,5); QuintalQueens1 := n -> 1+QuintalQueens0(n-1);
DoubleDigits := proc(n,b) local i; add((b^i)*((2*floor(n/(b^i))) mod b),i=0..floor(evalf(log[b](n+1)))+1); end;

A277617 Lexicographically earliest positive sequence such that a(n+1)-a(n) is a square > 1 and no number occurs twice; a(1) = 1.

Original entry on oeis.org

1, 5, 9, 13, 4, 8, 12, 3, 7, 11, 2, 6, 10, 14, 18, 22, 26, 17, 21, 25, 16, 20, 24, 15, 19, 23, 27, 31, 35, 39, 30, 34, 38, 29, 33, 37, 28, 32, 36, 40, 44, 48, 52, 43, 47, 51, 42, 46, 50, 41, 45, 49, 53, 57, 61, 65, 56, 60, 64, 55, 59, 63, 54, 58, 62, 66, 70, 74, 78, 69, 73, 77, 68, 72, 76, 67, 71, 75, 79, 83, 87, 91, 82, 86, 90, 81, 85, 89, 80, 84, 88

Offset: 1

Eric Angelini and M. F. Hasler, Oct 23 2016

A variant of A277616, which is defined in the same way but starts with a(0) = 0.

Another variant is A277618, which is defined in a similar way, but with primes instead of squares. (The strictly positive variant is A065186.)

Paolo Xausa, Table of n, a(n) for n = 1..10000
Index entries for linear recurrences with constant coefficients, signature (1,0,0,0,0,0,0,0,0,0,0,0,1,-1).

Cf. A277616, A277618, A065186.

LinearRecurrence[{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1}, {1, 5, 9, 13, 4, 8, 12, 3, 7, 11, 2, 6, 10, 14}, 100] (* Paolo Xausa, Jan 16 2025 *)

{u=[a=1];(chk(n)=(!#u||(n>u[1]&&!setsearch(u,n)))&&(u=setunion(u,[n]))&&!while(#u>1&&u[2]==u[1]+1,u=u[^1]));for(n=1,99,print1(a",");for(k=-sqrtint(a+!a-1),9e9,k^2>1||next;chk(a+k*abs(k))||next;a+=k*abs(k);break))}

From Chai Wah Wu, Mar 30 2023: (Start)
a(n) = a(n-1) + a(n-13) - a(n-14) for n > 14.
G.f.: x*(3*x^13 + 4*x^12 + 4*x^11 - 9*x^10 + 4*x^9 + 4*x^8 - 9*x^7 + 4*x^6 + 4*x^5 - 9*x^4 + 4*x^3 + 4*x^2 + 4*x + 1)/(x^14 - x^13 - x + 1). (End)

A308334 Lexicographically earliest sequence of distinct positive numbers such that for any n > 0, a(n) OR a(n+1) is a prime number (where OR denotes the bitwise OR operator).

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 16, 13, 8, 11, 9, 10, 21, 12, 17, 14, 19, 15, 18, 23, 20, 25, 22, 27, 28, 29, 24, 31, 26, 33, 36, 37, 32, 41, 34, 43, 35, 40, 39, 42, 45, 38, 47, 44, 49, 52, 53, 48, 59, 50, 57, 51, 56, 61, 60, 67, 62, 65, 63, 64, 71, 58, 69, 66, 77, 54

Offset: 1

Rémy Sigrist, May 20 2019

By Dirichlet's theorem on arithmetic progressions, we can always extend the sequence: say a(n) < 2^k, then a(n) OR 1 and 2^k are coprime and there are infinitely many prime numbers of the form (a(n) OR 1) + m*2^k = a(n) OR (1 + m*2^k) and we can extend the sequence.
Will every integer appear in this sequence?
Numerous sequences are based on the same model: the sequence is the lexicographically earliest sequence of distinct positive terms such that some function in two variables yields prime numbers when applied to consecutive terms:
  f(u,v)      Analog sequence
  -------     -----------------
  u OR v      a (this sequence)
  u + v       A055265
  u*v + 1     A073666
  u*v - 1     A081943
  abs(u-v)    A065186
  max(u,v)    A282649
  u^2 + v^2   A100208
The appearance of numbers much earlier or later than their corresponding index is flagged strikingly in the plot2 graph of a(n)/n (see links). - Peter Munn, Sep 10 2022

			The first terms, alongside a(n) OR a(n+1), are:
  n   a(n)  a(n) OR a(n+1)
  --  ----  --------------
   1     1               3
   2     2               3
   3     3               7
   4     4               5
   5     5               7
   6     6               7
   7     7              23
   8    16              29
   9    13              13
  10     8              11
  11    11              11
  12     9              11

Rémy Sigrist, Table of n, a(n) for n = 1..10000
Peter Munn, Plot2 graph of a(n)/n

See A308340 for the corresponding prime numbers.

See A055265, A065186, A073666, A081943, A100208, A282649 for similar sequences.

s=0; v=1; for (n=1, 67, s+=2^v; print1 (v ", "); for (w=1, oo, if (!bittest(s,w) && isprime(o=bitor(v,w)), v=w; break)))

from sympy import isprime
from itertools import count, islice
def agen():
    aset, k, mink = {1}, 1, 2
    for n in count(1):
        an = k; yield an; aset.add(an)
        s, k = set(str(an)), mink
        while k in aset or not isprime(an|k): k += 1
        while mink in aset: mink += 1
print(list(islice(agen(), 67))) # Michael S. Branicky, Sep 10 2022

cp's OEIS Frontend

A065187 "Greedy Dragons" permutation of the natural numbers, inverse of A065186.

Views

Author

Keywords

Links

Programs

Mathematica

Formula

A065188 "Greedy Queens" permutation of the positive integers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A277618 Lexicographically earliest nonnegative sequence such that |a(n+1)-a(n)| is a prime number, and no number occurs twice; a(0) = 0.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A065257 Quintal Queens permutation of N: double (mod 5) each digit (0->0, 1->2, 2->4, 3->1, 4->3) of the base-5 representation of n-1, add one.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

A277617 Lexicographically earliest positive sequence such that a(n+1)-a(n) is a square > 1 and no number occurs twice; a(1) = 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A308334 Lexicographically earliest sequence of distinct positive numbers such that for any n > 0, a(n) OR a(n+1) is a prime number (where OR denotes the bitwise OR operator).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Python