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.

  • 3
    $\begingroup$ What contest, please? $\endgroup$ – 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)."

The Tanaka reference is Tanaka, M. "A Numerical Investigation on Cumulative Sum of the Liouville Function". Tokyo Journal of Mathematics 3:1 (1980), pp. 187-189.

  • $\begingroup$ Interesting. I'll look up how Lehman managed to find that. $\endgroup$ – Ayesha Jan 2 '14 at 19:29

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.