A293578 Triangular array read by rows. One form of sieve of Eratosthenes (see comments for construction).

1, 2, 0, 2, 3, 0, 0, 0, 3, 4, 0, 0, 3, 0, 0, 4, 5, 0, 0, 0, 0, 0, 0, 0, 5, 6, 0, 0, 0, 4, 0, 4, 0, 0, 0, 6, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 8, 0, 0, 0, 0, 5, 0, 0, 0, 5, 0, 0, 0, 0, 8, 9, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 9, 10, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 10

Offset: 1

Author

Luc Rousseau, Oct 12 2017

Keywords

• nonn
• tabf

Comments

Construction: row n >= 1 contains 2n-1 values indexed from t=-(n-1) to t=+(n-1). Initialize all values to 0. For all positive integers n and all nonnegative integers u, set the value at coordinates (n, -(n-1)) + u*(n,1) to (n + u).

Each nonzero value in row n corresponds to a way of writing n as a product of two positive integers (see formulas). Each row starts with a nonzero value and ends with a nonzero value. A number n is a prime iff row n contains exactly two nonzero values.

Examples

			Array begins (zeros replaced by dots):
                  1
                2 . 2
              3 . . . 3
            4 . . 3 . . 4
          5 . . . . . . . 5
        6 . . . 4 . 4 . . . 6
      7 . . . . . . . . . . . 7
    8 . . . . 5 . . . 5 . . . . 8
  9 . . . . . . . 5 . . . . . . . 9
		

Crossrefs

Cf. A288969.

Programs

Mathematica

F[n_, t_] :=
  Module[{x}, x = Floor[(-t + Sqrt[t^2 + 4 n])/2]; n - x (t + x)];
T[n_, t_] := F[n - 1, t] - F[n, t] + 1;
ARow[n_] := Table[T[n, t], {t, -(n - 1), +(n - 1)}];
Table[ARow[n], {n, 1, 10}] // Flatten

Formula

If z is a nonzero value at coordinates (n,t) then

n = k*(k+t) where k is a positive integer solution of k^2 + tk - n = 0;

Moreover:

z = n/k + k - 1;

n = ((z+1)^2 - t^2)/4.