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?

  • $\begingroup$ Why not include 1 as having an even number of distinct prime factors, none? $\endgroup$ – hardmath Feb 27 '13 at 10:55
  • 1
    $\begingroup$ @hardmath: I don't see why not either, but it's not going to make any significant difference anyway. $\endgroup$ – Tara B Feb 27 '13 at 10:57
  • 1
    $\begingroup$ 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. $\endgroup$ – hardmath Feb 27 '13 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: This is similar to Chebyshev's bias and it could well be that generalized primes have similar properties. I don't think the proposition in the OP has been proven either way and even the proof of Chebyshev's bias is conditional.

  • $\begingroup$ 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<B. Does this hold up or is it a trick of small numbers? $\endgroup$ – falang Feb 27 '13 at 13:25
  • $\begingroup$ @falang: edit in response to your comment. $\endgroup$ – daniel Feb 28 '13 at 23:34

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.