[Fortran]FMLIBを用いた多倍長での分割数p(n)の計算
FMLIBを用いて多倍長計算を行い、整数の分割数p(n)を計算しました。10**5まで計算して、10000毎の値を出力しています。
ところで分割数に関しては、ラマヌジャンの関係式 p(5n+4) ≡ 0 mod 5、 p(7n+5) ≡ 0 mod 7、 p(11n+6) ≡ 0 mod 11 などが知られていますが、これを確かめてみることもやってみました。
すると10万までの範囲で
p(5^2n+24) ≡ 0 mod 5 p(5^3n+124) ≡ 0 mod 5^3, p(5^3n+99) ≡ 0 mod 5^3, p(5^3n+74) ≡ 0 mod 5^3 p(5^4n+599) ≡ 0 mod 5^4 p(5^5n+3099) ≡ 0 mod 5^5, p(5^5n+2474) ≡ 0 mod 5^5, p(5^5n+1849) ≡ 0 mod 5^5 p(5^6n+14974) ≡ 0 mod 5^6 p(7^2n+47) ≡ 0 mod 7^2, p(7^2n+40) ≡ 0 mod 7^2, p(7^2n+33) ≡ 0 mod 7^2, p(7^2n+19) ≡ 0 mod 7^2 p(11^2n+116) ≡ 0 mod 11^2 p(11^3n+721) ≡ 0 mod 11^3 p(11^4n+14031) ≡ 0 mod 11^4 p(5*7n+19) ≡ 0 mod 5*7 p(5*11n+39) ≡ 0 mod 5*11 p(7*11n+61) ≡ 0 mod 7*11 p(5*7*11n+369) ≡ 0 mod 5*7*11
等の関係式が成り立つことが確認できました。 なお、p(13n+m) の形は n<5 で成り立ちませんでした。また p(7^n+m) の形も n>2 では成り立たないようでした。
(H28.7.19 追記) Andrews の本によれば、7 のべき乗の場合は、7n に対して、mod 7^{(n+2)/2} となるそうです。n が奇数で割り切れない場合は切り捨てになるようです。
これらの式の証明は難しいのか初等的な本には簡単な場合の結果のみ記されていて、証明は記されていないのが普通です。近年、一般的な場合についての証明がされたらしいです。
追記：Hardy & Wright の数論入門 II に、簡単な場合の初等的証明がのっています。
ソース・プログラム
program test use FMZM implicit none integer, parameter :: ki = 8, kd = 16 integer, parameter :: np = 100000 integer(ki) :: i, j, k, kk type(im) :: m, mp(0:np), isgn character (1000) :: str mp(0) = to_im(1) do i = 1, np mp(i) = to_fm(0) isgn = 1 do j = 1, i k = i - j * ( 3 * j - 1) / 2 if ( k < 0 ) exit isgn = -isgn mp(i) = mp(i) - isgn * mp(k) end do isgn = 1 do j = 1, i k = i - j * ( 3 * j + 1) / 2 if ( k < 0 ) exit isgn = -isgn mp(i) = mp(i) - isgn * mp(k) end do if (mod(i, 10000) == 0) then call im_form('i1000', mp(i), str) write(*, '(a, i0, a, a)') 'p(', i, ')=', trim(adjustl(str)) end if end do stop end program test
実行結果
p(10000)=36167251325636293988820471890953695495016030339315650422081868605887952 568754066420592310556052906916435144 p(20000)=25211481381252969791661953323047045228132894960181159343685031410803428 44238015649566239707316898243691923247893519949030164118262305781667359592421130 97 p(30000)=42963584246325385174883157483005920912690248645401139066014480612764163 98621545818519299017331483217956421136722885532171801507449059809546972778418225 4987592569621576375743614022636192786 p(40000)=22807728274470728289340571240816959704646220378351611859439499408672657 82859054809370333001460500055412704256641231606173277168374068805126423747889386 9163586426487354600342477491620506603389595232890082673857997469797 p(50000)=36261860971416678445921408915956337281653830825277850490158727554141099 04256712082718122747316610565824630881772910217544261659239432670671532413858378 25618898733387712189158660795738975053844747471259297926371901246185871979162730 2489739548263 p(60000)=18018253822448169261804432800866044525454076287275317362509459435892806 25931784291878718926261747615099259834603843663102619608058253939417980970528696 40358534859725629820925337685243020834914794583507052832910065238613281226718926 2695338830922864518234313575586067751 p(70000)=11285798434044003214522323164974878820150546809512759036709574025595615 68213766726171558325948431574335460211655204512980264007025018090090264811039269 07012395305351100817336318973887000780327643402300239959081264584355424006955464 36739960930879459778742266723702470966943462554992479593773 p(80000)=22122317540323608851556871068806330055355496441209823522680555978502136 75192321350635052767170860436882327557325584663117174625842745778072057916541693 77642086708633913816353451601383896290009265556219970469439713533274332579380213 0314543501641455234756154862549293510444938661660293373217832816485579800085553 p(90000)=25531914643644807485539288265406423832074306757337214551552407720933333 23375417801607903581499186888830859880057185761395140934411286100661043770339969 53618200720834085531193732376137962592509081335368027573068447457235188677627803 43042085994980022567212953415383327807215845987770010290502385013470332572495580 563255768162567269 p(100000)=2749351056977569651267751632098635268817342931598005475820312598430214 73281149641730550507416607366215901578447742962489404930630702004617927644930335 10116079342457190155718943509725312466108452006369558934464248716828789832182345 00926285383140459702130713067451062441922731123899970228440860937093553162969785 1569569892196108480158600569421098519
