# (Not) Surprising Result on Natural Numbers as Sum of $k$-Almost Primes

I started with the following idea:

• Let $P_k$ be the infinte set of all $k$-almost primes.
• The counting function for $k$-almost primes less than $x$, is $\displaystyle \pi_k(x)\sim\frac{x}{\log x}\frac{(\log \log x)^{k-1}}{(k-1)!}$, where the error goes like $\displaystyle O\left(\frac{x(\log \log x)^{k-2}}{\log x} \right)$. See answer to this MO question.
• The union of all $P_k$ is $\mathbb{N}$ (except $1$), so the counting functions sum up to $\displaystyle \sum_k \pi_k (x)=x$.

I wanted to look at the error term and see how large the discrepancy, between the sum of primes counting functions and natural number couting function (haha!) is. But to my surprise I found the following:

With the series expansion of $\displaystyle e^t=\sum_{m=0}^\infty \frac{t^m}{m!}$, where $t=\log \log x$, we get: $$\log x = e^{\log \log x}=\sum_{m=1}^\infty\frac{(\log \log x)^{m-1}}{(m-1)!}.$$ Here I used a Taylor series with derivatives w.r.t. to $\log \log x$. We use $\displaystyle \frac{d^me^{\log \log x}}{d(\log \log x)^m}=1$ . Now summing up all $\pi_k(x)$, we have $$x=\sum_k \pi_k(x) \sim \frac{x}{\log x} \sum_{k=1}^\infty\frac{(\log \log x)^{k-1}}{(k-1)!} =x.$$

Ok, it's correct, but why? Do the error terms all cancel or is this just a artifact of the bad approximation of the counting function $\pi_k(x)$?

-
I have always thought of this computation as a heuristic for why Landau's result makes sense. (Landau first proved the above asymptotic for $\pi_k(x)$) –  Eric Naslund Feb 20 '12 at 12:45
@EricNaslund So you mean, you expected this? But what happens, if you plug in better approxiamtions, like $\pi(x)\sim {\rm li}(x)$? Unfortunately I didn't find any asymptotics, using integral logarithms, for $k$-almost primes, with $k>1$, but I think they are constructable somehow. –  draks ... Feb 20 '12 at 12:50
Just a small note: The asymptotic $$\pi_k(x)\sim \frac{x(\log \log x)^{k-1}}{(k-1)!\log x}$$ is simply not true in general, but rather only for fixed $k$. If $k$ is allowed to vary with $x$, as is the case in the sum $\sum_{k=1}^{\log_2(x)} \pi_k(x)$, then we have a very different result. Specifically given any fixed $C>0$, for $k\leq C\log\log x$ we have $$\pi_k(x)\sim F\left(\frac{k}{\log \log x}\right) \frac{x(\log \log x)^{k-1}}{(k-1)!\log x}$$ where $$F(z)=\frac{1}{\Gamma(z+1)}\prod_p \left(1+\frac{z}{p-1}\right)\left(1-\frac{1}{p}\right)^z.$$ –  Eric Naslund Feb 20 '12 at 12:58
@EricNaslund So I'd better start again, using your expression for $\pi_k(x)$? –  draks ... Feb 20 '12 at 13:14
Well, even with this you can't get the full sum. I just wanted to point this out, and the fact that we don't even have an asymptotic past $C\log\log x$. However, I still think the question you are asking is perfectly fine.Why does the basic asymptotic give exactly what we would expect when summed? I think there is a straightforward reason. –  Eric Naslund Feb 20 '12 at 13:25

Looking through Ramanjuan's Collected Papers in the 32d paper (p. 242 in my ed.) I notice he has the following:

$$(1)\hspace{7mm}\pi_k(x)\sim \frac{x}{\ln x} \frac{(\ln \ln x)^{k-1}}{(k-1)!}$$

$$(2)\hspace{5mm}[x] = \{\pi_1(x) + \pi_2(x)+\pi_3(x)...\}$$

and

$$(3)\hspace{5mm}x = \frac{x}{\ln x}\{1 + \ln\ln x + \frac{(\ln\ln x)^2}{2!}+...\}$$

He mentions that Landau proved (1) and says (2)and (3) are "obvious." He does say there is a "far from exact" correspondence between (2) and (3). Ramanujan does not suggest that (3) is other than asymptotically exact (nor do Eric's comments).

Sasha gives a very nice proof for numbers of the form $2^n$ here. My question was I think essentially the same as this one and motivated by the same question. Does this mean the PNT errors cancel?

I think expanding $e^y$ in a power series with $y = \ln\ln x$ gives (3).

So I think that, yes, the sum of the errors for the PNT must be zero for given x. Also I doubt there is much to be made of it.

(The proof of (1) in Landau is at p. 203 and following--Landau is not indexed.)

-
If I have missed some obvious aspect of the question please let me know--I will happily edit or take down. –  daniel Jul 5 '13 at 17:40