数数论

完全数，因子之和函数

字数统计: 1.6k字   |   阅读时长: 6分
, ,

摘要: 完全数

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文我们介绍一下最早由古希腊人提出的完全数，也称完美数。对于一个正整数 $n$，如果除它自身以外所有的正因子之和等于该正整数 $n$ 自身。则称其为完美数。

在欧几里得《几何原本》中有关于求某些完美数的方法：如果 $2^{p} - 1$ 是素数，则 $2^{p-1}(2^{p} - 1)$ 是完美数，这是偶完美数的一个充分条件。后来欧拉给出了偶完全数的必要条件，正是欧几里得提出的计算公式。

也就是对偶数 $n$ 来说，完全数的充要条件为 $n = 2^{p-1}(2^{p} - 1)$，其中 $2^{p} - 1$ 为梅森素数。即每找到一个梅森素数，即找到一个偶完美数。然而梅森素数本身就非常稀疏，因此偶完全数也是非常少，前几个梅森素数与完美数的数列如下，可以看到第 6 个完美数就达到了 $8e9$ 级别：

$p$ 2 3 5 7 13 17
$2^{p} - 1$ 3 7 31 127 8191 131071
$2^{p-1}(2^{p} - 1)$ 6 28 496 8128 33550336（$3e7$级别） 8589869056（$8e9$级别）

但是是否存在奇完全数目前还不知道。已知的结果是不存在小于 $10^{300}$ 的奇完全数。

本文我们证明欧几里得完全数公式以及欧拉完全数定理，其中用到了因子之和函数 $\sigma(n)$，也简要介绍一下该函数。最后我们解决力扣 507. 完美数。

欧几里得完全数公式

定理(欧几里得)

如果 $2^{p} - 1$ 是素数，则 $2^{p-1}(2^{p} - 1)$ 是完全数。

证明

设 $q = 2^{p} - 1$，我们要证明 $2^{p-1}q$ 是完全数。

$2^{p-1}q$ 的真因数分为两部分，第一部分为 $1,2,4,\cdots,2^{p-1}$ 第二部分为 $q,2q,4q,\cdots,2^{p-2}q$。

由等比数列求和公式 $1+x+x^{2} + \cdots + x^{p-1} = \frac{x^{p}-1}{x-1}$。

令 $x=2,n=p$ 得 $2^{p}-1=q$。即第一部分真因数的和为 $q$。

另一方面，$q+2q+4q+\cdots + 2^{p-2}q = q\frac{2^{p-1}-1}{2-1} = q(2^{p-1}-1)$，这是第二部分真因数。

将两部分相加，得 $q + q(2^{p-1}-1) = 2^{p-1}q$，这正是原数。

因此 $2^{p-1}q$ 是完全数。

$\Box$

因子之和函数 $\sigma(n)$

记 $\sigma(n)$ 表示 $n$ 的所有因子之和，包括 1 和 n，称为因子之和函数。

下面我们直接给出 $\sigma(n)$ 的两个结论，一个是素数幂 $p^{k}$ 的因子之和 $\sigma(p^{k})$，一个是 $\sigma(n)$ 为积性函数。证明参考数论相关的资料。

定理($\sigma(p^{k})$ 的值)

若 $p$ 为素数，$k \geq 1$，则：

定理($\sigma(n)$为积性函数)

若 $\gcd(m, n) = 1$，则：

欧拉完全数定理

定理(欧拉)

如果 $n$ 是偶完全数，则 $n$ 形如 $n = 2^{p-1}(2^{p}-1)$，其中 $2^{p}-1$ 是梅森素数。

证明

设 $n$ 为偶完全数。

由于 $n$ 为偶数，则其可分解为 $n=2^{k}m$，其中 $k\geq 1$ 且 $m$ 是奇数。

由于 $\gcd(2^{k}, m) = 1$，因此：

由于 $n$ 是完全数，所以 $\sigma(n) = 2n = 2^{k+1}m$，因此：

显然 $2^{k+1} - 1$ 是奇数，且 $(2^{k+1}-1)\sigma(m)$ 是 $2^{k+1}$ 的倍数，所以 $2^{k+1}$ 整除 $\sigma(m)$，也就是存在整数 $c$ 使得 $\sigma(m) = 2^{k+1}c$，代入后得：

两边消去 $2^{k+1}$ 得 $m = (2^{k+1}-1)c$。

下面通过反证法证明这里 $c = 1$。

如果 $c > 1$，则 $m = (2^{k+1}-1)c$ 被不同的 $1,c,m$ 整除，即：

另一方面，我们知道 $\sigma(m) = 2^{k+1}c$，于是 $2^{k+1}c \geq 1 + 2^{k+1}c$，导出矛盾。

于是我们得到，对于偶完全数 $n = 2^{k}m$，有：

也就是说 $m$ 的因子只有 $m$ 和 $1$，即 $m = 2^{k+1}-1$ 为质数。

因此，若 $n$ 为偶完全数，则 $n = 2^{k}(2^{k+1}-1)$ 其中 $2^{k+1}-1$ 为质数。

定理(梅森素数)

对于整数 $a \geq 2, n \geq 2$，如果 $a^{n}-1$ 是素数，则 $a=2$ 且 $n$ 为素数。

由梅森素数相关的结论，如果 $2^{k+1}-1$ 为质数，则 $p = k+1$ 为质数。

于是得到最终结论，偶完全数 $n$ 形如 $n = 2^{p-1}(2^{p}-1)$，其中 $2^{p}-1$ 为梅森素数。

$\Box$

507. 完美数

对于一个 正整数，如果它和除了它自身以外的所有 正因子 之和相等，我们称它为 「完美数」。

给定一个 整数 n， 如果是完美数，返回 true；否则返回 false。

提示：

1
2
3
4
5
6
7
8
9
10
11
12
1 <= num <= 1e8


>示例 1：
>输入：num = 28
>输出：true
>解释：28 = 1 + 2 + 4 + 7 + 14
>1, 2, 4, 7, 和 14 是 28 的所有正因子。
>
>示例 2：
>输入：num = 7
>输出：false

算法：数论、试除法

通过试除法将每个 $N$ 的因子累加，试除结束后对比原数与累加和是否相等即可。

$O(\sqrt{N})$

代码 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import math

class Solution:
    def checkPerfectNumber(self, num: int) -> bool:
        if num == 1:
            return False
        s = 1;
        for i in range(2, int(math.sqrt(num)) + 1):
            if num % i == 0:
                s += i
                s += num / i
            if s > num:
                break
        return s == num

算法2：数论、打表

根据数论中关于梅森素数与完全数的结论，在 $1e8$ 的范围内，奇完全数不存在，偶完全数只有 6、28、496、8128、33550336 这 5 个。

1
2
3
4
class Solution:
    def checkPerfectNumber(self, num: int) -> bool:
        setting = {6, 28, 496, 8128, 33550336}
        return num in setting
Share