完全数,因子之和函数

  |  

摘要: 完全数

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


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

在欧几里得《几何原本》中有关于求某些完美数的方法:如果 $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