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,7

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.

Links

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

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)).

Example

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;
  ...

Mathematica

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

Prog

(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))))

Crossrefs

A249809 is a more compact version.

A004526 gives the left edge, A001477 the row sums.

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

Sequence in context: A125676 A291955 A291904 * A258453 A025874 A256012

Adjacent sequences: A249805 A249806 A249807 * A249809 A249810 A249811

Keyword

nonn,tabl

Author

Antti Karttunen, Nov 06 2014

Status

approved