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.

Improve this question
$\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$
    – Gerhard Paseman
    Commented 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$
    – Timothy Foo
    Commented 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$
    – Frank Thorne
    Commented Jan 1, 2012 at 0:17

2 Answers 2

Reset to default
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$

Improve this answer
$\endgroup$
3
  • $\begingroup$ $B_2=1.0346538\ldots,$ see oeis.org/A083342. $\endgroup$
    – Charles
    Commented Jan 11, 2012 at 19:51
  • $\begingroup$ @Charles, thanks for the value of $B_2$ $\endgroup$
    – Will Jagy
    Commented 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$
    – Dimitris Koukoulopoulos
    Commented 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))$.

Improve this answer
$\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$
    – Anthony Quas
    Commented 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
    Commented Jan 1, 2012 at 22:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .