五角数

J.H. コンウェイ,‎ R.K. ガイの「数の本」を眺めていたら、五角数の簡単な求め方が載っていたので（第4章）、それを確かめてみたいと思います。
https://www.amazon.co.jp/dp/4621062077

その求め方とは、三角数を 3 で割って割り切れたらその商をとり、割り切れなかったら 0 とすれば五角数が出てくるというものです。ここで三角数は $\triangle(k)=k(k+1)/2$ です。

以前に五角数を使った漸化式による分割数の計算を行いましたが、この時は五角数の一般式 $\mathrm{penta}(k) = k(3k-1) / 2$ を用いました。この時は、負数に対する五角数を用いなければなりませんでしたが、今回のコンウェイ等のやり方に従えば、その辺もよろしく出てくるようになっております。
http://oomorigohan.tumblr.com/post/87116264321

ここで分割数とは整数を和の形に分解するやり方を数えたものです。例えば 4 の分割数は 4 = 3+1 = 2+2 = 2+1+1 = 1+1+1+1 の 5 通りの分割方法があるので 5 となります。整数を積に分解する素因数分解に対して、和の要素分解になっています。

ソース・プログラム

1 まず自然数列を用意します。
2 次に scan 的に和を蓄積してゆきます。すると三角数が求まります。
3 求まった三角数を三で割り、割り切れたら商を、余りが出たら 0 を代入します。五角数が求まります。
4 $p(n)=p(n−1)+p(n−2)−p(n−5)−p(n−7)+p(n−12)+p(n−15)+\cdots$ の漸化式で分割数を求めます。（但しここでの都合上 p(0) = 1 とおきます。）

Fortran は順序・無順序の区別がはっきりしているので、漸化式のように順序が本質的なものは do loop で、順序によらないものは無順序な配列演算命令で処理するようにしました。

    program test
      implicit none
      integer, parameter :: ki = selected_int_kind(10)
      integer, parameter :: n = 35
      integer(ki) :: i, mp(n)
      forall(i = 1:n) mp(i) = i
      print *, 'natural numbers'
      print *, mp
      !
      do i = 2, n
        mp(i) = mp(i) + mp(i-1)  
      end do    
      print *, 'triangular numbers'
      print *, mp
      !
      where( mod(mp, 3) == 0 )
        mp = mp / 3
      elsewhere
        mp = 0
      end where
      print *, 'pentagonal numbers'
      print *, mp
      !
      ! partition numbers
      !
      block 
        integer(ki) :: ii(n)  
        integer(ki), allocatable :: ip(:), np(:)
        allocate( ip(maxval(mp)), np(0:maxval(mp)) )
        ii = 0 
        forall(i = 2:n:6) ii(i) = +1
        forall(i = 3:n:6) ii(i) = +1
        forall(i = 5:n:6) ii(i) = -1
        forall(i = 6:n:6) ii(i) = -1
        ip = 0
        where(mp /= 0) ip(mp) = ii
        ! partition 
        np(0) = 1
        do i = 1, ubound(np, 1)
          np(i) = sum(np(i - 1:0:-1) * ip(:))  
        end do  
        print *, 'partition numbers'
        print '(5(2i15/))', transpose(reshape([(i, i = 0, ubound(np, 1)), np], [size(np), 2]))
      end block  
    end program test

実行結果

はじめに 35 までの自然数、次に 35 までの三角数、それに対応する五角数を出力しています。

後半は、Format を駆使して１行でzip 的に分割数を 5 個毎に出力しています。5n+4 番目の分割数は、5 の倍数になっていることが見て取れます（ $p(5n+4)\equiv0 \mod 5$）。

natural numbers
                    1                     2                     3
                    4                     5                     6
                    7                     8                     9
                   10                    11                    12
                   13                    14                    15
                   16                    17                    18
                   19                    20                    21
                   22                    23                    24
                   25                    26                    27
                   28                    29                    30
                   31                    32                    33
                   34                    35
triangular numbers
                    1                     3                     6
                   10                    15                    21
                   28                    36                    45
                   55                    66                    78
                   91                   105                   120
                  136                   153                   171
                  190                   210                   231
                  253                   276                   300
                  325                   351                   378
                  406                   435                   465
                  496                   528                   561
                  595                   630
pentagonal numbers
                    0                     1                     2
                    0                     5                     7
                    0                    12                    15
                    0                    22                    26
                    0                    35                    40
                    0                    51                    57
                    0                    70                    77
                    0                    92                   100
                    0                   117                   126
                    0                   145                   155
                    0                   176                   187
                    0                   210
partition numbers
             0              1
             1              1
             2              2
             3              3
             4              5

             5              7
             6             11
             7             15
             8             22
             9             30

            10             42
            11             56
            12             77
            13            101
            14            135

            15            176
            16            231
            17            297
            18            385
            19            490

            20            627
            21            792
            22           1002
            23           1255
            24           1575

            25           1958
            26           2436
            27           3010
            28           3718
            29           4565

            30           5604
            31           6842
            32           8349
            33          10143
            34          12310

            35          14883
            36          17977
            37          21637
            38          26015
            39          31185

            40          37338
            41          44583
            42          53174
            43          63261
            44          75175

            45          89134
            46         105558
            47         124754
            48         147273
            49         173525

            50         204226
            51         239943
            52         281589
            53         329931
            54         386155

            55         451276
            56         526823
            57         614154
            58         715220
            59         831820

            60         966467
            61        1121505
            62        1300156
            63        1505499
            64        1741630

            65        2012558
            66        2323520
            67        2679689
            68        3087735
            69        3554345

            70        4087968
            71        4697205
            72        5392783
            73        6185689
            74        7089500

            75        8118264
            76        9289091
            77       10619863
            78       12132164
            79       13848650

            80       15796476
            81       18004327
            82       20506255
            83       23338469
            84       26543660

            85       30167357
            86       34262962
            87       38887673
            88       44108109
            89       49995925

            90       56634173
            91       64112359
            92       72533807
            93       82010177
            94       92669720

            95      104651419
            96      118114304
            97      133230930
            98      150198136
            99      169229875

           100      190569292
           101      214481126
           102      241265379
           103      271248950
           104      304801365

           105      342325709
           106      384276336
           107      431149389
           108      483502844
           109      541946240

           110      607163746
           111      679903203
           112      761002156
           113      851376628
           114      952050665

           115     1064144451
           116     1188908248
           117     1327710076
           118     1482074143
           119     1653668665

           120     1844349560
           121     2056148051
           122     2291320912
           123     2552338241
           124     2841940500

           125     3163127352
           126     3519222692
           127     3913864295
           128     4351078600
           129     4835271870

           130     5371315400
           131     5964539504
           132     6620830889
           133     7346629512
           134     8149040695

           135     9035836076
           136    10015581680
           137    11097645016
           138    12292341831
           139    13610949895

           140    15065878135
           141    16670689208
           142    18440293320
           143    20390982757
           144    22540654445

           145    24908858009
           146    27517052599
           147    30388671978
           148    33549419497
           149    37027355200

           150    40853235313
           151    45060624582
           152    49686288421
           153    54770336324
           154    60356673280

           155    66493182097
           156    73232243759
           157    80630964769
           158    88751778802
           159    97662728555

           160   107438159466
           161   118159068427
           162   129913904637
           163   142798995930
           164   156919475295

           165   172389800255
           166   189334822579
           167   207890420102
           168   228204732751
           169   250438925115

           170   274768617130
           171   301384802048
           172   330495499613
           173   362326859895
           174   397125074750

           175   435157697830
           176   476715857290
           177   522115831195
           178   571701605655
           179   625846753120

           180   684957390936
           181   749474411781
           182   819876908323
           183   896684817527
           184   980462880430

           185  1071823774337
           186  1171432692373
           187  1280011042268
           188  1398341745571
           189  1527273599625

           190  1667727404093
           191  1820701100652
           192  1987276856363
           193  2168627105469
           194  2366022741845

           195  2580840212973
           196  2814570987591
           197  3068829878530
           198  3345365983698
           199  3646072432125

           200  3972999029388
           201  4328363658647
           202  4714566886083
           203  5134205287973
           204  5590088317495

           205  6085253859260
           206  6622987708040
           207  7206841706490
           208  7840656226137
           209  8528581302375

           210  9275102575355