文章目录
- 一、何谓完美数
- 二、寻找完美数
- (一)编程思路
- (二)编写程序
- (三)运行程序
- 三、实战小结
一、何谓完美数
- 完美数是一种特殊的自然数,它等于其所有正除数(不包括其本身)之和。完美数非常稀有,并且只存在于偶数中。第一个完美数是 6 6 6,其除数 1 1 1、 2 2 2、 3 3 3的和等于它本身。完美数与梅森素数紧密相关,如果 2 p − 1 2^p - 1 2p−1是梅森素数,那么 2 p − 1 ( 2 p − 1 ) 2^{p-1}(2^p - 1) 2p−1(2p−1)就是完美数。古希腊数学家欧几里得首次描述了完美数,但直到现代,已知的完美数仍然不多。寻找完美数是数论中一个古老而深奥的问题,至今仍在数学研究中占有一席之地。随着数值的增大,发现新的完美数变得越来越困难,需要高效的算法和强大的计算资源。
- 6 = 1 + 2 + 3 6 = 1 + 2 + 3 6=1+2+3是最小的完美数,不仅如此, 6 = 1 × 2 × 3 6 = 1 \times 2 \times 3 6=1×2×3,《圣经》开篇《创世纪》里提到,上帝用6天的时间创造了世界(第 7 7 7天是休息日),而相信地心说的古希腊人认为,月亮围绕地球旋转所需的时间是 28 28 28天(即便在哥白尼的眼里,太阳系也恰好有 6 6 6颗行星)。古罗马思想家圣奥古斯都在《上帝之城》中写道:“ 6 6 6这个数本身就是完美的,并非因为上帝造物用了 6 6 6天;事实上,恰恰因为 6 6 6是完美的,所以上帝在 6 6 6天之内把一切事物都造好了。”
- 迄今为止( 2024 2024 2024年 7 7 7月 9 9 9日),人们只发现
51
个偶完美数,没有人找到一个奇完美数,也没有人能够否定它的存在。不难证明,偶完美数均以数字 6 6 6或 8 8 8结尾。古希腊人曾猜测它们交替以 6 6 6和 8 8 8结尾,后来被证实是错误的。统计已有的完美数,以 8 8 8结尾的和以 6 6 6结尾的完美数分别是 19 19 19个和 32 32 32个,这个比值趋近于黄金分割比!有意思的是,黄金分割恰好也是毕达哥拉斯学派提出来的,只是他们当初没想过其与完美数之间可能存在某种联系。 - 所谓黄金分割比是指把一条线段分割成两部分,使其中一部分与全长之比等于另一部分与这部分之比,其比值是 5 − 1 2 ≈ 0.618 \displaystyle\frac{\sqrt{5}-1}{2}≈0.618 25−1≈0.618…按此比例设计的造型特别美丽,被称为黄金分割。这个数值不仅体现在诸如绘画、雕塑、音乐、建筑等艺术领域,也在管理、工程设计等方面有重要的应用,在日常生活中的应用也比比皆是。
二、寻找完美数
(一)编程思路
-
理解完美数与梅森素数的关系:完美数是形式为 2 p − 1 ( 2 p − 1 ) 2^{p-1}(2^p - 1) 2p−1(2p−1)的数,其中 2 p − 1 2^p - 1 2p−1必须是梅森素数。
-
实现Lucas-Lehmer素性测试:这是检测梅森素数的一种有效方法。对于每个 p p p,计算序列直到 p − 2 p-2 p−2项,如果最终结果为 0 0 0,则 2 p − 1 2^p - 1 2p−1是素数。
-
寻找梅森素数:从 p = 2 p=2 p=2开始,对每个 p p p调用
lucasLehmerPrime
函数,检查 2 p − 1 2^p - 1 2p−1是否为素数。 -
计算并输出完美数:一旦找到梅森素数,根据完美数的公式计算相应的完美数,并输出结果。
-
设置搜索限制:程序将持续寻找并输出完美数,直到找到大于预设限制的数为止。
-
优化与考虑:对于大数计算,使用
BigInteger
类处理可能的溢出问题。同时,考虑到计算量可能非常大,实际应用中可能需要进一步优化算法或使用并行计算。 -
代码实现:将上述思路转化为Java代码,使用
BigInteger
类进行大数运算,实现完美数的搜索程序。
(二)编写程序
- 在
net.huawei.number
包里创建PerfectNumberFinder
类
package net.huawei.number;import java.math.BigInteger;/*** 功能:完美数寻找器* 作者:华卫* 日期:2024年07月09日*/
public class PerfectNumberFinder {public static void main(String[] args) {// 设置寻找完美数的上限findPerfectNumbers(new BigInteger("1000000000000000000000000000000000000000000000000000000000000000000000000000"));}/*** 执行Lucas-Lehmer素性测试来检查2^p - 1是否为梅森素数。** @param p 用于计算2^p - 1的指数* @return 如果2^p - 1是素数,则返回true,否则返回false*/public static boolean lucasLehmerPrime(int p) {if (p == 2) {return true; // 2^2 - 1是最小的梅森素数}BigInteger s = BigInteger.valueOf(4); // 初始值BigInteger M = BigInteger.ONE.shiftLeft(p).subtract(BigInteger.ONE); // 计算2^p - 1for (int i = 0; i < p - 2; i++) {// 应用Lucas-Lehmer迭代过程s = s.multiply(s).subtract(BigInteger.valueOf(2)).mod(M);}return s.equals(BigInteger.ZERO); // 如果s为0,则2^p - 1是素数}/*** 寻找并打印所有小于给定限制的完美数** @param limit 完美数搜索的上限值*/public static void findPerfectNumbers(BigInteger limit) {int p = 2; // 从最小的梅森素数候选指数开始int count = 0;while (true) {if (lucasLehmerPrime(p)) {// 如果找到梅森素数,计算相应的完美数BigInteger mersennePrime = BigInteger.ONE.shiftLeft(p).subtract(BigInteger.ONE);BigInteger perfectNumber = BigInteger.ONE.shiftLeft(p - 1).multiply(mersennePrime);// 统计找到的完美数数量count++;// 打印梅森素数和对应的完美数System.out.println("梅森素数: " + mersennePrime);System.out.println("完 美 数: " + perfectNumber);// 如果完美数大于给定限制,则停止搜索if (perfectNumber.compareTo(limit) > 0) {break;}}p++; // 移动到下一个候选指数}System.out.println("找到" + count + "个完美数~");}
}
(三)运行程序
- 查看结果,在指定范围内找到12个完美数
三、实战小结
- 通过编写和运行完美数寻找器程序,我们深入理解了完美数与梅森素数的内在联系,体验了大数计算的挑战,并认识到了算法优化的重要性。此过程不仅锻炼了编程技能,还激发了我们对数论奥秘的探索兴趣。尽管寻找大完美数极具难度,但使用
BigInteger
类和Lucas-Lehmer测试,我们能够有效地识别梅森素数,进而发现新的完美数。