login
This site is supported by donations to The OEIS Foundation.

 

Logo

"Email this user" was broken Aug 14 to 9am Aug 16. If you sent someone a message in this period, please send it again.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A065188 "Greedy Queens" permutation of the natural numbers. 27
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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

LINKS

Alois P. Heinz, Table of n, a(n) for n = 1..10000

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

FORMULA

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

EXAMPLE

The top left corner of the board is:

Qxxxxxxxxx...

xxxQxxxxxx...

xQxxxxxxxx...

xxxxQxxxxx...

xxQxxxxxxx...

xxxxxxxxxQ...

xxxxxxxxxx...

xxxxxxxxxx...

xxxxxQxxxx...

.............

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

MAPLE

# Maple program from Alois P. Heinz, Aug 19 2016. (Start)

# For more terms change the constant 100.

max_diagonal:= 3* 100: # make this large enough -

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

GreedyQueens(256); GreedyQueens := upto_n -> PM2PL(GreedyNonThreateningPermutation(upto_n, -1, -1), upto_n);

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;

CROSSREFS

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.

Sequence in context: A082822 A109313 A176881 * A065257 A258428 A090396

Adjacent sequences:  A065185 A065186 A065187 * A065189 A065190 A065191

KEYWORD

nonn

AUTHOR

Antti Karttunen, Oct 19 2001

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified August 20 20:09 EDT 2017. Contains 290837 sequences.