A346617 Irregular triangle T(n,m) read by rows (n >= 1, 1 <= m <= Max(A001221([1..n]))): T(n,m) = number of integers in [1,n] with m distinct prime factors.

0, 1, 2, 3, 4, 4, 1, 5, 1, 6, 1, 7, 1, 7, 2, 8, 2, 8, 3, 9, 3, 9, 4, 9, 5, 10, 5, 11, 5, 11, 6, 12, 6, 12, 7, 12, 8, 12, 9, 13, 9, 13, 10, 14, 10, 14, 11, 15, 11, 15, 12, 16, 12, 16, 12, 1, 17, 12, 1, 18, 12, 1, 18, 13, 1, 18, 14, 1, 18, 15, 1, 18, 16, 1, 19, 16, 1, 19, 17, 1

Offset

1,3

Comments

Column k >= 1 of the triangle gives the number of numbers i in the range 1 <= i <= n with omega(i) = A001221(i) = k.

A285577 is a similar triangle which has an extra column on the left for k = 0.

References

Edmund Landau, Handbuch der Lehre von der Verteilung der Primzahlen, Chelsea Publishing, NY 1953, Vol. 1, p. 211, Eq. (5).

Links

Alois P. Heinz, Rows n = 1..10000, flattened

N. J. A. Sloane, The first 100 rows.

Formula

For fixed k, T(n,k) ~ (1/(k-1)!) * n * (log log n)^(k-1) / log n [Landau].

From Alois P. Heinz, Aug 19 2021: (Start)

Sum_{k>=1} k * T(n,k) = A013939(n).

Sum_{k>=1} k^2 * T(n,k) = A069811(n).

Sum_{k>=1} (-1)^(k-1) * T(n,k) = A123066(n).

Sum_{k>=1} (-1)^k * T(n,k) = -1 + A174863(n).

Sum_{k>=1} T(n,k) = n - 1. (End)

Example

Rows 1 through 12 are:
1 [0]
2 [1]
3 [2]
4 [3]
5 [4]
6 [4, 1]
7 [5, 1]
8 [6, 1]
9 [7, 1]
10 [7, 2]
11 [8, 2]
12 [8, 3]
13 [9, 3]

Maple

omega := proc(n) nops(numtheory[factorset](n)) end proc: # # A001221
A:=Array(1..20, 0);
ans:=[[0]];
mx:=0;
for n from 2 to 100 do
k:=omega(n);
if k>mx then mx:=k; fi;
A[k]:=A[k]+1;
ans:=[op(ans), [seq(A[i], i=1..mx)]];
od:
ans;
# second Maple program:
b:= proc(n) option remember; `if`(n=0, 0,
      b(n-1)+x^nops(ifactors(n)[2]))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..max(1, degree(p))))(b(n)):
seq(T(n), n=1..40);  # Alois P. Heinz, Aug 19 2021

Mathematica

T[n_] := If[n == 1, {0},
     Range[n] // PrimeNu // Tally // Rest // #[[All, 2]]&];
Array[T, 40] // Flatten (* Jean-François Alcover, Mar 08 2022 *)

Crossrefs

Cf. A001221, A013939, A069811, A123066, A174863, A285577.

Row lengths give A111972 (for n>1).

Sequence in context: A172160 A171170 A256913 * A160386 A347860 A343835

Adjacent sequences: A346614 A346615 A346616 * A346618 A346619 A346620

Keyword

nonn,tabf

Author

N. J. A. Sloane, Aug 19 2021

Status

approved