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[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 

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
    $\begingroup$ Where, exactly, did you find this? Title, authors, page numbers please. $\endgroup$
    – Will Jagy
    Nov 29, 2012 at 20:48
  • $\begingroup$ 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. $\endgroup$
    – Alvy Olsen
    Nov 30, 2012 at 13:52
  • 7
    $\begingroup$ Miessel-Lehmer is described, with some references, here: en.wikipedia.org/wiki/… 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. $\endgroup$
    – Will Jagy
    Nov 30, 2012 at 19:32
  • $\begingroup$ Edited OP to change $n^{\frac{1}{k}}$ in Dx iterator to be $\lfloor n^{\frac{1}{k}}\rfloor$ $\endgroup$ Mar 5, 2013 at 9:15
  • $\begingroup$ Possible duplicate of The myth of no prime formula? $\endgroup$
    – Klangen
    Jun 25, 2018 at 15:13


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.