1
$\begingroup$

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.

$\endgroup$
1
  • 3
    $\begingroup$ What contest, please? $\endgroup$ Commented Jan 2, 2014 at 18:31

1 Answer 1

2
$\begingroup$

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .