I have a question concerning the connection between the Dirichlet Hyperbola Method and properties of both the Mertens function and the prime counting function.

**Preliminary: Mertens function and the Prime Counting function**

Start by generalizing the [Divisor summatory function][1] as

$D_{k,s}(n) = \displaystyle\sum_{j=s}^n D_{k-1,s}(\lfloor \frac{n}{j} \rfloor )$  
$D_{0,s}(n) = 1$  
(1)

(the normal Divisor summatory function can be recovered by setting s to 1).

Using a variation on [Linnik's Identity and a related identity][2], we can express [Mertens function][3] as

$M(n) = \displaystyle\sum_{j=0}^{\log_2{n}} (-1)^j D_{j,2}(n)$  
(2)

and the [prime counting function][4] as

$\pi(n) = \displaystyle\sum_{k=1}^{\log_2{n}}\sum_{j=1}^{\log_2{n^\frac{1}{k}}} \frac{(-1)^{j+1} \mu(k)}{j k} D_{j,2}(n^{\frac{1}{k}})$  
(3)  



**Preliminary: Generalizing the Dirichlet Hyperbola Method**

There are symmetries in (1), which can be expressed by generalizing the [Dirichlet Hyperbola Method][5] into the following recursive identity

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

If we specify *s* as *2* and various whole number values for *k*, as required in (2) and (3) above, we'll find

$D_{1,2}(n) = \lfloor n \rfloor - 1$   
$D_{2,2}(n) = - (\lfloor n^{\frac{1}{2}} \rfloor ^ 2) + 1 +2 \displaystyle\sum_{m=2}^{\lfloor n^\frac{1}{2} \rfloor} \lfloor \frac{n}{m} \rfloor $   
$D_{3,2}(n) = \lfloor n^{\frac{1}{3}} \rfloor ^ 3 - 1 +3 \displaystyle\sum_{m=2}^{\lfloor n^\frac{1}{3} \rfloor} \lfloor \frac{n}{m^2} \rfloor - \lfloor (\frac{n}{m}^\frac{1}{2}) \rfloor^2 + 2 \sum_{j=m+1}^{\lfloor (\frac{n}{m})^\frac{1}{2} \rfloor} \lfloor \frac{\frac{n}{m}}{j} \rfloor $   
...and so on with ever larger expansions.

----------


***THE ACTUAL QUESTION***

My question is two-fold, concerning the intersection of (4) with (2) and (3).

1) Has there been any work done on using this kind of approach as a basis for prime counting algorithms?  Or, alternatively, does anyone have any smart ideas for improving or evolving such an approach?

I've actually turned this approach around in my head for quite some time, but without much luck - hence my question.  Using a suitably large wheel with (4) (say, only letting *m* take on values that are not divisible by primes <= 19) generates a surprisingly fast (in constant time) [prime counting algorithm][6], particularly for using $O(n^\epsilon)$ memory.  It seems to run in something like $O(n^\frac{4}{5})$ time or a bit worse (empirically).

But like I say, that's roughly the ceiling on what I've figured out to do with it.  Has any other work been done on approaches like this?

2) Is there any way to make use of approximations of (4) to say anything interesting about the asymptotic behavior of Mertens function or the prime counting function?  I know the error term of the generalized divisor problem is known to be no worse than $\Delta_k(n) = O(x^{1-\frac{1}{k}} \log^{k-2} x )$, but that doesn't seem enormously useful, and there are definitely deeper structural connections between the various Divisor summatory function values employed in (2) and (3).


----------


**Addendum: Mathematica code**

This is the Mathematica code for (4), as NumDivisors, (3), as PrimeCount, and (2), as Mertens.

    NumDivisors[k_, s_, n_] := 
     Sum[ Binomial[k, j] NumDivisors[j, m + 1, n/(m^(k - j))], {m, s, 
       n^(1/k)}, {j, 0, k - 1}]  
    NumDivisors[0, s_, n_] := 1  
    PrimeCount[n_] := 
     Sum[(-1)^(j + 1)/(j k) MoebiusMu[k] NumDivisors[j, 2, n^(1/k)], {k, 
       1, Log[2, n]}, {j, 1, Log[2, (n^(1/k))]}]  
    Mertens[n_] := 1 + Sum[(-1)^k NumDivisors[k, 2, n], {k, 1, Log[2, n]}]  

These can be tested against the following reference definitions.

    ReferenceNumDivisors[k_, s_, n_] := 
     Sum[ReferenceNumDivisors[k - 1, s, n/j ], {j, s, n}]  
    ReferenceNumDivisors[0, s_, n_] := 1  
    ReferenceCountPrimes[n_] := PrimePi[n]  
    ReferenceMertens[n_] := Sum[ MoebiusMu[j], {j, 1, n}]  


  [1]: http://en.wikipedia.org/wiki/Divisor_summatory_function
  [2]: http://books.google.com/books?id=7Vukkw8ywDgC&pg=PA347&lpg=PA347
  [3]: http://mathworld.wolfram.com/MertensFunction.html
  [4]: http://mathworld.wolfram.com/PrimeCountingFunction.html
  [5]: http://math.stackexchange.com/questions/2062/dirichlets-divisor-problem
  [6]: http://www.icecreambreakfast.com/math/primeshyperbola.cpp
  [7]: http://mathoverflow.net/questions/82911/logarithmic-integral-of-nzeta-zeroes-and-certain-nested-sums-of-the-fractional-p