A249808 Triangular table read by rows, a lower right triangular region of square array A(n,k) is the number of times prime p_k has occurred as the smallest prime factor of numbers 1..n.

0, 1, 0, 1, 1, 0, 2, 1, 0, 0, 2, 1, 1, 0, 0, 3, 1, 1, 0, 0, 0, 3, 1, 1, 1, 0, 0, 0, 4, 1, 1, 1, 0, 0, 0, 0, 4, 2, 1, 1, 0, 0, 0, 0, 0, 5, 2, 1, 1, 0, 0, 0, 0, 0, 0, 5, 2, 1, 1, 1, 0, 0, 0, 0, 0, 0, 6, 2, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 6, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 7, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 7, 3, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0

Offset: 1

Author

Antti Karttunen, Nov 06 2014

Keywords

• nonn
• tabl

Comments

Table is read by taking n terms from the beginning of row n: A(1,1), A(2,1), A(2,2), A(3,1), A(3,2), A(3,3), ...

See also A249809 for a version with extra zeros removed.

Examples

			The first eleven rows of this triangular table:
  0;
  1, 0;
  1, 1, 0;
  2, 1, 0, 0;
  2, 1, 1, 0, 0;
  3, 1, 1, 0, 0, 0;
  3, 1, 1, 1, 0, 0, 0;
  4, 1, 1, 1, 0, 0, 0, 0;
  4, 2, 1, 1, 0, 0, 0, 0, 0;
  5, 2, 1, 1, 0, 0, 0, 0, 0, 0;
  5, 2, 1, 1, 1, 0, 0, 0, 0, 0, 0;
  ...
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..10440; the first 144 rows of triangular table

Crossrefs

A249809 is a more compact version.

A004526 gives the left edge, A001477 the row sums.

Cf. A000040, A020639, A055396, A078898, A002024, A002260.

Programs

Mathematica

FoldList[Append[MapAt[# + 1 &, #1, PrimePi@ FactorInteger[#2][[1, 1]]], 0] &, {0}, Range[2, 15]] // Flatten (* Michael De Vlieger, Nov 24 2017 *)

Scheme

(define (A249808 n) (A249808bi (A002024 n) (A002260 n)))
(define (A249808bi row col) (if (= 1 row) 0 (+ (A249808bi (- row 1) col) (if (= (A055396 row) col) 1 0))))

Formula

If row n = 1, A(n,k) = 0, otherwise A(n,k) = A(n-1,k) + [A055396(n) = k], where the subexpression with the Iverson bracket is 1 if the index of the smallest prime dividing n is equal to k, and 0 otherwise. This is a formula for a full square array containing mostly zeros. The terms of this sequence are those collected from the lower right triangle of that square array.

For n > 1, A078898(n) = A(n, A055396(n)).