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

Author

N. J. A. Sloane, Aug 19 2021

Keywords

• nonn
• tabf

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.

Examples

			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]
		

References

• G. H. Hardy, Ramanujan: twelve lectures on subjects suggested by his life and work, Cambridge, University Press, 1940, pp. 52-56.
• 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.

Crossrefs

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

Row lengths give A111972 (for n>1).

Programs

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

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)