Interesting Array of Integers with Strange Pattern

Question

I was experimenting and I found this pattern:

Start with an (infinite) array with top row with all ones, and leftmost two columns also all ones.

$$ \begin{matrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdots \\ 1 & 1 & ? & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & ? & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & ? & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & ? & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & ? & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & ? & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & ? & ? & ? & ? & ? & ? & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{matrix} $$

Then, to find the columns, starting from the top row, add numbers on the diagonal to the left:

$$ \begin{matrix} 1 & \color{blue}{1} & \color{blue}{1} & 1 & 1 & 1 & 1 & 1 & \cdots \\ \color{blue}{1} & 1 & \color{blue}{1+1} & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & ? & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & ? & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & ? & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & ? & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & ? & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & ? & ? & ? & ? & ? & ? & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{matrix} $$ After this step, replace the numbers below the last one like this: $$ \begin{matrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdots \\ 1 & 1 & 2 & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & ? & ? & ? & ? & ? & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{matrix} $$

Repeat:

$$ \begin{matrix} 1 & 1 & \color{red}{1} & \color{red}{1} & 1 & 1 & 1 & 1 & \cdots \\ 1 & \color{red}{1} & 2 & \color{red}{1+1} & ? & ? & ? & ? & \cdots \\ \color{red}{1} & 1 & 2 & \color{red}{1+1+1} & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & ? & ? & ? & ? & ? & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{matrix} $$

Replace:

$$ \begin{matrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdots \\ 1 & 1 & 2 & 2 & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & ? & ? & ? & ? & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{matrix} $$

Repeat:

$$ \begin{matrix} 1 & 1 & 1 & \color{blue}{1} & \color{blue}{1} & 1 & 1 & 1 & \cdots \\ 1 & 1 & \color{blue}{2} & 2 & \color{blue}{1+2} & ? & ? & ? & \cdots \\ 1 & \color{blue}{1} & 2 & 3 & \color{blue}{1+2+1} & ? & ? & ? & \cdots \\ \color{blue}{1} & 1 & 2 & 3 & \color{blue}{1+2+1+1} & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & ? & ? & ? & ? & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{matrix} $$

Replace:

$$ \begin{matrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdots \\ 1 & 1 & 2 & 2 & 3 & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & 4 & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & 5 & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & 5 & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & 5 & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & 5 & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & 5 & ? & ? & ? & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{matrix} $$

I guess you get the idea now. So after filling in the array, I got:

$$ \begin{matrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdots \\ 1 & 1 & 2 & 2 & 3 & 3 & 4 & ? & \cdots \\ 1 & 1 & \color{red}{2} & 3 & 4 & 5 & 7 & ? & \cdots \\ 1 & 1 & 2 & \color{red}{3} & 5 & 6 & 9 & ? & \cdots \\ 1 & 1 & 2 & 3 & \color{red}{5} & 7 & 10 & ? & \cdots \\ 1 & 1 & 2 & 3 & 5 & \color{red}{7} & 11 & ? & \cdots \\ 1 & 1 & 2 & 3 & 5 & 7 & \color{red}{11} & ? & \cdots \\ 1 & 1 & 2 & 3 & 5 & 7 & 11 & \color{red}{?} & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{matrix} $$

So it looks like the numbers on the diagonal might be the prime numbers. But computing the next column destroys this hope:

$$ \begin{matrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdots \\ 1 & 1 & 2 & 2 & 3 & 3 & 4 & 4 & \cdots \\ 1 & 1 & \color{red}{2} & 3 & 4 & 5 & 7 & 8 & \cdots \\ 1 & 1 & 2 & \color{red}{3} & 5 & 6 & 9 & 11 & \cdots \\ 1 & 1 & 2 & 3 & \color{red}{5} & 7 & 10 & 13 & \cdots \\ 1 & 1 & 2 & 3 & 5 & \color{red}{7} & 11 & 14 & \cdots \\ 1 & 1 & 2 & 3 & 5 & 7 & \color{red}{11} & 15 & \cdots \\ 1 & 1 & 2 & 3 & 5 & 7 & 11 & \color{red}{15} & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{matrix} $$

Writing out this sequence:

$$2, 3, 5, 7, 11, 15, \cdots $$

So my question is, what is this sequence, that mirrored the primes but then suddenly diverged?

Answer 1

The entry in the $m$th row and $(n+1)$st column equals the number of partitions of $n$ into parts not exceeding $m$. In particular, the $m$th entry on the diagonal equals the number of partitions of $m$ (as noted by BoizWeir).

If $p(k,j)$ denotes the number of partitions of $k$ into parts not exceeding $j$, then sorting the partitions of $k$ by their largest part $i$ yields $$ p(k,j) = \sum_{i=1}^{\min\{j,k\}} p(k-i,i), $$ which matches the procedure you've used to construct the array (as do the initial conditions).

Answer 2

So after looking at the OEIS page (and the comment pointed out to me by @bburGsamohT), I think I have it figured out!

The comment defines the quantities (I have changed the variable names, though):

$$a_1 = \frac{1}{1-x}$$

$$a_2 = \frac{1}{1-x^2}$$

$$a_3 = \frac{1}{1-x^3}$$

$$a_4 = \frac{1}{1-x^4}$$

etc.

The key is that we can write these as series!

$$a_1 = \frac{1}{1-x} = 1+x+x^2+x^3+x^4+\cdots$$

$$a_2 = \frac{1}{1-x^2} = 1+x^2+x^4+x^6+x^8+\cdots$$

$$a_3 = \frac{1}{1-x^3} = 1+x^3+x^6+x^9+x^{12}+\cdots$$

$$a_4 = \frac{1}{1-x^4} = 1+x^4+x^8+x^{12}+x^{16}+\cdots$$

etc.

Then the coefficient of $x^n$ in the infinite product $a_1a_2a_3a_4\cdots$ is just the number of ways we can write the number $n$ as a sum:

$$n=x_1+2x_2+3x_3+4x_4+\cdots$$

where the $x_i$ are positive integers. (This results from multiplying out the infinite product.)

The array is actually constructed in such a way that the numbers on the diagonals (or rather, as the comment points out, the rows (which stabilize to longer and longer segments of the sequence)) exactly count the number of ways to write $n$ as the sum mentioned above.

But of course the infinite product mentioned earlier is a formula for the generating function of the partition numbers! Thus, equating coefficients, we find that the sequence from the array is the sequence of partition numbers. Q.E.D.

Thanks to all of you for the help!