[seqfan] Re: A269526, an infinite Sudoku-type array

Fri Jul 1 20:42:12 CEST 2016

Rob, I created a new entry A274177 for the solution to the nonattacking
queens on a triangular board (and I corrected the comment and the reference
in A004396).

For a board of size K (with K(K+1)/2) squares, as you say, the max number
is roughly 2K/3. This is enough to complete Bob's proof that every row in
A269526 is a permutation.

Proving that the diagonals are permutations will involve a similar argument
although I didn't check all the details yet.

Best regards
Neil

Neil J. A. Sloane, President, OEIS Foundation.
11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
Phone: 732 828 6098; home page: http://NeilSloane.com
Email: njasloane at gmail.com

On Fri, Jul 1, 2016 at 11:23 AM, Rob Pratt <Rob.Pratt at sas.com> wrote:

> It doesn't appear to be in OEIS.
>
> The first 50 terms are:
> 1, 1, 2, 2, 3, 4, 5, 5, 6, 7, 7, 8, 9, 9, 10, 11, 11, 12, 13, 13, 14, 15,
> 15, 16, 17, 17, 18, 19, 19, 20, 21, 21, 22, 23, 23, 24, 25, 25, 26, 27, 27,
> 28, 29, 29, 30, 31, 31, 32, 33, 33
>
> Except for n = 4, it looks like round(2n/3).  See first comment in
> http://oeis.org/A004396.
>
> -----Original Message-----
> From: SeqFan [mailto:seqfan-bounces at list.seqfan.eu] On Behalf Of Neil
> Sloane
> Sent: Friday, July 01, 2016 9:18 AM
> To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
> Subject: [seqfan] Re: A269526, an infinite Sudoku-type array
>
> I agree that argument proves that the columns are permutations.
>
> The proof isn't quite so clear for the rows. Take row 1. Suppose j is
> missing. Then every antidiagonal must contain a j (before it reaches the
> first row). But the antidiagonals are getting longer and longer.
>
> What we have to is show (roughly) that if we take a triangle formed by the
> first K antidiagonals, containing about K(K+1)/2 grid points, then we
> cannot place K nonattacking queens on this board (thinking of the positions
> of the j's as queens)
>
> Now we can place K nonattacking queens on a square k X K board (see
> A000170). But we surely cannot do it on a triangular board.  Proof?
>
> Our problem is not exactly that, since we stop the antidiagonals just
> before they reach the top row.
>
> But still, it is a nice question: Take a triangular chess board containing
> K*(K+1)/2 cells.
> What is the max number of nonattacking queens? This must be a known
> sequence?
> Maybe it begins 1,1,2,2,3?  Is there a proof that it is <= (K+1)/2 ?
>
> Best regards
> Neil
>
> Neil J. A. Sloane, President, OEIS Foundation.
> 11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
> Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
> Phone: 732 828 6098; home page: http://NeilSloane.com
> Email: njasloane at gmail.com
>
>
> On Fri, Jul 1, 2016 at 7:34 AM, Bob Selcoe <rselcoe at entouchonline.net>
> wrote:
>
> > Hi,
> >
> > Unless I'm missing something, I think there's a straightforward proof
> > that the columns, rows and diagonals are permutations.
> >
> > Let the array T(n,k) in A269526 start T(0,0).
> >
> > Let j be the smallest number not yet appearing in Column K, and let F
> > be the first cell in K where j may appear.  j only must avoid elements
> > from prior (i.e, to the left of K) columns.  Since no element can
> > repeat in any columns, the maximum number of elements that j must
> > avoid is 3k (i.e, the elements in the row and two diagonals to the
> > left of where j is being evaluated).  Therefore j must appear no later
> > than 3k+1 places after F, and columns are permutations.
> >
> > Same logic applies to the rows and diagonals, though the maximum
> > number of places after F is different: 2n+k+1 for rows and n+2k+1 for
> > diagonals.  The constraints probably can be tightened, but it's not
> necessary for a proof.
> >
> > If this proof is acceptable I would like to add it as a comment in
> A269526.
> >
> > Cheers,
> > Bob S.
> >
> > --------------------------------------------------
> > From: "Neil Sloane" <njasloane at gmail.com>
> > Sent: Wednesday, June 29, 2016 1:24 PM
> > To: "Sequence Fanatics Discussion list" <seqfan at list.seqfan.eu>
> > Subject: [seqfan] A269526, an infinite Sudoku-type array
> >
> > Dear Seq Fans,  The following is a pretty interesting recent sequence:
> >>
> >> Array read by anti-diagonals upwards in which each term is the least
> >> positive value satisfying the condition that no row, column, or
> >> diagonal contains a repeated term.
> >>
> >> The sequence is A269526.  I just added the first three rows and the
> >> main diagonal as A274315 ff. (They all need b-files.)
> >>
> >> The array begins:
> >>
> >> 1, 3, 2, 6, 4, 5, 10, 11, 13, 8, 14, 18, 7, 20, 19, ...
> >> 2, 4, 5, 1, 8, 3, 6, 12, 14, 16, 7, 15, 17, 9, 22, ...
> >> 3, 1, 6, 2, 9, 7, 5, 4, 15, 17, 12, 19, 18, 21, 8, ...
> >> 4, 2, 3, 5, 1, 8, 9, 7, 16, 6, 18, 17, 11, 10, 23, ...
> >> 5, 7, 1, 4, 2, 6, 3, 15, 9, 10, 13, 8, 20, 14, 12, ...
> >> ...
> >>
> >> It seems very likely that every row, columns and diagonal (meaning
> >> diagonals parallel to the main diagonal) is a perm of the natural
> >> numbers, but I didn't try to find a proof.
> >>
> >> The first col is just 1,2,3,4,... but the next few columns could also
> >> be added as new? entries.
> >>
> >> There are a lot of other related sequences, for example, in row n,
> >> where does 1 appear?
> >>
> >> It is unusual to see such a nice array which is unrelated to any
> >> other sequence in the OEIS!  (But I didn't try Superseeker).
> >>
> >> This looks like a lovely problem crying out to be analyzed.
> >>
> >> Best regards
> >> Neil
> >>
> >> Neil J. A. Sloane, President, OEIS Foundation.
> >> 11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
> >> Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway,
> NJ.
> >> Phone: 732 828 6098; home page: http://NeilSloane.com
> >> Email: njasloane at gmail.com
> >>
> >> --
> >> Seqfan Mailing list - http://list.seqfan.eu/
> >>
> >>
> > --
> > Seqfan Mailing list - http://list.seqfan.eu/
> >
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>