親和數(shù)的數(shù)值算法和數(shù)量估計

徐明毅

（武漢大學(xué)水利水電學(xué)院，湖北武漢430072）

親和數(shù)的數(shù)值算法和數(shù)量估計

徐明毅

（武漢大學(xué)水利水電學(xué)院，湖北武漢430072）

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

數(shù)論；素因數(shù)；親和數(shù)

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

1 親和數(shù)的基本定理

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

1.1 素數(shù)冪的全因數(shù)和

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

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

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

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

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

1.2 多因數(shù)的全因數(shù)和

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

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

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

2 判斷親和數(shù)的分解算法

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

1）分解某數(shù)的素因子，并統(tǒng)計出每個素因子的個數(shù)，即得到每個素因子的冪次。

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

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

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

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

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

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

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

3 判斷親和數(shù)的遞推算法

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

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

然后掃描一遍數(shù)組，只要某數(shù)的真因數(shù)和在該區(qū)段內(nèi)就可判斷了，代碼如下：

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

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

式中：D(x)為正整數(shù)x范圍內(nèi)總的求和次數(shù)，r為調(diào)和級數(shù)的歐拉常數(shù)項，約為0.577 2。

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

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

4 大整數(shù)的定義方法

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

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

5 親和數(shù)的分布估計

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

表1 1 000億內(nèi)親和數(shù)的數(shù)目統(tǒng)計Tab.1 Statistics of amicable numbers within one hundred billion

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

另外，采用分解算法，尋找到1萬億以上的5對親和數(shù)：（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），可見在該范圍內(nèi)，平均約搜索3億個數(shù)才發(fā)現(xiàn)一對親和數(shù)。

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

6 結(jié)語

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

[1]華羅庚.數(shù)論導(dǎo)引[M].北京:科學(xué)出版社,1979.

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

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

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

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

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

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

[8]向紅軍,楊吉清.親和數(shù)的一種求法[J].湖南理工學(xué)院學(xué)報:自然科學(xué)版,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—），男，副教授，主要研究方向為水工結(jié)構(gòu)數(shù)值模擬。

1005-0523（2014）04-0054-05