Dirichlet hyperbola method

<h2 id="examples">Examples</h2>
Let σ0(n) be the <a href="/facts/Divisor_function/rzvm1jw2">divisor-counting function</a>, and let D(n) be <a href="/facts/Divisor_summatory_function/LC52uv0F">its summatory function</a>:

D
        (
        n
        )
        =
        
          ∑
          
            k
            =
            1
          
          
            n
          
        
        
          σ
          
            0
          
        
        (
        k
        )
        .
      
    
    {\displaystyle D(n)=\sum _{k=1}^{n}\sigma _{0}(k).}

Computing D(n) naïvely requires <a href="/facts/Integer_factorization/EjMCTz2t">factoring</a> every integer in the interval [1, n]; an improvement can be made by using a modified <a href="/facts/Sieve_of_Eratosthenes/ACzqmLGE">Sieve of Eratosthenes</a>, but this still requires Õ(n)<a href="/facts/Big_O_notation/weFFjSWg"> time</a>. Since σ0 admits the Dirichlet convolution σ0 = 1 ∗ 1, taking a = b = √n in (1) yields the formula

D
        (
        n
        )
        =
        
          ∑
          
            x
            =
            1
          
          
            
              n
            
          
        
        
          ∑
          
            y
            =
            1
          
          
            n
            
              /
            
            x
          
        
        1
        ⋅
        1
        +
        
          ∑
          
            y
            =
            1
          
          
            
              n
            
          
        
        
          ∑
          
            x
            =
            1
          
          
            n
            
              /
            
            y
          
        
        1
        ⋅
        1
        −
        
          ∑
          
            x
            =
            1
          
          
            
              n
            
          
        
        
          ∑
          
            y
            =
            1
          
          
            
              n
            
          
        
        1
        ⋅
        1
        ,
      
    
    {\displaystyle D(n)=\sum _{x=1}^{\sqrt {n}}\sum _{y=1}^{n/x}1\cdot 1+\sum _{y=1}^{\sqrt {n}}\sum _{x=1}^{n/y}1\cdot 1-\sum _{x=1}^{\sqrt {n}}\sum _{y=1}^{\sqrt {n}}1\cdot 1,}

which simplifies to

D
        (
        n
        )
        =
        2
        ⋅
        
          ∑
          
            x
            =
            1
          
          
            
              n
            
          
        
        
          ⌊
          
            
              n
              x
            
          
          ⌋
        
        −
        
          
            ⌊
            
              
                n
              
            
            ⌋
          
          
            2
          
        
        ,
      
    
    {\displaystyle D(n)=2\cdot \sum _{x=1}^{\sqrt {n}}\left\lfloor {\frac {n}{x}}\right\rfloor -\left\lfloor {\sqrt {n}}\right\rfloor ^{2},}

which can be evaluated in O(√n) operations.
The method also has theoretical applications: for example, <a href="/facts/Peter_Gustav_Lejeune_Dirichlet/b5UIU7Uy">Peter Gustav Lejeune Dirichlet</a> introduced the technique in 1849 to obtain the estimate<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a><a class="footnote-ref" id="fnref:2" href="#fn:2">2</a>

D
        (
        n
        )
        =
        n
        log
        ⁡
        n
        +
        (
        2
        γ
        −
        1
        )
        n
        +
        O
        (
        
          
            n
          
        
        )
        ,
      
    
    {\displaystyle D(n)=n\log n+(2\gamma -1)n+O({\sqrt {n}}),}

where γ is the <a href="/facts/Euler%E2%80%93Mascheroni_constant/2kEgRvjC">Euler–Mascheroni constant</a>.

<h2 id="external-links">External links</h2>
<ul><li><a href="https://gbroxey.github.io/blog/2023/04/30/mult-sum-1.html">Discussion of the Dirichlet hyperbola method for computational purposes</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Dirichlet, Peter Gustav Lejeune (1849). "Über die Bestimmung der mittleren Werthe in der Zahlentheorie". Abhandlungen der Königlich Preussischen Akademie der Wissenchaften (in German): 49–66 – via Gallica. <a href="/wiki/Peter_Gustav_Lejeune_Dirichlet" target="_blank">/wiki/Peter_Gustav_Lejeune_Dirichlet</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Tenenbaum, Gérald (2015-07-16). Introduction to Analytic and Probabilistic Number Theory. American Mathematical Soc. p. 44. ISBN 9780821898543. <a href="9780821898543" target="_blank">9780821898543</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
</ol>

Dirichlet hyperbola method open-in-new

Dirichlet hyperbola method