Totient summatory function

<h2 id="properties">Properties</h2>
<p>Applying <a href="/facts/M%25C3%25B6bius_inversion_formula/xDnSrPp6">Möbius inversion</a> to the totient function yields
</p>

Φ
        (
        n
        )
        =
        
          ∑
          
            k
            =
            1
          
          
            n
          
        
        k
        
          ∑
          
            d
            ∣
            k
          
        
        
          
            
              μ
              (
              d
              )
            
            d
          
        
        =
        
          
            1
            2
          
        
        
          ∑
          
            k
            =
            1
          
          
            n
          
        
        μ
        (
        k
        )
        
          ⌊
          
            
              n
              k
            
          
          ⌋
        
        
          (
          
            1
            +
            
              ⌊
              
                
                  n
                  k
                
              
              ⌋
            
          
          )
        
        .
      
    
    {\displaystyle \Phi (n)=\sum _{k=1}^{n}k\sum _{d\mid k}{\frac {\mu (d)}{d}}={\frac {1}{2}}\sum _{k=1}^{n}\mu (k)\left\lfloor {\frac {n}{k}}\right\rfloor \left(1+\left\lfloor {\frac {n}{k}}\right\rfloor \right).}

<p>Φ(<i>n</i>) has the asymptotic expansion
</p>

Φ
        (
        n
        )
        ∼
        
          
            1
            
              2
              ζ
              (
              2
              )
            
          
        
        
          n
          
            2
          
        
        +
        O
        
          (
          
            n
            log
            ⁡
            n
          
          )
        
        =
        
          
            3
            
              π
              
                2
              
            
          
        
        
          n
          
            2
          
        
        +
        O
        
          (
          
            n
            log
            ⁡
            n
          
          )
        
        ,
      
    
    {\displaystyle \Phi (n)\sim {\frac {1}{2\zeta (2)}}n^{2}+O\left(n\log n\right)={\frac {3}{\pi ^{2}}}n^{2}+O\left(n\log n\right),}

<p>where ζ(2) is the <a href="/facts/Riemann_zeta_function/MnfRu7lY">Riemann zeta function</a> evaluated at 2, which is 
  
    
      
        
          
            
              π
              
                2
              
            
            6
          
        
      
    
    {\displaystyle {\frac {\pi ^{2}}{6}}}
  
.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a>
</p>
<h2 id="reciprocal-totient-summatory-function">Reciprocal totient summatory function</h2>
<p>The summatory function of the reciprocal of the totient is
</p>

S
        (
        n
        )
        :=
        
          ∑
          
            k
            =
            1
          
          
            n
          
        
        
          
            1
            
              φ
              (
              k
              )
            
          
        
        .
      
    
    {\displaystyle S(n):=\sum _{k=1}^{n}{\frac {1}{\varphi (k)}}.}

<p><a href="/facts/Edmund_Landau/lVgFVLBw">Edmund Landau</a> showed in 1900 that this function has the asymptotic behavior
</p>

S
        (
        n
        )
        ∼
        A
        (
        γ
        +
        log
        ⁡
        n
        )
        +
        B
        +
        O
        
          (
          
            
              
                log
                ⁡
                n
              
              n
            
          
          )
        
        ,
      
    
    {\displaystyle S(n)\sim A(\gamma +\log n)+B+O\left({\frac {\log n}{n}}\right),}

<p>where γ is the <a href="/facts/Euler%25E2%2580%2593Mascheroni_constant/2kEgRvjC">Euler–Mascheroni constant</a>,
</p>

A
        =
        
          ∑
          
            k
            =
            1
          
          
            ∞
          
        
        
          
            
              μ
              (
              k
              
                )
                
                  2
                
              
            
            
              k
              φ
              (
              k
              )
            
          
        
        =
        
          
            
              ζ
              (
              2
              )
              ζ
              (
              3
              )
            
            
              ζ
              (
              6
              )
            
          
        
        =
        
          ∏
          
            p
            ∈
            
              P
            
          
        
        
          (
          
            1
            +
            
              
                1
                
                  p
                  (
                  p
                  −
                  1
                  )
                
              
            
          
          )
        
        ,
      
    
    {\displaystyle A=\sum _{k=1}^{\infty }{\frac {\mu (k)^{2}}{k\varphi (k)}}={\frac {\zeta (2)\zeta (3)}{\zeta (6)}}=\prod _{p\in \mathbb {P} }\left(1+{\frac {1}{p(p-1)}}\right),}

B
        =
        
          ∑
          
            k
            =
            1
          
          
            ∞
          
        
        
          
            
              μ
              (
              k
              
                )
                
                  2
                
              
              log
              ⁡
              k
            
            
              k
              
              φ
              (
              k
              )
            
          
        
        =
        A
        
        
          ∏
          
            p
            ∈
            
              P
            
          
        
        
          (
          
            
              
                log
                ⁡
                p
              
              
                
                  p
                  
                    2
                  
                
                −
                p
                +
                1
              
            
          
          )
        
        .
      
    
    {\displaystyle B=\sum _{k=1}^{\infty }{\frac {\mu (k)^{2}\log k}{k\,\varphi (k)}}=A\,\prod _{p\in \mathbb {P} }\left({\frac {\log p}{p^{2}-p+1}}\right).}

<p>The constant <i>A</i> = 1.943596... is sometimes known as Landau's totient constant. The sum 
  
    
      
        
          
            ∑
            
              k
              =
              1
            
            
              ∞
            
          
          1
          
            /
          
          (
          k
          
          φ
          (
          k
          )
          )
        
      
    
    {\displaystyle \textstyle \sum _{k=1}^{\infty }1/(k\;\varphi (k))}
  
 converges to
</p>

∑
          
            k
            =
            1
          
          
            ∞
          
        
        
          
            1
            
              k
              φ
              (
              k
              )
            
          
        
        =
        ζ
        (
        2
        )
        
          ∏
          
            p
            ∈
            
              P
            
          
        
        
          (
          
            1
            +
            
              
                1
                
                  
                    p
                    
                      2
                    
                  
                  (
                  p
                  −
                  1
                  )
                
              
            
          
          )
        
        =
        2.20386
        …
        .
      
    
    {\displaystyle \sum _{k=1}^{\infty }{\frac {1}{k\varphi (k)}}=\zeta (2)\prod _{p\in \mathbb {P} }\left(1+{\frac {1}{p^{2}(p-1)}}\right)=2.20386\ldots .}

<p>In this case, the product over the primes in the right side is a constant known as the totient summatory constant,<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> and its value is
</p>

∏
          
            p
            ∈
            
              P
            
          
        
        
          (
          
            1
            +
            
              
                1
                
                  
                    p
                    
                      2
                    
                  
                  (
                  p
                  −
                  1
                  )
                
              
            
          
          )
        
        =
        1.339784
        …
        .
      
    
    {\displaystyle \prod _{p\in \mathbb {P} }\left(1+{\frac {1}{p^{2}(p-1)}}\right)=1.339784\ldots .}

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Arithmetic_function/hULxwsgm">Arithmetic function</a></li></ul>

<ul><li><a href="/facts/Eric_W._Weisstein/FbMuVDep">Weisstein, Eric W.</a> <a href="https://mathworld.wolfram.com/TotientSummatoryFunction.html">"Totient Summatory Function"</a>. <i><a href="/facts/MathWorld/yc1jodbq">MathWorld</a></i>.</li></ul>
<h2 id="external-links">External links</h2>
<ul><li>OEIS Totient summatory function</li>
<li><a href="https://oeis.org/A065483">Decimal expansion of totient constant product(1 + 1/(p^2*(p-1))), p prime >= 2)</a></li></ul>

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

<ol>
<li id="fn:1"><p>Weisstein, Eric W., "Riemann Zeta Function \zeta(2)", MathWorld <a href="/wiki/Eric_W._Weisstein" target="_blank">/wiki/Eric_W._Weisstein</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>OEIS: A065483 <a href="/wiki/On-Line_Encyclopedia_of_Integer_Sequences" target="_blank">/wiki/On-Line_Encyclopedia_of_Integer_Sequences</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
</ol>

Totient summatory function open-in-new

Totient summatory function