10
$\begingroup$

Can someone explain why this identity gives the number of primes? I don't understand it.

$D_{0,a}(n) = 1$
$D_{k,a}(n) = \displaystyle\sum_{j=1}^{k} \binom{k}{j}\sum_{m=a+1}^{\lfloor n^{\frac{1}{k}}\rfloor}D_{k-j,m}(\frac{n}{m^{j}})$
$\pi(n) = \displaystyle\sum_{j=1}^{\log_2 n}j^{-1}\mu(j)\sum_{k=1}^{\log_2 n^\frac{1}{j}}{-1}^{k+1} k^{-1}D_{k,1}(n^{\frac{1}{j}})$

$\pi(n)$ is the number of primes function here. I tried translating all this into Mathematica:

Dx[0,a_,n_]:=1   Dx[k_,a_,n_]:=Sum[Binomial[k,j] Dx[k-j,m,n/m^j],{m,a+1,Floor[n^k^-1]},{j,1,k}]   NumberOfPrimes[n_]:=Sum[j^-1 MoebiusMu[j](-1)^(k+1) k^-1      Dx[k,1,n^j^-1],{j,1,Log[2,n]},{k,1,Log[2,n^j^-1]}] 

and sure enough NumberOfPrimes[n] is giving me exactly what PrimePi[n] does, so it seems like it works. But I don't understand why.

The place I found this said it was $O(n)$ time and constant space, but it only mentioned the identity in passing and didn't give a derivation.

  • 4
    Where, exactly, did you find this? Title, authors, page numbers please.2012-11-29
  • 0
    Huh. I have several books on number theory here. I think it's from one of them. I was trying to collect all the formulas for prime numbers I could find in one place recently - I should have written down the references along with them. I'll update this question when I find the source.2012-11-30
  • 7
    Miessel-Lehmer is described, with some references, here: http://en.wikipedia.org/wiki/Prime-counting_function#Algorithms_for_evaluating_.CF.80.28x.29 and there has been considerable revision, including completely new methods, a big name being Lagarias. But these methods are generally far from intuitive. A correct explanation is a chapter or two in a book rather than an MSE answer box.2012-11-30
  • 0
    Edited OP to change $n^{\frac{1}{k}}$ in Dx iterator to be $\lfloor n^{\frac{1}{k}}\rfloor$2013-03-05
  • 0
    Possible duplicate of [The myth of no prime formula?](https://math.stackexchange.com/questions/940338/the-myth-of-no-prime-formula)2018-06-25

0 Answers 0