求完美数

简介: 一个数如果恰好等于它的因子之和,这个数就称为"完美数"或"完数"。例如6=1+2+3.(6的因子是1,2,3) 完美数的一些性质: 欧几里德证明了:一个偶数是完数,当且仅当它具有如下形式:2(p-1)×(2p-1) 其中p和(2p-1)是素数。 尽管没有发现奇完数,但是当代数学家奥斯丁·欧尔(Oystein Ore)证明,若有奇完全数,则其形状必然是12p+1或36p+9的形式,其中p是素

一个数如果恰好等于它的因子之和,这个数就称为"完美数"或"完数"。例如6=1+2+3.(6的因子是1,2,3) 完美数的一些性质:

  1. 欧几里德证明了:一个偶数是完数,当且仅当它具有如下形式:2(p-1)×(2p-1) 其中p和(2p-1)是素数。 尽管没有发现奇完数,但是当代数学家奥斯丁·欧尔(Oystein Ore)证明,若有奇完全数,则其形状必然是12p+1或36p+9的形式,其中p是素数。在1018以下的自然数中奇完数是不存在的。
  2. 除6以外的偶完数,把它的各位数字相加,直到变成一位数,那么这个一位数一定是1(亦即:除6以外的完数,被9除都余1) 28:2+8=10,1+0=1 496:4+9+6=19,1+9=10,1+0=1
  3. 因为 2p 是 2的幂,用C语言也就是1 << p,那么 2p-1 的二进制也就是p个1组成了,而 2(p-1) 是 2的幂,这两个数相乘,也就相当于把 2p-1 向左移 p-1 位,即 (2p-1) << (p-1),那所有完美数的二进制就是前面p个1,后面跟着p-1个0。 所以偶完数都可以表达为2的一些连续正整数次幂之和,如: 6=2(1 ) +   2(2 ) 28=2(2  ) +   2(3)   +   2(4) 8128=2(6)   +   2(7)   +   ...   +   2(12) 33550336=2(12)   +   2(13 )  +   ...   +   2(24)
    j = ((1 + (i ^ (i-1) )) >> 1) + i - 1;
    (j & (j + 1)) || (i & 1)
    上面的代码可以判断整数i是否是前面1后面0的形式。
  4. 每一个偶完数都可以写成连续自然数之和: 6=1+2+3 28=1+2+3+4+5+6+7 496=1+2+3+…+30+31
  5. 除6以外的偶完数,还可以表示成连续奇数的立方和(被加的项共有): 28 = 1(3) + 3(3) 496 = 1(3) + 3(3) + 5(3) + 7(3) 8128 = 1(3) + 3(3) + 5(3) + ... + 15(3) 33550336 = 1(3) + 3(3) + 5(3) + ... + 125(3) + 127(3)
  6. 每一个完数的所有约数(包括本身)的倒数之和,都等于2: 1/1 + 1/2 + 1/3 + 1/6 = 2 1/1 + 1/2 + 1/4 + 1/7 + 1/14 + 1/28 = 2

了解了上面一些性质后,就可以简单的来写一个求完美数的程序了。

#include <stdio.h>

#ifndef WIN32
typedef long long ll;
#else
typedef __int64 ll;
#endif

int main(void)
{
	ll i, j, n, x;

	for (n = 2; n <= 31; n++)
	{
		x = (1 << n) - 1;
		for(i = 3; i*i <= x; i += 2)
			if(x % i == 0)
				break;
		if(i*i <= x) continue;
		printf("%lld/n", (1 << (n - 1)) * x);
	}

	return 0;
}

运行结果:

6
28
496
8128
33550336
8589869056
137438691328
2305843008139952128

到目前为止,已经求出的2p-1是素数的有25个:2、3、5、7、13、17、19、31、61、89、107、127、521、607、1279、2203、2281、3217、4253、4423、9689、9941、11213、19937、21701。 据说最后一个即221701-1是1978年两名美国大学生新发现的截止目前为止最大的一个素数 所有我们可以利用这个结果来求已知的完美数:

import java.math.BigInteger;

public class Main
{
	public static void main(String[] argv)
	{
		int [] prime = {
			2,3,5,7,13,17,19,31,61,	89,107,127,
			521,607,1279,2203,2281,3217,4253,
			4423,9689,9941,11213,19937,21701
		};
		BigInteger x = BigInteger.ONE;
		for (int i = 0; i < prime.length; i++)
			System.out.println(x.shiftLeft(prime[i]-1).multiply(x.shiftLeft(prime[i]).subtract(x)));
	}
}

最后一个完美数的长度是13066!堪称是BinIntegest


版权声明

本人的所有原创文章皆保留版权,请尊重原创作品。
转载必须包含本声明,保持本文完整,并以超链接形式注明原始作者“redraiment”和主站点上的本文原始地址。

联系方式

我的邮箱,欢迎来信(redraiment@gmail.com
我的Blogger(子清行
我的Google Sites(子清行
我的CSDN博客(梦婷轩
我的百度空间(梦婷轩

目录
相关文章
|
Kubernetes 安全 Docker
如何在 K8S 集群范围使用 imagePullSecret?
如何在 K8S 集群范围使用 imagePullSecret?
|
前端开发 JavaScript C++
QML信号与信号槽实践指南:轻松掌握现代软件开发的关键技术(一)
QML信号与信号槽实践指南:轻松掌握现代软件开发的关键技术
632 0
|
IDE 安全 数据管理
Visual Basic for Applications (VBA):自动化Office任务
【4月更文挑战第27天】**Visual Basic for Applications (VBA)** 是Microsoft Office中的宏语言,用于自动化Excel、Word、Outlook等应用的任务。VBA基于Visual Basic,通过编写代码控制应用行为,提升效率。文章介绍了VBA环境、基础语法,展示了在Excel(数据处理)、Word(文档管理)和Outlook(邮件自动化)中的应用。强调安全性和调试重要性,学习VBA能增强Office软件的功能,实现高效自动化工作流程。
446 0
|
9月前
|
存储 监控 关系型数据库
深入解析 Hologres Table Group 与 Shard Count
Hologres 是一款强大的实时数仓,支持海量数据的高效存储与快速查询。Table Group 和 Shard Count 是其核心概念,前者管理数据分片,后者指定分片数量。合理配置二者可显著提升性能。Table Group 实现资源共享与协同管理,Shard Count 根据数据量和读写模式优化分片,确保高效处理。结合业务需求进行动态调整,可充分发挥 Hologres 的潜力,助力企业数字化转型。
318 60
|
存储 消息中间件 druid
大数据-150 Apache Druid 安装部署 单机启动 系统架构
大数据-150 Apache Druid 安装部署 单机启动 系统架构
163 1
|
存储 Kubernetes 持续交付
深入浅出 Kubernetes:掌握容器编排的艺术
Kubernetes作为容器编排领域的领头羊,提供了运行分布式系统的强大框架,支持自动化部署、扩展和管理容器化应用。本文深入浅出地介绍了Kubernetes的核心概念与关键组件,包括服务发现、存储编排及自动部署等特性。通过Minikube、kubeadm及云服务商等多种方式部署集群,并使用`kubectl`、YAML配置文件和Helm进行资源管理。掌握Kubernetes将成为软件开发者的宝贵技能。
|
消息中间件 Prometheus 监控
Producer的监控与日志记录最佳实践
【8月更文第29天】在分布式系统中,消息队列作为关键组件之一,其稳定性和性能至关重要。生产者(Producer)负责生成并发送消息到消息队列中,因此确保生产者的健康运行是非常重要的。本文将探讨如何为生产者设置监控和日志记录,以跟踪其健康状况和性能指标。
218 0
|
数据采集 机器学习/深度学习 数据挖掘
使用Python进行数据预处理与清洗的最佳实践
本文探讨了Python在数据预处理和清洗中的关键作用。预处理包括数据收集、整合、探索、转换和标准化,而清洗则涉及缺失值、重复值、异常值的处理及数据格式转换。文中提供了使用pandas库进行数据读取、缺失值(如用平均值填充)和重复值处理、异常值检测(如IQR法则)以及数据转换(如min-max缩放)的代码示例。此外,还讲解了文本数据清洗的基本步骤,包括去除标点、转换为小写和停用词移除。整体上,文章旨在帮助读者掌握数据预处理和清洗的最佳实践,以提高数据分析的准确性和效率。
1976 2
|
SQL XML Java
【MyBatis】 MyBatis框架下的高效数据操作:深入理解增删查改(CRUD)
【MyBatis】 MyBatis框架下的高效数据操作:深入理解增删查改(CRUD)
170 1