This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A269526 #167 May 20 2025 03:15:21
%S A269526 1,2,3,3,4,2,4,1,5,6,5,2,6,1,4,6,7,3,2,8,5,7,8,1,5,9,3,10,8,5,9,4,1,7,
%T A269526 6,11,9,6,4,7,2,8,5,12,13,10,11,7,3,5,6,9,4,14,8,11,12,8,9,6,10,3,7,
%U A269526 15,16,14,12,9,13,10,11,14,4,15,16,17,7,18,13,10,14,11,3,4,8,16,9,6,12,15,7
%N A269526 Square array T(n,k) (n>=1, k>=1) read by antidiagonals upwards in which each term is the least positive integer satisfying the condition that no row, column, diagonal, or antidiagonal contains a repeated term.
%C A269526 An infinite Sudoku-type array.
%C A269526 In the definition, "diagonal" means a diagonal line of slope -1, and "antidiagonal" means a diagonal line of slope +1.
%C A269526 Theorem C (_Bob Selcoe_, Jul 01 2016): Every column is a permutation of the natural numbers.
%C A269526 Proof: Fix k, and suppose j is the smallest number missing from that column. For this to happen, every entry T(n,k) for sufficiently large n in that column must see a j in the NW diagonal through that cell or in the row to the W of that cell. But there are at most k-1 copies of j in the columns to the left of the k-th column, and if n is very large the entry T(n,k) will be unaffected by those j's, and so T(n,k) would then be set to j, a contradiction. QED
%C A269526 Theorem R (_Rob Pratt_, _Bob Selcoe_, _N. J. A. Sloane_, Jul 02 2016): Every row is a permutation of the natural numbers.
%C A269526 Proof: Fix n, and suppose j is the smallest number missing from that row. For this to happen, every entry T(n,k) for sufficiently large k in that row must see a j in the column to the N, or in the NW diagonal through that cell or in the SW diagonal through that cell.
%C A269526 Rows 1 through n-1 contain at most n-1 copies of j, and their influence on the entries in the n-th row only extend out to the entry T(n,k_0), say. We take k to be much larger than k_0 and consider the entry T(n,k). We will show that for large enough k it can (and therefore must) be equal to j, which is a contradiction.
%C A269526 Consider the triangle bounded by row n, column 1, and the SW antidiagonal through cell (n,k). Replace every copy of j in this triangle by a queen and think of these cells as a triangular chessboard. These are non-attacking queens, by definition of the sequence, and by the result in A274616 there can be at most 2*k/3 + 1 such queens. However, there are k-k_0 cells in row n that have to be attacked, and for large k this is impossible since k-k_0 > 2*k/3+1. If a cell (n,k) is not attacked by a queen, then T(n,k) can take the value j. QED
%C A269526 Presumably every diagonal is also a permutation of the natural numbers, but the proof does not seem so straightforward. Of course the antidiagonals are not permutations of the natural numbers, since they are finite in length. - _N. J. A. Sloane_, Jul 02 2016
%C A269526 For an interpretation of this array in terms of Sprague-Grundy values, see A274528.
%C A269526 From _Don Reble_, Jun 30 2016: (Start)
%C A269526 Let b(n) be the position in column n where 1 appears, i.e., such that T(b(n),n) = 1. Then b(n) is A065188, which is _Antti Karttunen_'s "Greedy Queens" permutation.
%C A269526 Let b'(n) be the position in row n where 1 appears, i.e., such that T(n,b'(n)) = 1. Then b'(n) is A065189, the inverse "Greedy Queens" permutation. (End)
%C A269526 The same sequence arises if we construct a triangle, by reading from left to right in each row, always choosing the smallest positive number which does not produce a duplicate number in any row or diagonal. - _N. J. A. Sloane_, Jul 02 2016
%C A269526 It appears that the numbers generally appear for the first time in or near the first few rows. - _Omar E. Pol_, Jul 03 2016
%C A269526 The last comment in the FORMULA section seems wrong: It seems that columns 4, 5, 6, 7, 8, 9, ...(?) all have first differences which become 16-periodic from, respectively, term 8, 17, 52, 91, 92, 131, ... on, rather than having period 4^(k-1) from term k on. - _M. F. Hasler_, Sep 26 2022
%H A269526 Peter Kagey, <a href="/A269526/b269526.txt">Table of n, a(n) for n = 1..10000</a>
%H A269526 F. Michel Dekking, Jeffrey Shallit, and N. J. A. Sloane, <a href="https://doi.org/10.37236/8905">Queens in exile: non-attacking queens on infinite chess boards</a>, Electronic J. Combin., 27:1 (2020), #P1.52.
%H A269526 Peter Kagey, <a href="/A269526/a269526.gif">Animated example illustrating the first fifteen terms</a>.
%F A269526 Theorem 1: T(n,1) = n.
%F A269526 Proof by induction. T(1,1)=1 by definition. When calculating T(n,1), the only constraint is that it be different from all earlier entries in the first column, which are 1,2,3,...,n-1. So T(n,1)=n. QED
%F A269526 Theorem 2 (Based on a message from _Bob Selcoe_, Jun 29 2016): Write n = 4t+i with t >= 0, i=1,2,3, or 4. Then T(n,2) = 4t+3 if i=1, 4t+4 if i=2, 4t+1 if i=3, 4t+2 if i=4. This implies that the second column is the permutation A256008.
%F A269526 Proof: We check that the first 4 entries in column 2 are 2,5,6,3. From then on, to calculate the entry T(n,2), we need only look to the N, NW, W, and SW (we need never look to the East). After we have found the first 4t entries in the column, the column contains all the numbers from 1 to 4t. The four smallest free numbers are 4t+1, 4t+2, 4t+3, 4t+4. Entry T(4t+1,2) cannot be 4t+1 or 4t+2, but it can (and therefore must) be 4t+3. Similarly T(4t+2,2)=4t+4, T(4t+3,2)=4t+1, and T(4t+4,2)=4t+2. The column now contains all the numbers from 1 to 4t+4. Repeating this argument established the theorem. QED
%F A269526 Comments from _Bob Selcoe_, Jun 29 2016: (Start)
%F A269526 From Theorem 2, column 2 (i.e., terms a((j^2+j+4)/2), j>=1) is a permutation. After a(3)=3, the differences of successive terms follow the pattern a(n) = 3 [+1, -3, +1, +5], so a(5)=4, a(8)=1, a(12)=2, a(17)=7, a(23)=8, a(30)=5...
%F A269526 Similarly, column 3 (i.e., terms a((j^2+j+6)/2), j>=2) appears to be a permutation, but with the pattern after a(6)=2 and a(9)=5 being 5 [+1, -3, -2, +8, -5, +3, +1, +5, +1, -3, +1, -2, +8, -3, +1, +5]. (See A274614 and A274615.)
%F A269526 I conjecture that other similar cyclical difference patterns should hold for any column k (i.e., terms a((j^2+j+2*k)/2), j>=k-1), so that each column is a permutation.
%F A269526 Also, the differences in column 1 are a 1-cycle ([+1]), in column 2 a 4-cycle after the first term, and in column 3 a 16-cycle after the second term. Perhaps the cycle lengths are 4^(k-1) starting after j=k-1. (End) WARNING: These comments may be wrong - see COMMENTS section. - _N. J. A. Sloane_, Sep 26 2022
%e A269526 The array is constructed along its antidiagonals, in the following way:
%e A269526 a(1) a(3) a(6) a(10)
%e A269526 a(2) a(5) a(9)
%e A269526 a(4) a(8)
%e A269526 a(7)
%e A269526 See the link from Peter Kagey for an animated example.
%e A269526 The beginning of the square array is:
%e A269526 1, 3, 2, 6, 4, 5, 10, 11, 13, 8, 14, 18, 7, 20, 19, 9, 12, ...
%e A269526 2, 4, 5, 1, 8, 3, 6, 12, 14, 16, 7, 15, 17, 9, 22, 21, 11, ...
%e A269526 3, 1, 6, 2, 9, 7, 5, 4, 15, 17, 12, 19, 18, 21, 8, 10, 23, ...
%e A269526 4, 2, 3, 5, 1, 8, 9, 7, 16, 6, 18, 17, 11, 10, 23, 22, 14, ...
%e A269526 5, 7, 1, 4, 2, 6, 3, 15, 9, 10, 13, 8, 20, 14, 12, 11, 17, ...
%e A269526 6, 8, 9, 7, 5, 10, 4, 16, 2, 1, 3, 11, 22, 15, 24, 13, 27, ...
%e A269526 7, 5, 4, 3, 6, 14, 8, 9, 11, 18, 2, 21, 1, 16, 10, 12, 20, ...
%e A269526 8, 6, 7, 9, 11, 4, 13, 3, 12, 15, 1, 10, 2, 5, 26, 14, 18, ...
%e A269526 9, 11, 8, 10, 3, 1, 14, 6, 7, 13, 4, 12, 24, 18, 2, 5, 19, ...
%e A269526 10, 12, 13, 11, 16, 2, 17, 5, 20, 9, 8, 14, 4, 6, 1, 7, 3, ...
%e A269526 11, 9, 14, 12, 10, 15, 1, 8, 21, 7, 16, 20, 5, 3, 18, 17, 32, ...
%e A269526 12, 10, 11, 8, 7, 9, 2, 13, 5, 23, 25, 26, 14, 17, 16, 15, 33, ...
%e A269526 ...
%e A269526 - _N. J. A. Sloane_, Jun 29 2016
%p A269526 # The following Maple program was provided at my request by _Alois P. Heinz_, who said that he had not posted it himself because it stores the data in an inefficient way. - _N. J. A. Sloane_, Jul 01 2016
%p A269526 A:= proc(n, k) option remember; local m, s;
%p A269526 if n=1 and k=1 then 1
%p A269526 else s:= {seq(A(i,k), i=1..n-1),
%p A269526 seq(A(n,j), j=1..k-1),
%p A269526 seq(A(n-t,k-t), t=1..min(n,k)-1),
%p A269526 seq(A(n+j,k-j), j=1..k-1)};
%p A269526 for m while m in s do od; m
%p A269526 fi
%p A269526 end:
%p A269526 [seq(seq(A(1+d-k, k), k=1..d), d=1..15)];
%t A269526 A[n_, k_] := A[n, k] = If[n == 1 && k == 1, 1, s = {Table[A[i, k], {i, 1, n-1}], Table[A[n, j], {j, 1, k-1}], Table[A[n-t, k-t], {t, 1, Min[n, k] - 1}], Table[A[n+j, k-j], {j, 1, k-1}]} // Flatten; For[m = 1, True, m++, If[FreeQ[s, m], Return[m]]]];
%t A269526 Table[Table[A[1+d-k, k], {k, 1, d}], {d, 1, 15}] // Flatten (* _Jean-François Alcover_, Jul 21 2016, translated from Maple *)
%o A269526 (Haskell)
%o A269526 import Data.List ((\\))
%o A269526 a269526 n = head $ [1..] \\ map a269526 (a274080_row n)
%o A269526 -- _Peter Kagey_, Jun 10 2016
%o A269526 (PARI) {M269526=Map(); A269526=T(r,c)=c>1 && !mapisdefined(M269526, [r,c], &r) && mapput(M269526, [r,c], r=sum(k=1, #c=Set(concat([[T(r+k,c+k)|k<-[1-min(r, c)..-1]], [T(r,k)|k<-[1..c-1]], [T(k,c)|k<-[1..r-1]], [T(r+c-k,k)|k<-[1..c-1]]])), c[k]==k)+1); r} \\ _M. F. Hasler_, Sep 26 2022
%Y A269526 First 4 rows are A274315, A274316, A274317, A274791.
%Y A269526 Main diagonal is A274318.
%Y A269526 Column 1 is A000027, column 2 is A256008(n) = A004443(n-1)+1 = 1 + (nimsum of n-1 and 2), column 3 is A274614 (or equally, A274615 + 1), and column 4 is A274617 (or equally, A274619 + 1).
%Y A269526 Antidiagonal sums give A274530. Other properties of antidiagonals: A274529, A275883.
%Y A269526 Cf. A274080 (used in Haskell program), A274616.
%Y A269526 A065188 and A065189 say where the 1's appear in successive columns and rows.
%Y A269526 If all terms are reduced by 1 and the offset is changed to 0 we get A274528.
%Y A269526 A274650 and A274651 are triangles in the shape of a right triangle and with a similar definition.
%Y A269526 See A274630 for the case where both queens' and knights' moves must avoid duplicates.
%K A269526 nonn,tabl,easy,look,nice
%O A269526 1,2
%A A269526 _Alec Jones_, Apr 07 2016
%E A269526 Definition clarified by _Omar E. Pol_, Jun 29 2016