I would like to know if this identity (or trivial equivalents) for $\pi(n)$, the count of primes, is currently published anywhere.
$D_{0,a}(n) = 1$
$D_{1,a}(n) = \lfloor n\rfloor-a-1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \Pi(n) = \displaystyle\sum_{k=1}^{\lfloor\log_2 n\rfloor}{-1}^{k+1} k^{-1}D_{k,2}(n)$
$D_{k,a}(n) = \displaystyle\sum_{j=1}^{k} \binom{k}{j}\sum_{m=a}^{\lfloor n^{\frac{1}{k}}\rfloor}D_{k-j,m+1}(\frac{n}{m^{j}}) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \pi(n) = \displaystyle\sum_{j=1}^{\lfloor\log_2 n\rfloor}j^{-1}\mu(j)\Pi(n^{\frac{1}{j}})$
(with $\mu(n)$: Mobius mu function, $\binom{k}{j}$: binomial coefficient)
It seems interesting because evaluating $\pi(n)$ this way is empirically a bit faster than $O(n)$ time and $O(n^\epsilon)$ space or, if $m$ isn't divisible by, say, primes $< 23$ (using a wheel), about $O(n^\frac{4}{5})$ time and $O(n^\epsilon)$ space.
So that's my question - I'm only looking for references (or, better still, published work extending on this).
Only read below this line if you want justification of the time and space bounds claims of this approach.
I'm really looking for references here. That's my interest. Nevertheless, when I posted this originally, some of you seemed dubious about the claims of time and space performance of this approach (and had questions about memoization and caching, too). I actually have a hard time reasoning about its execution time too; hence my claim only that that's what I've found empirically.
So, just to clarify, here is the C++ code I find runs in around O(n) time and essentially no space:
#include "math.h"
long long binomial[30][30];
double D( long long n, int k, long long a ){
if( k == 0 )return 1;
if( k == 1 )return n - a + 1;
double t = 0;
for( long long m = a; m <= pow(n, 1.0 / k) + .0000001; m++ )
for( int j = 1; j <= k; j++ )
t += D( n / pow( (double)m, j ), k-j, m+1 )*binomial[k][j];
return t;
}
long long pi(long long n){
int mu[] = { 0, 1, -1, -1, 0, -1, 1, -1, 0, 0, 1, -1, 0, -1, 1, 1, 0, -1, 0, -1, 0,
1, 1, -1, 0, 0, 1, 0, 0, -1, -1, -1, 0, 1, 1, 1, 0, -1, 1, 1, 0, -1, -1, -1,0, 0,
1, -1, 0, 0, 0, 1, 0, -1, 0, 1, 0, 1, 1, -1, 0, -1, 1, 0, 0, 1, -1 };
// Cache our binomials.
for( int k = 1; k < 30; k++ )
for( int j = 1; j <= k; j++ ){
double m = 1;
for( double i = 1; i <= j; i++ )m *= ( k - ( j - i ) ) / i;
binomial[ k ][ j ] = long long( m + .0000001 );
}
// Run the actual prime counting algorithm
double t = 0.0;
for (int j = 1; j < log((double)n) / log(2.0); j++)
for (int k = 1; k < log( pow( n, 1.0 / j ) ) / log(2.0); k++)
t += pow( -1.0, k + 1 ) * D(pow(n, 1.0 / j) + .0000001, k, 2 ) / k / j * mu[j];
return t + .5;
}
As you can see, I'm almost literally just dumping the equations straight into C functions. Nothing clever at all. You can find this source code, in a timing harness, here. A screen capture of timings up to 10^12 can be found here. For every x10 that input increases, the function takes about 9.0-9.6 times as long. It does seem to be growing very slightly, but that's just eyeballing it. Watching the program's memory usage in Windows Task Manager, it grabs 572k of RAM at program launch, and that number doesn't budge, regardless of input value.
The version with the wheel runs dramatically faster. You can see a screen capture of its timings up to 10^17 here. For every x10 that input increases, the function takes about 6.4-7.1 times as long. I'm even less sure about that timing - it also seems to be going up a bit, though slowly. Watching the program's memory usage in Windows Task Manager, it allocates 45 Megs of RAM at program launch to fill in the wheel (consisting of primes <= 19), and that number doesn't budge, regardless of input value.
The wheel version isn't using any memoizing at all. You can find its source code here. I haven't had any luck finding any ideas relying on caching to substantially improve the algorithm's performance, so that's something I'm really, really interested in (although probably too elaborate for a good MO question).
This link is a .zip file with win32 executables of both implementations.
I'm absolutely willing to be shown I'm wrong about the bounds on this algorithm. For the execution time bound, I do have a tough time reasoning about it. I'm particularly unsure about the long term growth of the wheel version.
I've corrected a few errors in my math notation since this question was originally published; my apologies for that.