# Even numbers have more factors than odd numbers…

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.

-
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

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

$$\mu=\mu_0+\frac12+\frac14+\frac18+\dotso=\mu_0+\frac1{2-1}=\mu_0+1\;,$$

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

$$\mu=\mu_n+\sum_{m=1}^k\frac1{p_m-1}\;.$$

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.

-
@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