cp's OEIS Frontend

Theorem: This is a permutation of the positive integers. For proof, see link in A274650. - N. J. A. Sloane, Jun 07 2017

Theorem: This is a permutation of the nonnegative integers. For proof see link in A274650. - N. J. A. Sloane, Jun 07 2017

It appears that this sequence has infinitely many negative terms, infinitely many zeros and infinitely many positive terms.

An infinite Sudoku-type array.

In the definition, "diagonal" means a diagonal line of slope -1, and "antidiagonal" means a diagonal line of slope +1.

Theorem C (Bob Selcoe, Jul 01 2016): Every column is a permutation of the natural numbers.

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

Theorem R (Rob Pratt, Bob Selcoe, N. J. A. Sloane, Jul 02 2016): Every row is a permutation of the natural numbers.

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.

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.

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

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

For an interpretation of this array in terms of Sprague-Grundy values, see A274528.

From Don Reble, Jun 30 2016: (Start)

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.

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)

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

It appears that the numbers generally appear for the first time in or near the first few rows. - Omar E. Pol, Jul 03 2016

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

This sequence has essentially the same properties as the main sequence A269526, but now involves the nonnegative integers.

This version is important because of the following comment from Allan C. Wechsler, originally contributed to A269526. - N. J. A. Sloane, Jun 30 2016

Sprague-Grundy (Nim) values for a combinatorial game played with two piles of counters. Legal moves consist of removing any positive number of counters from either pile, or removing the same number from both piles, or moving any positive number of counters from the right pile to the left pile. If the Nim-values (as in Sprague-Grundy theory) are written in an array indexed by the number of counters in the two piles, we obtain this array. - Allan C. Wechsler, Jun 29 2016 [corrected by N. J. A. Sloane, Sep 25 2016]

The same sequence arises if we construct a triangle, by reading from left to right in each row, always choosing the smallest nonnegative number which does not produce a duplicate number in any row or diagonal. - N. J. A. Sloane, Jul 02 2016

It appears that the numbers generally appear for the first time in or near the first few rows. - Omar E. Pol, Jul 03 2016

Also spiral constructed on the infinite hexagonal grid in which each term is the least nonnegative integer such that no diagonal of successive adjacent cells contains a repeated term. Every number is located in the center of a hexagonal cell. Every cell is also the center of three diagonals of successive adjacent cells.

Presumably every line of cells with slope a multiple of 60 degrees (not necessarily passing through the central cell) is a permutation of the nonnegative numbers. See A296343-A296348 for the spokes through the central cell. - N. J. A. Sloane, Dec 12 2017

Analog of A269526, but note that this is a right triangle.

The same rule applied to an equilateral triangle gives A269526.

We construct the triangle by reading from left to right in each row, starting with T(1,1) = 1.

Presumably every diagonal and every column is also a permutation of the positive integers, but the proof does not seem so straightforward. Of course, neither the rows nor the antidiagonals are permutations of the positive integers, since they are finite in length.

Omar E. Pol's conjecture that every column and every diagonal of the triangle is a permutation of the positive integers is true: see the link in A274650 (duplicated below). - N. J. A. Sloane, Jun 07 2017

It appears that the numbers generally appear for the first time in or near the right border of the triangle.

Theorem 1: the middle diagonal gives A000012 (the all 1's sequence).

Theorem 2: all 1's are in the middle diagonal.

For the proofs of the theorems 1 and 2 see the proofs of the theorems 1 and 2 of A274650 since both sequences are essentially the same.

From Bob Selcoe, Feb 15 2017: (Start)

The columns and diagonal are permutations of the natural numbers. The proofs are essentially the same as the proofs given for the columns and rows (respectively) in A269526.

All coefficients j <= 4 eventually populate in a repeating pattern toward the "middle diagonal" (i.e., relatively near the 1's); this is because we can build the triangle by j in ascending order; that is, we can start by placing all the 1's in the proper cells, then add the 2's, 3's, 4's, 5's, etc. So for i >= 0: since the 1's appear at T(1+2i, 1+i), the 2's appear at T(2+8i, 1+4i), T(3+8i, 3+4i), T(5+8i, 2+4i) and T(6+8i, 4+4i). Accordingly, after the first five 3's appear (at T(2,2), T(4,1), T(5,4), T(7,3) and T(8,6)), the remaining 3's appear at T(11+8i, 5+4i), T(12+8i, 7+4i), T(16+8i, 8+4i) and T(17+8i, 10+4i). Similarly for 4's, after the first 21 appearances, 4's appear at T(44+8i, 21+4i), T(45+8i, 24+4i), T(47+8i, 23+4i) and T(48+8i, 26+4i). So starting at T(41,21), this 16-coefficient pattern repeats at T(41+8i, 21+4i):

n/k 21 22 23 24 25 26

41 1 3

42 2

43 3 1 2

44 4 3

45 2 1 4

46 2

47 4 1

48 3 4

where the next 1 appears at T(49,25), and the pattern repeats at that point from the top left (so T(49,26) = 3, T(50,25) = 2, etc.).

Conjecture: as n gets sufficiently large, all coefficients j>4 will appear in a repeating pattern, populating all rows and diagonals around smaller j's near the "middle diagonal" (while I can offer no formal proof, it appears very likely that this is the case). (End)

From Hartmut F. W. Hoft, Jun 12 2017: (Start)

T(2k+1,k+1) = 1, for all k>=0, and T(n,{n/2,(n+3)/2,(n-1)/2,(n+2)/2}) = 2, for all n>=1 with mod(n,8) = {2,3,5,6} respectively, and no 1's or 2's occur in other positions.

Proof by (recursive) picture:

Positions in the triangle that are empty and those containing the dots of the guiding diagonals contain numbers larger than two.

n\k 1 2 3 4 5 6 7 8 10 12 14 16 18 20 22 24

1 |1

2 |2 .

3 | 1 2

4 | .

5 | 2 1 .

6 | 2 .

7 | 1 .

8 |____________.

9 | |1 .

10 | |2 . .

11 | | 1 2 .

12 | | . .

13 | | 2 1 . .

14 | | 2 . .

15 | | 1 . .

16 |_____|______________._____.

17 | | |1 . .

18 | | |2 . . .

19 | | | 1 2 . .

20 | | | . . .

21 | | | 2 1 . . .

22 | | | 2 . . .

23 | | | 1 . . .

24 |_____|_______|____._______._____._______.

1 2 3 4 5 6 7 8 12 16 20 24

Consider the center of the triangle. In each octave of rows the columns in the first central quatrain contain a 1 and a 2, and the diagonals in the second central quatrain contain a 1 and a 2. Therefore, no 1's or 2's can occur in the respective downward quatrains of leading columns and trailing diagonals.

The sequence of rows containing 2's is A047447 (n mod 8 = {2,3,5,6}), those containing only 2's is A016825 (n mod 8 = {2,6}), those containing both 1's and 2's is A047621 (n mod 8 = {3,5}), those containing only 1's is A047522 (n mod 8 = {1,7}), and those containing neither 1's nor 2's is A008586 (n mod 8 = {0,4}).

(End)

Conjecture: every column or diagonal of slope +-1 is a permutation of the nonnegative numbers.

Note that the n-th row of this triangle is constructed from right to left, starting at the column n and ending at the column 0.

Theorem 1: the middle diagonal gives A000004, the all-zeros sequence.

Theorem 2: all zeros are in the middle diagonal.

For the proofs of the theorems 1 and 2 see the proofs of the theorems 1 and 2 of A274650, because this is essentially the same problem.

Conjecture 3: every column is a permutation of the nonnegative integers.

Conjecture 4: every diagonal is a permutation of the right border which gives the nonnegative integers.