6
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ What do you mean by $O(\epsilon)$? $\endgroup$ Dec 19, 2012 at 18:36
  • $\begingroup$ Oh - epsilon. Negligible. Probably $\log n$ or thereabouts, because the recursive depth of $D_{k,a}(n)$ grows at roughly $\log n$ Essentially it doesn't use any memory at all for practical purposes. $\endgroup$ Dec 19, 2012 at 18:47
  • 1
    $\begingroup$ I don't agree that this procedure is confined to a small amount of space. Yes, the indices of $D$ won't get larger than $\log n$ or so, but each of those functions must be evaluated at tons of arguments. I suspect you actually have more than $n$ such evaluations in total. (I also disagree that restricting to $n$ not divisible by small primes will result in a power savings in the time variable.) $\endgroup$ Dec 19, 2012 at 19:13
  • 5
    $\begingroup$ Perhaps you intended to write $O(n^\epsilon)$ space? This of course cannot be done in $O(\epsilon)=O(1)$ space. But I don't even see how that can be done. What is memoized and what is recomputed? $\endgroup$
    – Charles
    Dec 19, 2012 at 23:12
  • $\begingroup$ Charles: I suppose I did mean $O(n^\epsilon)$. Anyway, in neither implementation are any values memoized. This is especially easy to see in the first C implementation I linked to. If you skim the 25 lines of code of the actual algorithm, you can see it's literally transcribing the identity I'm asking about verbatim. No tricks or cleverness (aside from specializing D_1 for constant time speed improvement). Aside from pushing functions onto the stack to a depth of $\log_2 n$, no memory is ever allocated. Also notice my edit; sorry about that. $\endgroup$ Dec 20, 2012 at 21:47

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.