Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

This was an exercise to show that, in a sense, the even numbers have more prime factors than the odds, but--if it's right-- I still have a question.

As an heuristic calculation, we could take a large interval (1, 2N) on which the average number of prime factors with repetitions is $\mu$ (for sufficiently large N, $\mu $ is about $ \ln \ln 2N$; see answer to this problem). WLOG N is even, then the set $S_2 = \{N+2, N+4, N+6, ..., 2N \} $ corresponds to a sequence $S_1 = \{\frac{N}{2}+1, \frac{N}{2}+ 2, ..., N \}$. The average number of primes in $S_1$ is only slightly less than $\mu$ for large N$^{(1)}$, and so the average number of primes $\mu_2$ in $ S_2$ is $\mu+1$ primes. Let $\mu_o$ be the average number of primes of odd numbers in $[N,2N]$.

Since on $[N,2N]$ the average number of primes is also about $\mu$, we have that $$\mu =\frac{( \mu_2 + \mu_o)}{2} = \frac{(\mu + 1 + \mu_o )}{2},$$ and so the average number of primes for the odd numbers $^{(2)} $ is $$\mu_o = \mu - 1 = \mu_2 - 2 $$ so

$$\mu_2 - \mu_o \approx 2.$$

This argument has I think a somewhat complicated generalization. Using the same reasoning for multiples of $3, 5,...,p_k $ and so on, the net result would be an average number of primes $\mu_{p_k} $ for multiples of the set $P_k = \{ 2,3,5, ..., p_k \}$ with an increasing number of numbers that are multiples of more than one such prime, so that $\mu_{p_k} > \mu + 1$ and $\mu_{p_k}$ is an increasing function of N (or k ). So if we call $\mu_n$ the average number of primes for non-multiples of $P_k$, I expect that for large N the difference

$$\mu_{p_k} - \mu_n > 2 . $$ My question is whether we reach a point beyond which $$ \mu_{p_k} = \mu + \beta$$ with $\beta(N)>1$ and a,b constants of proportionality with $a > b$ , because multiples of $P_k$ take up more than half the interval, so that $$\mu = a\mu_{p_k} + b\mu_n = a(\mu + \beta) + b\mu_n$$ and $$\mu(1-a) = \mu b = a\beta + b\mu_n$$ and finally $$\mu_n = \mu -\frac{a\beta}{b} < 2.$$

I am guessing so, but that the asymptotic relationships involved make it a somewhat weak assertion?

Hopefully the question is clear. Thanks.

(1) Because $\ln \ln 2N = \ln (\ln 2 + \ln N) \sim \ln \ln N.$

(2) On [1, N] for N = 2,500,000, $\mu_2 - \mu_o$ is about 1.9.

share|cite|improve this question
A happy coincidence that my upvote for this question took you over the $1000$-point threshold for an "established user" -- I like your questions :-) – joriki Jul 20 '12 at 20:21
i am very interested in this question too, thanks @daniel – dato datuashvili Jul 20 '12 at 20:45
up vote 5 down vote accepted

If I understand the question correctly, it's mainly a matter of the order of limits.

There are two numbers going to infinity here, $N$ and $k$. If you keep $k$ fixed and let $N$ go to infinity, your argument goes through just as it did when you considered only $2$ as a factor, and as you say, asymptotically (for $N\to\infty$) the discrepancy between $\mu_{p_k}$ and $\mu_n$ will be greater than $2$; it increases with $k$ (if you let $k$ go to $\infty$ after $N$), and it does so without bound, as does the average number of prime factors itself.

However, that doesn't mean you can write $\beta(N)$, increase $k$ at finite $N$ and conclude from the growing discrepancy that the average number of prime factors for the remaining numbers will eventually fall below $2$; that would only happen if you increase $k$ to a point where $\log\log N$ begins to change significantly from the factors you're pulling out.

To calculate the discrepancy (for fixed $k$ and $N\to\infty)$, note that the reason we get a discrepancy of $2$ considering only the prime factor $2$, and not the $1$ that one might have expected, is that after pulling out a factor of $2$ from the even numbers they still have a chance of containing further factors of $2$, whereas the odd numbers don't. We can express this as


since all numbers on average have $\mu_0$ prime factors other than $2$, half of them half one factor of two, a quarter have two, and so on. We can do the same thing with the other primes up to $p_k$, and the "probabilities" for different primes will asymptotically be independent, so we get


The sum diverges for $k\to\infty$, so you can make the discrepancy arbitrarily large; but you then have to go to very high $N$ to actually see it, since you're pulling out more and more factors.

share|cite|improve this answer
@daniel: I added a calculation of the discrepancy. – joriki Jul 20 '12 at 20:56
Abiding appreciation for this answer, especially given the badly expressed question. Thanks again. – daniel Dec 1 '13 at 16:14

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.