In number theory , the totient summatory function
Φ
(
n
)
{\displaystyle \Phi (n)}
summatory function of Euler's totient function defined by:
Φ
(
n
)
:=
∑
k
=
1
n
φ
(
k
)
,
n
∈
N
{\displaystyle \Phi (n):=\sum _{k=1}^{n}\varphi (k),\quad n\in \mathbf {N} }
It is the number of coprime integer pairs {p, q}, 1 ≤ p ≤ q ≤ n .
The first few values are 0, 1, 2, 4, 6, 10, 12, 18, 22, 28, 32 (sequence A002088 OEIS ). Values for powers of 10 at (sequence A064018 OEIS ).
Using Möbius inversion to the totient function, we obtain
Φ
(
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)}
Φ(n ) has the asymptotic expansion
Φ
(
n
)
∼
1
2
ζ
(
2
)
n
2
+
O
(
n
log
n
)
,
{\displaystyle \Phi (n)\sim {\frac {1}{2\zeta (2)}}n^{2}+O\left(n\log n\right),}
where ζ(2) is the Riemann zeta function for the value 2.
Φ(n ) is the number of coprime integer pairs {p, q}, 1 ≤ p ≤ q ≤ n .
The summatory of reciprocal totient function
edit
The summatory of reciprocal totient function is defined as
S
(
n
)
:=
∑
k
=
1
n
1
φ
(
k
)
{\displaystyle S(n):=\sum _{k=1}^{n}{\frac {1}{\varphi (k)}}}
Edmund Landau showed in 1900 that this function has the asymptotic behavior
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)}
where γ is the Euler–Mascheroni constant ,
A
=
∑
k
=
1
∞
μ
(
k
)
2
k
φ
(
k
)
=
ζ
(
2
)
ζ
(
3
)
ζ
(
6
)
=
∏
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}\left(1+{\frac {1}{p(p-1)}}\right)}
and
B
=
∑
k
=
1
∞
μ
(
k
)
2
log
k
k
φ
(
k
)
=
A
∏
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}\left({\frac {\log p}{p^{2}-p+1}}\right).}
The constant A = 1.943596...Landau's totient constant . The sum
∑
k
=
1
∞
1
k
φ
(
k
)
{\displaystyle \textstyle \sum _{k=1}^{\infty }{\frac {1}{k\varphi (k)}}}
∑
k
=
1
∞
1
k
φ
(
k
)
=
ζ
(
2
)
∏
p
(
1
+
1
p
2
(
p
−
1
)
)
=
2.20386
…
{\displaystyle \sum _{k=1}^{\infty }{\frac {1}{k\varphi (k)}}=\zeta (2)\prod _{p}\left(1+{\frac {1}{p^{2}(p-1)}}\right)=2.20386\ldots }
In this case, the product over the primes in the right side is a constant known as totient summatory constant ,[ 1]
∏
p
(
1
+
1
p
2
(
p
−
1
)
)
=
1.339784
…
{\displaystyle \prod _{p}\left(1+{\frac {1}{p^{2}(p-1)}}\right)=1.339784\ldots }
