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.

  • 4
    $\begingroup$ A happy coincidence that my upvote for this question took you over the $1000$-point threshold for an "established user" -- I like your questions :-) $\endgroup$
    – joriki
    Jul 20, 2012 at 20:21
  • 1
    $\begingroup$ i am very interested in this question too, thanks @daniel $\endgroup$ Jul 20, 2012 at 20:45

1 Answer 1


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.

  • $\begingroup$ @daniel: I added a calculation of the discrepancy. $\endgroup$
    – joriki
    Jul 20, 2012 at 20:56
  • 1
    $\begingroup$ Abiding appreciation for this answer, especially given the badly expressed question. Thanks again. $\endgroup$
    – daniel
    Dec 1, 2013 at 16:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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