Just My Life & My Work

[C++] 奇數的完美數 (Odd Perfect Number)

2011 年 04 月 05 日

這是計算理論Halting Problem的例子，想要找出奇數的完美數，使得此程式可以停下來。

我們知道完美數的定義是：n=其因數之和，例子如：

6=1+2+3
28=1+2+4+7+14
496=1+2+4+8+16+31+62+124+248
…

定理：若2^m-1是質數，則2^(m-1)(2^m-1)必為完美數。
因為2^(m-1)必為偶數，而2^m-1質數有無窮多個，因此偶數的完美數有無窮多個。但是是否存在奇數的完美數？依然是個Open Question！目前已知10^300以內沒有，已經在1991年證出，最新數據為10^1500內沒有，但沒有被發表。可以參考WiKi的Perfect number。

先來看[1,10000]有幾個完美數，程式碼如下：

/**
	Theme: Odd Perfect Number
	Compiler: Dev C++ 4.9.9.2
	Date: 100/04/16
	Author: ShengWen
	Blog: https://cg2010studio.wordpress.com/
*/
#include<iostream>
using namespace std;
const int NUMBER=10000;
int main(){
	int sum;
	for(int n=1; n<NUMBER;n++){
		sum=0;
		for(int i=1; i<n; i++){
			if(n%i==0)
				sum+=i;
		}
		if(n==sum)
			cout<<n<<endl;
	}
	system("pause");
	return EXIT_SUCCESS;
}

執行結果：

6
28
496
8128
請按任意鍵繼續 . . .

直接拿定理來找完美數：2^(m-1)(2^m-1)

6=2^(2-1)*(2^2-1), m=2
28=2^(3-1)*(2^3-1), m=3
496=2^(5-1)*(2^5-1), m=5
8128=2^(7-1)*(2^7-1), m=7
33550336=2^(13-1)*(2^13-1), m=13

很神奇地把它轉為2進位數：左邊m個1，右邊m-1個0

6(10) = 110(2)
28(10) = 11100(2)
496(10) = 111110000(2)
8128(10) = 1111111000000(2)
33550336(10) = 1111111111111000000000000(2)

若想找[1,10000]奇數的完美數是否存在，只要把n++改為n+=2即可！

分類：

計算理論, 課業

發表留言

隨意留個言吧：）～

這個網站採用 Akismet 服務減少垃圾留言。進一步了解 Akismet 如何處理網站訪客的留言資料。

標籤雲