Essays/Bernoulli Numbers
Bernoulli numbers are defined by the recurrence relation:
(0=m) = +/ (B 1+m) * (i.1+m)!1+m
for m>:0 (Graham, Knuth, and Patashnik, Concrete Mathematics, Section 6.5). They can be computed as follows:
B0=: 3 : 0 b=. ,1x for_m. }.i.x: y do. b=. b,(1+m)%~-+/b*(i.m)!1+m end. )
B0 y are the first y Bernoulli numbers. For example:
B0 1 1 B0 13 1 _1r2 1r6 0 _1r30 0 1r42 0 _1r30 0 5r66 0 _691r2730 (B0 13) +/ .* (i.!]) 13x 0
The number of iterations can be halved by exploiting the fact that the odd-numbered Bernoulli numbers (other than the first) are 0.
B=: 3 : 0 b=. 1 _1r2 for_m. 2x*}.i.>.-:y do. b=. b,0,~(1+m)%~-+/b*(i.m)!1+m end. }:^:(2|y) b ) B 13 1 _1r2 1r6 0 _1r30 0 1r42 0 _1r30 0 5r66 0 _691r2730 (B +/ .* i.!])"0 >:i.50x 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
A shorter (but less efficient) expression derives by considering the recurrence relation as a matrix equation.
(i.!])"0 >: i.10x
1 0 0 0 0 0 0 0 0 0
1 2 0 0 0 0 0 0 0 0
1 3 3 0 0 0 0 0 0 0
1 4 6 4 0 0 0 0 0 0
1 5 10 10 5 0 0 0 0 0
1 6 15 20 15 6 0 0 0 0
1 7 21 35 35 21 7 0 0 0
1 8 28 56 70 56 28 8 0 0
1 9 36 84 126 126 84 36 9 0
1 10 45 120 210 252 210 120 45 10
(10{.1) %. (i.!])"0 >: i.10x
1 _1r2 1r6 0 _1r30 0 1r42 0 _1r30 0
B 10
1 _1r2 1r6 0 _1r30 0 1r42 0 _1r30 0
B1=: {.&1 %. (i.!])@>:@i.@x:
B1 10
1 _1r2 1r6 0 _1r30 0 1r42 0 _1r30 0
(B -: B1)"0 >: i.50
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
GKP equation 6.89 relates the 2*n-th Bernoulli number and the generalized harmonic number H2n of order 2*n :
H2n = (_1^n-1) * (2^(2*n)-1) * (1p1^2*n) * ({:B 1+2*n) % !2*n
Since H2n tends to 1 , we can derive, from these, approximations for the sizes of the Bernoulli numbers and for the logs of their absolute values. Thus:
BH=: 3 : 0
if. 2|y do. 0 else. (_1^<:-:y)*+:(!y)%2p1^y end.
)
BL=: 3 : 0
if. 2|y do. __ else. (^.2)+(+/^.>:i.y)-y*^.2p1 end.
)
0j_16 ": BH 100
_2.8382249570693794e78
0j_16 ": {: B 101
_2.8382249570693707e78
^. {: B 171
394.827
BL 170
394.827
Collected Definitions
B0=: 3 : 0
b=. ,1x
for_m. }.i.x: y do. b=. b,(1+m)%~-+/b*(i.m)!1+m end.
)
B=: 3 : 0
b=. 1 _1r2
for_m. 2x*}.i.>.-:y do. b=. b,0,~(1+m)%~-+/b*(i.m)!1+m end.
}:^:(2|y) b
)
B1=: {.&1 %. (i.!])@>:@i.@x:
BH=: 3 : 0
if. 2|y do. 0 else. (_1^<:-:y)*+:(!y)%2p1^y end.
)
BL=: 3 : 0
if. 2|y do. __ else. (^.2)+(+/^.>:i.y)-y*^.2p1 end.
)
Contributed by Roger Hui.