親和數的數值算法和數量估計

徐明毅

（武漢大學水利水電學院，湖北武漢430072）

親和數的數值算法和數量估計

徐明毅

（武漢大學水利水電學院，湖北武漢430072）

總結了搜尋親和數的分解算法和遞推算法，計算出1 000億內的親和數3 261對，根據數值結果給出了在一定范圍內親和數的數量估計式，得出1018內的親和數約為百萬對。

數論；素因數；親和數

一個正整數z的所有因數之和，包括1和該數本身，記為σ(z)。親和數為不包含本身的其它所有因數之和等于另一個數的一對數，即對于數p，q，如果σ(p)-p=q，σ(q)-q=p，或者σ(p)=p+q=σ(q)，則p，q為一對親和數。如果p=q，則稱為完全數［1］。最小的一對親和數為220和284，是由古希臘的畢達哥拉斯學派提出的［2］，后來直到1636年，法國數學家費馬給出第二對親和數17 296和18 416，而數學家歐拉曾找出59對新的親和數。在計算機出現后，人們加快了親和數的尋找。文獻［3］計算出90億以下的親和數1 360對，文獻［4］和文獻［5］又找到了更大一些的親和數。另外，也有學者提出了判別一些特定的數不構成親和數對［6］，或尋找一些特別的親和數對［7-8］的理論公式，但離完全解決親和數問題尚有距離。在總結親和數的基本定理基礎上，采用數值方法計算了1 000億內的親和數，并根據數值計算結果，給出了一定范圍內親和數的數量估計方法。

1 親和數的基本定理

其中：a，b，c為素數；m，n，l為大于或等于1的正整數。

1.1 素數冪的全因數和

對于素數a，因數只有1和它本身，因此全部因子和為σ(a)=1+a，因此素數不可能構成親和數對。如果某數分解為m個a的乘積，其中a為素數，可以通過組合得到所有的因數。任選出其中的一個，因數為a，任選出其中的兩個，因數為a2，以此類推，因此，包括因數1和該數本身am，所有的因數之和為

對任一個正整數z，因數分解后可以表達為以下的形式

該式退化形式對于素數同樣成立，此時退化為m=1，σ(a)=1+a。特殊地，當a=2時，σ(2m)=2m+1-1=2?2m-1，對小的素數可通過查表方法加速計算。

該表達式在計算機求解時，有m次乘法和1次除法，如果先完成乘法，就是求出一個大數再除以一個數，大數可能超界，限制了使用范圍。如果直接用迭代法計算，則沒有此顧慮。迭代格式為

考慮到不需計算m=0的情況，于是可用代碼表示為：int s=a+1；while（--m）s=a*s+1；這樣對于素數，不需要進入循環增加一次乘法。

1.2 多因數的全因數和

先考慮素數分解后，只有兩個互相獨立的素數：z=a?b，此時的因子有1，a，b，a?b，全部因數和為

其實，只要是獨立的兩個因子，都可以表示為以上的形式。設z=x?y，x和y為互相獨立的兩個數，不管是素數還是合數，即它們的因數沒有重合的部分。于是，考慮組合的情況，只有x部分的組合為全因數和減去1，為σ(x)-1；只有y部分的組合為σ(y)-1，考慮兩者的相互組合為[σ(x)-1][σ(y)-1]，于是總的全因數和為

因此，可以逐次分解直到求最后的素數冪的全因數和。例如3個素數的乘積：z=a?b?c，用組合方法可知所有因子為：1，a，b，c，a?b，b?c，a?c，a?b?c，用逐步分解的方法也同樣得到全因數和這樣，分解素因子后，求全因數和比較簡單，比直接組合的方式要簡便很多。

2 判斷親和數的分解算法

由以上親和數的基本定理，可得到判斷親和數的主要步驟為

1）分解某數的素因子，并統計出每個素因子的個數，即得到每個素因子的冪次。

2）通過公式求出該數的全因數和，再減去本身，就得到可能的親和數對的另一個數。

3）對另一個數同樣進行計算，如果重新得到原來的數，則構成親和數對，否則重新搜索。

其中較為困難的部分為分解素因數，考慮采用簡單的方法。先準備素數表，如果搜索范圍到n，則素數表的范圍只需到n即可。然后從小到大依次測試素因數，如果測試出一個素因子，就記錄下來，然后原數除以該因子，剩余的部分再繼續判斷素因子。在計算時，對小的素因子只要能夠整除，就一直提取到沒有該素因子為止，這樣剩余部分就不用從素數表的開頭進行判斷，而是直接往后判斷是否有更大的素因子，提高計算效率。

以下用代碼表示素因子的提取過程，假設素數表用數組reserve［］表示，某數的獨立的素因子用數組childs［］保存，對應的素因子的階次用數組rank［］表示，代碼如下：

分解算法中，主要的計算量為素因子分解。在從某數得到可能的另一個親和數時，如果更小，則顯然已搜索過，為避免重復計算和記錄，就直接跳過，減少了計算量。

現在主要估算分解過程所需的計算量。由以上素因子分解算法，分解正數數x的素因子最多需對該范圍內的ρx個素數依次進行求余測試，因此對該范圍內所有正整數的素因子分解的測試總數為

式中：C(x)為總的求余次數；ρ為該范圍內的平均素數密度。

3 判斷親和數的遞推算法

在小范圍搜索時，上述的分解算法并不是最快的。因為要用除法來分解出素因子，也要用乘法來求出全因數和。其實，可以從因數的原始定義出發，可以將乘除法計算變換為加法計算。因為一個數的所有倍數對應的數都有該數為因子，因此將該因子計入因數和，逐步累加多個因子就可得到所有因數和。算法就轉換為找出具有某因數的所有數的位置，然后不斷累加因數就可以了。

開辟一個連續的數組來表示某數的真因數和，即全因數和減去某數本身。首先1是所有數的因數，故所有數都計入該因數，初始化為1。然后從2開始的每一個可能的真因數，在它的倍數位置加上該數，而不是它倍數的位置就不用累加該數，那么在循環結束之后，就得到該位置對應數的真因數和，其中為1的就是素數，因為沒有除1以外的小于它的任一因數。然后再對數組只需要一次遍歷就可以輕松找到該范圍內所有的親和數了。假設數組為sum［］，長度為len，初始的位置為ini，列出求真因數和的代碼如下：

然后掃描一遍數組，只要某數的真因數和在該區段內就可判斷了，代碼如下：

可以看到，因為問題的特殊性，方便和巧妙地利用了下標作為伴隨數組，用數組空間來節約計算時間。同時將回溯的思想轉換成遞推的思想，分解算法的乘除操作大部分轉化為累加操作，因此加快了計算速度。

遞推算法中的主要計算量為求真因數和的累加過程，如對于因數1，累加次數為x，對于因數2，累加次數為x/2，以此類推，總的累加次數為：

式中：D(x)為正整數x范圍內總的求和次數，r為調和級數的歐拉常數項，約為0.577 2。

實際計算中，如果范圍超過劃定的區段容量，則可將得到的真因數和保留到一個緩沖數組中，這樣超出區段的數同樣可以查詢判斷是否是親和數。緩沖區越大，能夠增加的搜索范圍越大，一般能增加十倍范圍以上。但范圍更大時，暫時不能判斷是否親和的數將溢出緩沖區，這時就必須結合分解算法，將緩沖區清空一部分，再進行下一個區段的搜索。

判斷親和數的遞推算法在小范圍搜索時十分有效，但在搜索空間擴大后，效率下降，此時反而是采用分解算法更有效了，兩者效率相當時的搜索范圍與使用的內存空間大小和具體的算法有關，必須通過實際的數值實驗才能確定。

4 大整數的定義方法

為表示較大的數據范圍，需要采用64位二進制整數。在VC++中，int是4字節整數，而__int64（前面為2個下橫線）是8字節整數。如果是較新的版本，符合C99標準的話，也可以用long long來表示8字節整數。為便于使用，可以用條件定義語句：typedef__int64 xint；于是用重定義類型xint來表示64位二進制整數。輸入采用scanf（“%I64d”，&n）來讀入一個數，輸出用printf（“%I64d”，n），如果是64位無符號整數，格式字符串為%I64u。如果要表示更大的整數范圍，C/C++編譯器不能直接支持，必須用自定義的方法來處理。

在編譯為32位程序還是64位程序時，以上的數據定義格式都不用變化，只有表示地址的指針大小會自動更改。32位程序中，指針用4字節表示，而在64位程序中，指針用8字節表示。由于在64位系統中運行64位程序更快，并且可以分配更大的內存，這時只需要選擇目標運行平臺為x64即可。如在vs2008中，建立項目后，用快捷建“alt+f7”配置項目屬性，在對話框中點擊“配置管理器”，在彈出對話框中“活動解決方案平臺”欄下選擇“＜新建…＞”，再選擇x64平臺即可。但在一些精簡版本的編譯器中可能沒有該選項，使用時要注意。

5 親和數的分布估計

親和數是較為稀少的，但現在還不能確定親和數對的數量是否有限。在搜尋出的親和數對中，均同為偶數或奇數，還沒有一奇一偶的情況，但這是否是普遍規律，還未見證明［2］。使用較為快速的遞推算法，已計算得到1 000億內的所有親和數對，數量統計如表1所示。

表1 1 000億內親和數的數目統計Tab.1 Statistics of amicable numbers within one hundred billion

式中：n(x)為正整數x范圍內的親和數對的數目；x0為已知親和數對的正整數范圍；a為增長比例，從當前成果看似乎應介于2和3之間，其是否隨范圍增大會趨于一個定值，還需要更多的計算支持或從理論上加以證明。

另外，采用分解算法，尋找到1萬億以上的5對親和數：（1 000 452 085 744，1 023 608 366 096），（1 000 539 285 525，1 015 331 690 475），（1 000 607 505 404，1 147 934 333 956），（1 001 352 481 250，1 117 674 392 350），（1 001 583 011 750，1 019 368 284 250），可見在該范圍內，平均約搜索3億個數才發現一對親和數。

從計算結果可以看出，親和數的分布有較好的規律性，在搜索范圍增加為原來的10倍時，親和數對的數量為原來的2倍多，隨著范圍增大，親和數越稀少，搜索也越困難。假設增長比率為a，按a=2.3計算，以1億為計算起點，則100億億（1018）內的親和數對估計為231×2.310=956 952；以100億為計算起點，則估計為1 391×2.38=1 089 305，差別不大，估計為100萬對左右。在該搜索范圍內平均萬億個數才能找到一對親和數，可用“沙里淘金”來形容尋找難度。歸納得到在正整數x內親和數的數量為：

6 結語

親和數是數學中的有趣問題，本文給出了搜尋親和數的分解算法和遞推算法，并得到1 000億內的所有親和數。分析計算結果得出，親和數隨范圍增大愈加稀疏，相鄰親和數對之間相距越來越遠，估計1018內的親和數約100萬對。

[1]華羅庚.數論導引[M].北京:科學出版社,1979.

[2]徐品方.尋找親和數的艱辛歲月[J].數學通報,1999(6):37-38.

[3]周尚超.親和數[J].華東交通大學學報,1998(4):67-68.

[4]周尚超,劉二根,鄧毅雄,等.15對親和數[J].華東交通大學學報,1999,26(3):66-67.

[5]周尚超,劉二根,鄧毅雄,等.親和數的若干性質與10對親和數[J],華東交通大學學報,2000,27(3):68-70.

[6]沈忠華.關于親和數的一個結果[J].哈爾濱師范大學自然科學學報,2001(5):15-19.

[7]鄧淙.探求親和數的一種方法[J].昭通師專學報,1984(1):10-13.

[8]向紅軍,楊吉清.親和數的一種求法[J].湖南理工學院學報:自然科學版,2009(3):14-15.

Numeric Algorithm and Magnitude Estimation of Amicable Numbers

Xu Mingyi
(School of Water Resources and Hydropower Engineering,Wuhan University,Wuhan 430072,China)

This paper proposes the decomposition algorithm and recursive algorithm to search amicable numbers.3 261 pairs of amicable numbers are searched out within 100 billion.The numerical estimated expression of amica?ble numbers in a certain range is obtained according to numeric results.There are approximately onemillion ami?cable numbers in 1018range.

number theory;prime factor;amicable number

O157.1

A

2014-05-30

徐明毅（1973—），男，副教授，主要研究方向為水工結構數值模擬。

1005-0523（2014）04-0054-05