Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
4  
Where, exactly, did you find this? Title, authors, page numbers please. –  Will Jagy Nov 29 '12 at 20:48
    
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. –  Alvy Olsen Nov 30 '12 at 13:52
5  
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. –  Will Jagy Nov 30 '12 at 19:32
    
Edited OP to change $n^{\frac{1}{k}}$ in Dx iterator to be $\lfloor n^{\frac{1}{k}}\rfloor$ –  Fred Kline Mar 5 '13 at 9:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.