Dan Asimov <dasimov@earthlink.net> wrote:

Keith's February puzzle led me to wonder:

Let pf(n) denote the number of prime factors of n, counting multiplicity. ...

I don't know, but I do know that if you instead said that any number with a repeat prime factor isn't counted at all, your question would be equivalent to the Reimann Hypothesis. In other words, add 1 for any number that's the product of even number of unique primes, add 0 for any number with any duplicate prime factors (i.e. any number divisible by a square), and subtract 1 for any number that's the product of odd number of unique primes. (This is the Mertens function, Sloane's A002321).

Such questions are always philosophically tricky, since the outcomes of independent random trials will have probability 0 of conforming exactly to any number-theoretic function like Q.

The question that's equivalent to the RH is whether the Mertens function exceeds Big-O(n^(1/2 + epsilon)).