nt.number theory - Asymptotic density of k-almost primes

Saturday, 21 April 2012

nt.number theory - Asymptotic density of k-almost primes

As not necessarily proven results were asked for, I have found the following quite accurate:

$N_k(x):= mid{nleq x : Omega(n)=k}mid sim Rebigg(frac{2^{1-k}alpha e^{1+e}xlog(1+e+log(2^{1-k}alpha x))^{beta}}{beta!(1+e+log(2^{1+e}alpha x)}bigg)$
for

$1 leq kleq lfloor log_2 (x) rfloor$ , where

$log_2$ is

$log$ base

$2$ ,

$gamma$ is Euler's constant,

$beta=1+e+ log alpha +(1+e+ log alpha) ^{1/pi}$ , and

$alpha=frac{1}{2} rm{erfc}bigg(-frac{k-(2e^{gamma}+frac{1}{4})}{(2e^{gamma}+frac{1}{4})sqrt{2} }bigg)-2rm{T}bigg(bigg(frac{k}{(2e^{gamma}+frac{1}{4})}-1bigg),e^{gamma}-frac{1}{4}bigg)\$
where

$rm{erfc}$ is the complementary error function and

$rm{T}$ is the Owen T-function.

In integral form,

$alpha= frac{1}{pi}int_{(-3+8e^gamma)/(sqrt{2}(1+8e^gamma))}^infty e^{-t^2}rm{d} t +int_0^{1/4 - e^gamma}frac{e^{-(3 - 8e^gamma)^2(1+t^2)/(2(1+8e^gamma)^2)}}{1+t^2}rm{d} t.$

As $krightarrow infty$ , $alpharightarrow 1$ , so

$lim_{k rightarrow infty}N_{k}(x cdot 2^{k-1})simfrac { {e^{e+1}} xloglog( {e^{e+1}} x)^{beta}}{log( {e^{e+1}} x)beta!},$
where

$beta=log(e^{e+1})+log(e^{e+1})^{1/pi}.$

For $kleqslant 3$ , improvements to the above can certainly be made, but as $krightarrow infty$ (or more correctly, as $krightarrow lfloor log_2 (x) rfloor$ ), the formulae above, as far as have been tested, seem to be fairly accurate.

For convenience, I include the following Mathematica code:

cdf[k_, x_] :=
Re[N[
(2^-k E^(1 + E) x Log[1 + E + Log[2^-k x (Erfc[(1 + 8 E^EulerGamma - 4 k)/(Sqrt[2]
(1 + 8 E^EulerGamma))] + 4 OwenT[(1 + 8 E^EulerGamma - 4 k)/(1 + 8 E^EulerGamma),
1/4 - E^EulerGamma])]]^(1 + E + Log[1/2 (Erfc[(1 + 8 E^EulerGamma - 4 k)/(Sqrt[2]
(1 + 8 E^EulerGamma))] +4 OwenT[(1 + 8 E^EulerGamma - 4 k)/(1 + 8 E^EulerGamma),
1/4 - E^EulerGamma])] + (1 + E + Log[1/2 (Erfc[(1 + 8 E^EulerGamma - 4 k)/(Sqrt[2]
(1 + 8 E^EulerGamma))] + 4 OwenT[(1 + 8 E^EulerGamma - 4 k)/(1 + 8 E^EulerGamma),
1/4 - E^EulerGamma])])^(1/[Pi])) (Erfc[(1 + 8 E^EulerGamma - 4 k)/(Sqrt[2]
(1 + 8 E^EulerGamma))] + 4 OwenT[(1 + 8 E^EulerGamma - 4 k)/(1 + 8 E^EulerGamma),
1/4 - E^EulerGamma]))/((1 + E + Log[1/2 (Erfc[(1 + 8 E^EulerGamma - 4 k)/(Sqrt[2]
(1 + 8 E^EulerGamma))] + 4 OwenT[(1 + 8 E^EulerGamma - 4 k)/(1 + 8 E^EulerGamma),
1/4 - E^EulerGamma])] + (1 + E + Log[1/2 (Erfc[(1 + 8 E^EulerGamma - 4 k)/(Sqrt[2]
(1 + 8 E^EulerGamma))] + 4 OwenT[(1 + 8 E^EulerGamma - 4 k)/(1 + 8 E^EulerGamma),
1/4 - E^EulerGamma])])^(1/[Pi]))!
(1 + E + Log[2^-k x (Erfc[(1 + 8 E^EulerGamma - 4 k)/(Sqrt[2] (1 + 8 E^EulerGamma))] +
4 OwenT[(1 + 8 E^EulerGamma - 4 k)/(1 + 8 E^EulerGamma), 1/4 - E^EulerGamma])]))]];

landau[k_, x_] := N[(x Log[Log[x]]^(-1 + k))/((-1 + k)! Log[x])];

actual[k_, x_] := N[Sum[1, ##] & @@ Transpose[{#, Prepend[Most[#], 1], PrimePi@
Prepend[ Prime[First[#]]^(1 - k) Rest@FoldList[Times, x, Prime@First[#]/Prime@Most[#]],
x^(1/k)]}] &@Table[Unique[], {k}]];

I warmly welcome any criticism or comments on the above, and apologise in advance if I have made any serious errors.

Note: Table code included as requested:

a = 7;
x = 10^a;
kk = 20;
TableForm[Transpose[{Table[x, {x, 1, kk}], Table[Round[landau[k, x]], {k, 1, kk}], 
Table[Round[cdf[k, x]], {k, 1, kk}], Table[actual[k, x], {k, 1, kk}]}], 
TableHeadings -> {None, {"k  ", "Landau", "CDF   ", "Actual"}}, 
TableSpacing -> {2, 3, 0}]

AnswerDesk

Saturday, 21 April 2012