Consider $b,n\in\mathbb{N}$ where $b\leq n$. We want to find the parity (ie. odd or even) of the number of divisors of $n$ that are $\leq b$.
The question is to find a fast algorithm to find that parity.
(ref: this is essentially problem E from ACM-NA regional contest 2013: http://ncna-region.unl.edu/regional_2013_final.pdf)
Now the problem is rather easy for $b\geq\frac{n}{2}$, as it boils down to simply checking whether $n$ is a perfect square. However, I can't figure out how to solve for the general case. Obviously, factoring out $n$ is going to be rather slow, but since we are only trying to count the number of divisor, it might not be as hard. The worst case scenario for this problem appeared to be when $b\approx\sqrt{n}$: using the perfect square technique, we can reduce the problem to the case when $b\leq\sqrt{n}$.
I am looking for a polynomial time algorithm, or a proof that it is polynomially reducible from one of the more well-known problem with no known polynomial time solution (or both - :D). If neither are possible, even any suggestions for a reasonably fast algorithm would be appreciated. Thank you for your help.
(not sure which tag to put, number-theory or elementary-number-theory; while I don't have much background in number theory, I don't mind people answering using advanced number theory as long as they provide references)
If you can do this in time $O(f(n))$, then you can factor semiprimes (i.e., $n$ of the form $pq$, where $p$ and $q$ are both primes) in time $O(f(n)\log n)$. To see this, note that if $n=pq$ (with $p<q$), then for all $b<p$, the number of divisors of $n$ less than or equal to $b$ is odd (just $1$), whereas if $p\leq b < \sqrt{n}$, then the number of divisors of $n$ less than or equal to $b$ is even ($1$ and $p$).
By binary searching for the smallest such $b$ in the range $[1, \sqrt{n}]$ where the number of divisors of $n$ less than $b$ is even, we can find $p$ and hence factor $n$.
Factoring semiprimes is considered to be the "hardest" instance of the general integer factorization problem, which has no known polynomial time solution (I believe the best current algorithms run in time something like $O(\exp((\log n)^{1/3}))$). You've already noted the straightforward algorithm that gives you $f(n) = \sqrt{n}$; I'm not sure how to do much better (without using ridiculously high-powered factoring algorithms).