fortran66のブログ

fortran について書きます。

10万までの分割数

[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