2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$ Jan 1, 2012 at 0:14
  • $\begingroup$ 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. $\endgroup$ Jan 1, 2012 at 0:15
  • $\begingroup$ 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. $\endgroup$ Jan 1, 2012 at 0:17

2 Answers 2

7
$\begingroup$

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$

$\endgroup$
3
  • $\begingroup$ $B_2=1.0346538\ldots,$ see oeis.org/A083342. $\endgroup$
    – Charles
    Jan 11, 2012 at 19:51
  • $\begingroup$ @Charles, thanks for the value of $B_2$ $\endgroup$
    – Will Jagy
    Jan 11, 2012 at 22:27
  • $\begingroup$ 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]$. $\endgroup$ Jan 14, 2012 at 6:44
0
$\begingroup$

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))$.

$\endgroup$
2
  • $\begingroup$ $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)$) $\endgroup$ Jan 1, 2012 at 6:20
  • $\begingroup$ 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 mathoverflow.net/questions/43103/… and mathoverflow.net/questions/84266/on-robins-criterion-for-rh/… . A typical result is something <= something * (asymptotic series in 1/loglogn) $\endgroup$
    – Will Jagy
    Jan 1, 2012 at 22:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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