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.

  • 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