#五角数
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