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

Rob Pratt Rob.Pratt at sas.com
Fri Jul 1 17:23:57 CEST 2016


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/


More information about the SeqFan mailing list