数论函数

贡献者： int256; hfb25

预备知识　映射

　　以自然数集或正整数集为定义域，以一数集¹为值域的函数称为数论函数。

　　下面列出常见的数论函数（均定义在自然数集上，其中的 $\lambda$ 均是实数）:

单位函数 $I(n)$
\begin{equation} I(n) = \begin{cases} 1\quad (n = 1)\\ 0\quad (n > 1)~. \end{cases} \end{equation}
有时也表示为 $\varepsilon(n)$。
单值函数 $u(n)$
\begin{equation} u(n)\equiv1~. \end{equation}
恒等函数 $e(n)$
\begin{equation} e(n)=n~. \end{equation}
幂函数 $n^\lambda$
对数函数² $\log n$
幂函数 $\operatorname{id}_k(n) = n^k, \operatorname{id} = \operatorname{id}_1$。

除数函数 $d(n)$
\begin{equation} d(n)=\sum_{d|n} 1= \begin{cases} 1&(n=1)\\ \prod\limits_{i=1}^{s}(\alpha_i+1)&(n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_s^{\alpha_s})~. \end{cases} \end{equation}
除数和函数 $\sigma(n)$
\begin{equation} \sigma(n)=\sum_{d|n}d= \begin{cases} 1&(n=1)\\ \prod\limits_{i=1}^{s}\dfrac{p_i^{\alpha_i+1}-1}{p_i-1}&(n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_s^{\alpha_s})~. \end{cases} \end{equation}
除数幂和函数 $\sigma_\lambda(n)$
\begin{equation} \sigma_\lambda(n)=\sum_{d|n}d^\lambda~. \end{equation}
不同素因子个数 $\omega(n)$
\begin{equation} \omega(n)=\sum_{p|n}1= \begin{cases} 0\quad (n=1)\\ s\quad(n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_s^{\alpha_s})~. \end{cases} \end{equation}
全部素因子个数（按重数计）$\Omega(n)$
\begin{equation} \Omega(n)=\sum_{p^r\|n}r= \begin{cases} 0&(n=1)\\ \sum\limits_{i=1}^{s}\alpha_i&(n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_s^{\alpha_s})~.\\ \end{cases} \end{equation}

素数计数函数 $\pi(n)$
\begin{equation} \pi(n)=\sum_{p\leq n} 1~. \end{equation}
$\mathrm{M\ddot{o}bius}$ 函数 $\mu(n)$
\begin{equation} \mu(n)= \begin{cases} 1&\ (n=1)\\ 0&\ (n=l^2k,\ l>1,\ l,k\in\mathbb{N})\\ (-1)^s&\ (n=p_1p_2p_3\cdots p_s)~. \end{cases} \end{equation}
$\mathrm{Euler}$ 函数 $\varphi(n)$
\begin{equation} \varphi(n)=\sum_{1\leq d\leq n,(d,n)=1}1~. \end{equation}
$\mathrm{van\ Mangoldt}$ 函数 $\Lambda(n)$
\begin{equation} \varLambda(n)= \begin{cases} \ln p&\ (n=p^s)\\ 0&\ (\omega(n)\neq 1)~. \end{cases} \end{equation}
有以下常用性质： $$\ln n = \sum_{d|n} \varLambda(d) ~,$$ $$\varLambda(n) = \sum_{d|n} \mu\left(\frac nd\right) \ln\left(d\right) ~,$$ $$\varLambda(n) = - \sum_{d|n} \mu(d) \ln d ~.$$
$\mathrm{Liouville}$ 函数 $\lambda(n)$
\begin{equation} \lambda(n)=(-1)^{\Omega(n)}~. \end{equation}
有性质：$\mu(n) = \sum_{d^2 | n} \mu(d) \lambda{n/d^2}$。
$\vartheta(x)$ 函数
\begin{equation} \vartheta(x) = \sum_{1 \le p \le x} \ln p = \ln\left(\prod_{1 \le p \le x} p\right) ~. \end{equation}
$\psi(x)$ 函数
\begin{equation} \psi(x) = \sum_{1 \le p^m \le x} \ln p = \sum_{1 \le n \le x} \varLambda(n)~, \end{equation}

1. ^ 指复数域的一个子集。
2. ^ 在数论研究中，对数函数的底默认为自然常数 $e$。