# What is the growth rate for divisibility of integers

For a natural number $n\geq 1$, let $PF(n)$ denote the number of prime factors (with multiplicity) of $n$. For example, since $48=2*2*2*2*3$, we have $PF(48)=5$.

For any natural number $N\geq 1$, define $$E(N)=\frac{\sum_{k=1}^N PF(k)}{N},$$ the expected value for the number of prime factors for an integer between $1$ and $N$.

I have computed, for example, that $E(2^{22})\approx 3.63,$ and the sequence generally seems to increase. (Of course, the sequence $E(N)$ is not monotonically increasing, because it decreases when $N$ is prime. But when I evaluate $E(2^m)$ for various $m$, I find it is monotonically increasing for $m\leq 22$.

${\bf Question}$: Does there exist an elementary function $g\colon\{\mathbb N}\rightarrow {\mathbb N}$ such that $$E(n)\in\Theta(g(n)).$$ Here we are using "big-$\Theta$" notation; one function is said to be "big-$\Theta$" of another function if the first is asymptotically bounded above and below by a nonzero constant multiple of the second. By "elementary function," I mean the standard definition; roughly the closure under sum, product, quotient, and composition of exponential, log, and polynomial functions.

• Most integers n have about loglogn factors, which when averaged will make little difference whether multiplicity is considered. I suspect a web search on the phrase "number of factors" may be enlightening. Also, this subject should be covered in a handbook on number theory as well as many analytic number theory texts. Not being a number theorist, I will leave naming the texts to others. Gerhard "But I Do It Anyway" Paseman, 2011.12.31 – Gerhard Paseman Jan 1 '12 at 0:14
• Hope you don't mind me switching notation from $PF(n)$ to $\Omega(n)$. :) $\Omega(n) \leq \tau(n)$, the number of divisors of $n$, and $\sum_{n \leq x}\tau(n) \sim x \log x$ by a result of Dirichlet, so this gives what you want. – Timothy Foo Jan 1 '12 at 0:15
• If you don't count with multiplicity then this is a standard problem and $E(N)$ is asymptotic to $\log \log N$. This is proved in the beginning of Tao and Vu's book, among (I presume) many other places. If you count with multiplicity, I anticipate that you will get at least $O(\log \log N)$ and probably an asymptotic, although I didn't work out the details. – Frank Thorne Jan 1 '12 at 0:17

This Theorem 430, on page 355 of Hardy and Wright, that he "average order" of $\Omega(n)$ is $\log \log n.$ Then they point out, formula 22.10.2, that $$\sum_{n \leq x} \; \Omega (n) \; = \; x \log \log x + B_2 x + o(x)$$ and say how to find the constant $$B_2 = B_1 + \sum_p \; \frac{1}{p(p-1)}.$$ Previously , $B_1$ was given as the constant in Merten's Theorem, first 427: $$\sum_{p \leq x} \; \frac{1}{p} \; = \; \log \log x + B_1 + o(1),$$ then theorem 428, $$B_1 = \gamma + \sum \left\{ \log \left( 1 - \frac{1}{p} \right) + \frac{1}{p} \right\}$$ so that $B_1 = 0.26149721\ldots$
• $B_2=1.0346538\ldots,$ see oeis.org/A083342. – Charles Jan 11 '12 at 19:51
• @Charles, thanks for the value of $B_2$ – Will Jagy Jan 11 '12 at 22:27
• Also, the "normal order" of $\Omega(n)$ is $\log\log n$. This means that for every fixed $\epsilon>0$ the density $\\#\\{ n\le N:|\Omega(n)-\log\log n|\le\epsilon\log\log n\\}/N$ tends to 1 as $N\to\infty$. So, `with probability 1' $\Omega(n)$ lies in $[(1−\epsilon)\log\log n,(1+\epsilon)\log\log n]$. – Dimitris Koukoulopoulos Jan 14 '12 at 6:44
Sorry, I've asked a similar question before, and the current question seems to have been answered there by Cam McLeman. The answer he gives is $PF(n)\approx ln(ln(n)).$ To me, this means that $E(N)$ should also be $ln(ln(N))$.
• $PF(N)$ is certainly not $\approx \log\log N$. $PF(N)$ varies a lot according to $N$ (if $N$ is large and prime, $PF(N)=1$, while if $N$ is of the form $2^k$, then $PF(N)=\log_2 N$). The statements people have been talking about are about the average value of $PF(N)$ (i.e. $E(N)$) – Anthony Quas Jan 1 '12 at 6:20