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

Fri Jul 1 21:55:12 CEST 2016

Hi Neil, Rob & Seqfans,

I was in the process of offering a proof for the rows and diagonals; If 
you'd like I can finish it for a diagonal proof, but essentially the same 
logic holds as for columns.

I'm guessing that someone will provide a proof more elegantly than I can 
;-), but I'll give mine if you would like (on or off list).

Cheers,
Bob

--------------------------------------------------
From: "Neil Sloane" <njasloane at gmail.com>
Sent: Friday, July 01, 2016 1:42 PM
To: "Sequence Fanatics Discussion list" <seqfan at list.seqfan.eu>
Subject: [seqfan] Re: A269526, an infinite Sudoku-type array

> 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/
>>
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
> 