show/hide this revision's text 5 Added more justification and examples for the time and space bound claims.

$D_{0,a}(n) = 11$
$D_{1,a}(n) = \lfloor n\rfloor-a-1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ D_{1,a}(n) = n-a \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \Pi(n) = \displaystyle\sum_{k=1}^{\lfloor\log_2 n\rfloor}{-1}^{k+1} k^{-1}D_{k,2}(n)$

(or, instead, $D_{k,a}(n) = \displaystyle\sum_{j=1}^{k} (-1)^{j-1}\binom{k}{j}\sum_{m=a}^{\lfloor n^{\frac{1}{k}}\rfloor}D_{k-j,m}(\frac{n}{m^{j}})$)with $\pi(n)$: count of primes, $\mu(n)$: Mobius mu function, $\binom{k}{j}$: binomial coefficient)

Some

So that's my question - I'm only looking for references : I'll respond to comments once (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 get a chanceposted this originally, but since a few some of you seem uncertain seemed dubious about the claims of time and space bounds performance of this approach (and had questions about memoization and caching, for some verification:

$\cdot\ \ $This linktoo). 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) + .cpp source file 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   implemented in 35 lines of 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 test harness, here.  $\cdot\ \ $This link is 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.  cpp source file for It does seem to be growing very slightly, but that's just eyeballing it.  Watching the algorithm 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 some optimizations implemented in 180 lines that number doesn't budge, regardless of C 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 timing test harnessgood MO question).
$\cdot\ \ $
This link is a .zip file with win32 executables of both of these filesimplementations.
AN IMPORTANT EDIT: My apologies - I had left out a specialization of $D_{1,a}(n)$ required for this 
I'm absolutely willing to workbe shown I'm wrong about the bounds on this algorithm.  For the execution time bound, assuming it only affected constant I do have a tough time performancereasoning about it.  That was an incorrect assumptionI'm particularly unsure about the long term growth of the wheel version.
I've added it corrected a few errors in my math notation since this question was originally published; my apologies for that.
show/hide this revision's text 4 Fixed an error in the identity - a specific specialization is required for it to work.

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) = n-a \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \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}})$
(or, instead, $D_{k,a}(n) = \displaystyle\sum_{j=1}^{k} (-1)^{j-1}\binom{k}{j}\sum_{m=a}^{\lfloor n^{\frac{1}{k}}\rfloor}D_{k-j,m}(\frac{n}{m^{j}})$)

with $\pi(n)$: count of primes, $\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.

Some references: I'll respond to comments once I get a chance, but since a few of you seem uncertain about the time and space bounds of this, for some verification:

$\cdot\ \ $This link is the .cpp source file for the algorithm implemented in 35 lines of C code in a timing test harness. $\cdot\ \ $This link is the .cpp source file for the algorithm with a wheel and some optimizations implemented in 180 lines of C code in a timing test harness.
$\cdot\ \ $This link is a .zip file with win32 executables of both of these files.

AN IMPORTANT EDIT: My apologies - I had left out a specialization of $D_{1,a}(n)$ required for this to work, assuming it only affected constant time performance. That was an incorrect assumption. I've added it in.
show/hide this revision's text 3 Fixed Memory Bound notation

Any published references for this $O(n)$ time, $O(\epsilon)$ O(n^\epsilon)$ space identity for the count of primes?

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\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \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}})$
(or, instead, $D_{k,a}(n) = \displaystyle\sum_{j=1}^{k} (-1)^{j-1}\binom{k}{j}\sum_{m=a}^{\lfloor n^{\frac{1}{k}}\rfloor}D_{k-j,m}(\frac{n}{m^{j}})$)

with $\pi(n)$: count of primes, $\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(\epsilon)$ 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(\epsilon)$ O(n^\epsilon)$ space.

Some references: I'll respond to comments once I get a chance, but since a few of you seem uncertain about the time and space bounds of this, for some verification:

$\cdot\ \ $This link is the .cpp source file for the algorithm implemented in 35 lines of C code in a timing test harness. $\cdot\ \ $This link is the .cpp source file for the algorithm with a wheel and some optimizations implemented in 180 lines of C code in a timing test harness.
$\cdot\ \ $This link is a .zip file with win32 executables of both of these files.
show/hide this revision's text 2 Added some clarifying references
show/hide this revision's text 1