# On the number of integers with an even number of distinct prime factors

Let $A(n)$ be the number of integers from 2 to $n$ with an even number of distinct prime factors, and let $B(n)$ be the number of integers from 2 to $n$ with an odd number of distinct prime factors. (By "distinct" I mean, for example, that $2^{100}$ has one distinct prime factor.)

A little python program shows that as $n$ ranges from 2 to 1000000, there are only 9437 values of $n$ for which $A(n)>B(n)$, whereas there are 990450 values of $n$ for which $A(n)<B(n)$. There are 112 values of $n$ for which $A(n)=B(n)$, the largest of which is 12099.

Is there some precise theorem or conjecture or even plausible heuristic to the effect that $A(n)<B(n)$ "most of the time", or perhaps "eventually"? Or is this just an illusion that dissolves as $n$ grows larger?

-
Why not include 1 as having an even number of distinct prime factors, none? – hardmath Feb 27 at 10:55
@hardmath: I don't see why not either, but it's not going to make any significant difference anyway. – Tara B Feb 27 at 10:57
This OEIS entry gives the counts of distinct prime factors, starting from 1 having none, a function the Wikipedia article denotes as $\omega(n)$. Lots of references given with the OEIS entry. – hardmath Feb 27 at 11:04

The Generalized Prime Number Theorem gives a decent estimate of the number of numbers with k factors less than n. You can use this to see that the number of numbers with 2,4,6,... prime factors should not in the large differ from the number of numbers with 1,3,5,... factors.

The Generalized PNT states:

$$\pi_k(x) \sim \frac{x}{\log x}\frac{(\log\log x)^{k-1}}{(k-1)!}$$

in which $\pi_k(x)$ is the number of numbers with k factors less than or equal to x.

See also problem 168307 (Generalized PNT in limit as numbers get large) which shows that in a sense even numbers have more prime factors than odd ones, and cites a result of Ramanujan that the "normal order" of prime factors of a number n, with or without repetitions, is about $\log\log n.$

For the last see Ramanujan, Collected Works, p. 274. For the Generalized PNT see, for example, G.J.O. Jameson, The Prime Number Theorem, p.145.

Edit in response to comment: For n = 3M, 4M, 5M the ratio of numbers with an odd number of factors to those with even, including repetitions and not including repetitions, appears to approach 1 from above, and the ratio of sums of PNT estimates for odd/even suggests (at least for the case allowing repetitions) this should be the case (let $y = \ln\ln x,$ etc.). I don't think the PNT permits a proof that there are always more odd-factored than even-factored numbers less than n. Perhaps, as with the PNT for k = 1, we can write empirically plausible results that cannot be justified in terms of known error bounds. So I think one would need something else to prove or disprove the specific claim in the OP, which may well be true. (M: =1,000,000)

-
 Thanks for your reference to the Generalized Prime Number Theorem. Do you take that as suggesting that A>B infinitely often and B>A infinitely often? And what about the preponderance of n for which A