MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 6 down vote accepted

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$

share|cite|improve this answer
$B_2=1.0346538\ldots,$ see – 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))$.

share|cite|improve this answer
$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
Dear David, Hardy and Wright really is very good, and the one math book I noticed on the bookshelves of computer science professors when I was a student. The topic of explicit upper bounds (improving on lim sup results) is more recent and often comes with the names Jean-Louis Nicolas (Lyon) and Guy Robin (Limoges), see… and… . A typical result is something <= something * (asymptotic series in 1/loglogn) – Will Jagy Jan 1 '12 at 22:26

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.