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

Let $0 < \alpha < 1$ be a constant. The expected number of prime factors of a "random" integer near $n$ which are greater than $n^\alpha$ is $-\log \alpha$.

It's my understanding that (properly formulated) this is a well-known fact in analytic number theory but I cannot find a reference for it. Can anybody provide a reference?

Edited to add (March 28):: The asymptotic density of positive integers $n$ with $k$th largest factor smaller than $n^{1/\alpha}$ is $\rho_k(\alpha)$, where we have $L_0(\alpha) = [\alpha > 0]$ and $$ L_k(\alpha) = [\alpha \ge k] \int_k^\alpha L_{k-1}(t-1) \: {dt \over t}, $$ and $1-\rho_k(\alpha) = \sum_{n=0}^\infty {-k \choose n} L_{n+k}(\alpha)$. (See Riesel, p. 162.) The density of positive integers with $k$th largest factor larger than $n^{1/\alpha}$ is therefore $1-\rho_k(\alpha)$, and so the expected number of factors larger than $n^{1/\alpha}$ is $\sum_{k \ge 1} (1-\rho_k(\alpha))$. Therefore the expected number of such factors is $$ \sum_{k \ge 1} \sum_{n \ge 0} {-k \choose n} L_{n+k}(\alpha). $$ Letting $n+k = j$ we can rewrite this sum as $$ \sum_{j \ge 1} \sum_{n=0}^{j-1} {n-j \choose n} L_j = \sum_{j \ge 1} L_j \left( \sum_{n=-0}^{j-1} (-1)^n {j-1 \choose n} \right) $$ and the inner sum is $0$ except when $j=1$, when it is $1$. So the expected number of factors larger than $n^{1/\alpha}$ is $L_1(\alpha)$; this is $\log \alpha$.

share|cite|improve this question
up vote 2 down vote accepted

Theorem 5.4 of Riesel, Prime Numbers and Computer Methods for Factorization, says "the number of prime factors $p$ of integers in the interval $[N-x,N+x]$ such that $a<\log\log p< b$ is proportional to $b-a$ if $b-a$ as well as $x$ are sufficiently large as $N\to\infty$."

share|cite|improve this answer
I am accepting this even though it is not exactly what I was looking for, because what I was looking for is a couple pages later in Riesel's book. – Michael Lugo Mar 28 '10 at 16:35

You seem to be over complicating things. For $\alpha$ fixed, this is relatively easy to prove. I leave it to you deduce the desired result as a consequence of the following theorem:

Theorem: Let $x>0$ and fix $0<\alpha<1$. Define $\omega_{x,\alpha}(n)=\sum_{p|n,\ p>x^\alpha} 1$. Then this function has average value $$\frac{1}{x}\sum_{n\leq x} \omega_{x,\alpha}(n)=-\log \alpha +O\left(\frac{1}{\log x}\right).$$

Proof: Notice that

$$\frac{1}{x}\sum_{n\leq x} \omega_{x,\alpha}(n)=\frac{1}{x}\sum_{x^{\alpha}<p<\leq x}\left[\frac{x}{p}\right] =\sum_{x^{\alpha}<p<\leq x}\frac{1}{p}-\frac{1}{x}\sum_{x^{\alpha}<p<\leq x}\left\{\frac{x}{p}\right\}$$

$$= \sum_{x^\alpha<p<x} \frac{1}{p} +O\left(\frac{1}{\log x}\right)=\log \log (x)-\log \log x^\alpha +O\left(\frac{1}{\log x}\right)$$ $$=-\log \alpha +O\left(\frac{1}{\log x}\right).$$

share|cite|improve this answer

I believe you can extract this from a paper of Andrew Granville, "Prime divisors are Poisson distributed". There is an electronic copy of this on his website.

share|cite|improve this answer
Maybe. I feel like I've seen it stated explicitly, though. – Michael Lugo Mar 4 '10 at 18:01

Do you mean that $\log(1/\alpha)$ is the expected number of prime factors in $(x^\alpha,x]$ when $\alpha\to0$? For fixed $\alpha\in(0,1)$ what you are claiming is not true. For example,

$|\{n\le x:\exists p|n\;{\rm with}\;\sqrt{x}\lt p\le x\}|\sim x\log2 $


$|\{n\le x:p\le\sqrt{x}\;{\rm for all}\;p|n\}|\sim(1-\log2)x$.

When $\alpha\to0$ it is not hard to prove what you need, but I am not sure where you can find a precise reference. For example, setting $\omega(n;y,z)=|\{p|n:y\lt p\le z\}|$ and following the proof of Theorem 6 in page 311 in Tenenbaum's book "Introduction to Analytic and Probabilistic Number Theory" gives that

$|\{n\le x:|\omega(n;x^\alpha,x)-\log(1/\alpha)|\ge(1+\delta)\log(1/\alpha)\}|\ll x\alpha^{Q(1+\delta)},$

where $Q(1+\delta)=\int_1^{1+\delta}\log tdt$.

share|cite|improve this answer

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.