login
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.
9

%I #36 Mar 08 2022 11:06:16

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

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

%U 12,1,18,12,1,18,13,1,18,14,1,18,15,1,18,16,1,19,16,1,19,17,1

%N 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.

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

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

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

%H Alois P. Heinz, <a href="/A346617/b346617.txt">Rows n = 1..10000, flattened</a>

%H N. J. A. Sloane, <a href="/A346617/a346617.txt">The first 100 rows.</a>

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

%F From _Alois P. Heinz_, Aug 19 2021: (Start)

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

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

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

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

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

%e Rows 1 through 12 are:

%e 1 [0]

%e 2 [1]

%e 3 [2]

%e 4 [3]

%e 5 [4]

%e 6 [4, 1]

%e 7 [5, 1]

%e 8 [6, 1]

%e 9 [7, 1]

%e 10 [7, 2]

%e 11 [8, 2]

%e 12 [8, 3]

%e 13 [9, 3]

%p omega := proc(n) nops(numtheory[factorset](n)) end proc: # # A001221

%p A:=Array(1..20,0);

%p ans:=[[0]];

%p mx:=0;

%p for n from 2 to 100 do

%p k:=omega(n);

%p if k>mx then mx:=k; fi;

%p A[k]:=A[k]+1;

%p ans:=[op(ans),[seq(A[i],i=1..mx)]];

%p od:

%p ans;

%p # second Maple program:

%p b:= proc(n) option remember; `if`(n=0, 0,

%p b(n-1)+x^nops(ifactors(n)[2]))

%p end:

%p T:= n-> (p-> seq(coeff(p, x, i), i=1..max(1, degree(p))))(b(n)):

%p seq(T(n), n=1..40); # _Alois P. Heinz_, Aug 19 2021

%t T[n_] := If[n == 1, {0},

%t Range[n] // PrimeNu // Tally // Rest // #[[All, 2]]&];

%t Array[T, 40] // Flatten (* _Jean-François Alcover_, Mar 08 2022 *)

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

%Y Row lengths give A111972 (for n>1).

%K nonn,tabf

%O 1,3

%A _N. J. A. Sloane_, Aug 19 2021