理解 Sigma 函数：因子、乘法性与公式推导

一文看懂 Sigma 函数：因子分解的终极威力！ σ(n) 完全解析：为什么求和函数能“自动”变成乘积？ 数学之美：Sigma 函数的推导、公式与 Python 实现 从几何级数到质因数：Sigma 函数的魔法公式大揭秘 搞懂 σ(n) 的那一天，我看到了数学的秩序 为什么 σ(n) = 乘积？带你走进数论的核心思想 Divisor 终极指南：Sigma 函数推导 + 代码 一篇搞定

Sigma 函数，记作 [math]\sigma(n)[/math]，表示一个整数所有正因子的和。 例如 12 的因子有 1、2、3、4、6、12，因此 [math]\sigma(12)=28[/math]。 本文解释什么是 Sigma 函数、为什么它满足乘法性、如何从质因数分解推导出通用公式，并给出高效的 Python 实现。

可除性符号

在数论中，符号 “|” 表示“整除”。 [math]d \mid a \quad \Longleftrightarrow \quad \exists k \in \mathbb{Z},\; a = dk[/math] 因此表达式 [math]\sum_{d \mid n} d[/math] 的意思是“对所有能整除 n 的 d 求和”。

质因数分解与因子的结构

任意正整数 [math]n[/math] 都可以唯一写成： [math]n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}[/math] 它的一个因子必须从每个质数的指数中“选择”一个： [math]d = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}, \qquad 0 \le e_i \le a_i[/math] 所有因子结构的规律都来自这个事实。

关键性质：Sigma 函数是乘法性的

当两个整数互质时，Sigma 函数满足： [math]\sigma(mn) = \sigma(m)\,\sigma(n) \qquad \text{if} \gcd(m,n)=1[/math] 原因是：若 [math]m[/math] 和 [math]n[/math] 的质因数互不相同， 那么 [math]mn[/math] 的每个因子都能唯一写成： [math]d = d_m d_n, \quad d_m \mid m, \; d_n \mid n[/math] 因此对所有因子求和可以写成二重求和： [math]\sigma(mn) = \sum_{d_m \mid m} \sum_{d_n \mid n} d_m d_n[/math] 接下来把二重求和“拆开”。固定某个 [math]d_m[/math]，则： [math]\sum_{d_n \mid n} (d_m d_n) = d_m \sum_{d_n \mid n} d_n = d_m \sigma(n)[/math] 再对所有 [math]d_m[/math] 求和： [math]\sigma(mn) = \sum_{d_m \mid m} d_m \sigma(n) = \sigma(n) \sum_{d_m \mid m} d_m = \sigma(n)\sigma(m)[/math] 这就证明了 Sigma 的乘法性。

质数幂的 Sigma 公式

利用乘法性，只需计算 [math]\sigma(p^k)[/math]。 其因子为： [math]1, p, p^2, \ldots, p^k[/math] 这是一个几何级数： [math]\sigma(p^k) = 1 + p + p^2 + \cdots + p^k = \frac{p^{k+1} - 1}{p - 1}[/math] 把所有质因数幂的贡献相乘，就得到通用公式： [math]\sigma(n) = \prod_{i=1}^k \frac{p_i^{a_i+1} - 1}{p_i - 1}[/math] 这就是任意正整数的因子和公式。

示例：计算 σ(12)

质因数分解： [math]12 = 2^2 \cdot 3^1[/math] 分别计算： [math]\sigma(2^2) = 1 + 2 + 4 = 7[/math] [math]\sigma(3^1) = 1 + 3 = 4[/math] 相乘： [math]\sigma(12) = 7 \cdot 4 = 28[/math]

Python 实现：高效的 Sigma 函数

以下是基于质因数分解与乘法性的高效Python实现，时间复杂度约为 [math]O(\sqrt{n})[/math]。

def sigma(n: int) -> int:
    """高效计算因子和函数 σ(n)。"""
    total = 1
    x = n

    # 处理质因数 2
    count = 0
    while x % 2 == 0:
        x //= 2
        count += 1
    if count > 0:
        total *= (2 ** (count + 1) - 1) // (2 - 1)

    # 处理奇质数
    p = 3
    while p * p <= x:
        if x % p == 0:
            count = 0
            while x % p == 0:
                x //= p
                count += 1
            total *= (p ** (count + 1) - 1) // (p - 1)
        p += 2

    # 若剩下的是质数
    if x > 1:
        total *= (x**2 - 1) // (x - 1)

    return total

结语

Sigma 函数展示了因子结构的优雅与质因数分解的力量。通过理解乘法性与几何级数求和，我们得到一个漂亮的闭式公式，并能编写高效的计算程序。有了理论与代码，你就能深入探索更多数论中的算术函数了。 [show_file file="/var/www/wp-post-common/justyy.com/math.php"] 英文：Understanding the Sigma Function: Divisors, Multiplicativity, and the Formula