Optimization: Potential speedup for nth_powerfree

[danaj]

Once we have an initial estimate and the associated count, we can make a very good second estimate by using the Qk ~ 1n/ zeta(k) on the error term.

For instance, we make an initial estimate either using n/zeta(k) of using the midpoint (which for most cases ends up being the same). We calculate the count. This has error say 20000 too low. Then count + 20000 * zeta(k) is going to be very close to the correct value.

We could do this 1 or more times until we're very close (in my tests the very first time will reduce the error from say 30,000 to about 60, which is close enough). No need to bracket.

Alternately, use this in the binary search. If count < n, mid is our new lo value as in the current code. But if hi > 2 * zeta(k) * error then set hi to that. Same thing for the count > n case. (1) that means the next midpoint will be the expected approximation. (2) We want to prove this is actually a proper bound. I believe it is an overestimate (which we need for a bracket), but I haven't sat down to do the math.

In powerfree count, we might be able to save some time by pulling out small constant values at the tail. This is a half-way version of the full squarefree_count optimization. I'm not sure it's really worth doing in the C code, but in my Perl code it is a big deal as the simple bigmath operations are terribly expensive (Sidef beautifully avoids this by using Math::GMPz). The final values can be done by either summing the moebius values in their range or by using two calls to mertens (a version of mertens that did this in a single call would be nice).