# Number theory problem, parity

Let $f(x)$ denote the number of (not necessarily distinct) prime factors of $x$. Let $n > 1$ be the smallest positive integer for which there are more $i$ with with $f(i)$ even than $f(i)$ odd in the range $1 \leq i \leq n$. Compute $n$ modulo 1000.

• What contest, please? – Gerry Myerson Jan 2 '14 at 18:31

I don't know any way to do this without just doing a lot of computing, and I don't see the "modulo 1000" thing as making it any easier. At http://oeis.org/A072203 there is a tabulation of "(Number of oddly factored numbers $\le n$) $-$ (number of evenly factored numbers $\le n$)" where "A number $m$ is oddly or evenly factored depending on whether $m$ has an odd or even number of prime factors [counting with multiplicity]." It says,
"Polya conjectured that $a(n) \ge 0$ for all $n$, but this was disproved by Haselgrove. Lehman gave the first explicit counterexample, $a(906180359) = -1$; the first counterexample is at $906150257$ (Tanaka)."