# §24.19 Methods of Computation

## §24.19(i) Bernoulli and Euler Numbers and Polynomials

Equations (24.5.3) and (24.5.4) enable $B_{n}$ and $E_{n}$ to be computed by recurrence. For higher values of $n$ more efficient methods are available. For example, the tangent numbers $T_{n}$ can be generated by simple recurrence relations obtained from (24.15.3), then (24.15.4) is applied. A similar method can be used for the Euler numbers based on (4.19.5). For details see Knuth and Buckholtz (1967).

Another method is based on the identities

 24.19.1 $N_{2n}=\frac{2(2n)!}{(2\pi)^{2n}}\left(\prod_{p-1\mathbin{|}2n}p\right)\left(% \prod_{p}\frac{p^{2n}}{p^{2n}-1}\right),$ ⓘ Symbols: $\pi$: the ratio of the circumference of a circle to its diameter, $!$: factorial (as in $n!$), $n$: integer and $p$: prime Referenced by: §24.19(i) Permalink: http://dlmf.nist.gov/24.19.E1 Encodings: TeX, pMML, png See also: Annotations for §24.19(i), §24.19 and Ch.24
 24.19.2 $\displaystyle D_{2n}$ $\displaystyle=\prod_{p-1\mathbin{|}2n}p,$ $\displaystyle B_{2n}$ $\displaystyle=\dfrac{N_{2n}}{D_{2n}}.$ ⓘ Symbols: $B_{\NVar{n}}$: Bernoulli numbers, $n$: integer and $p$: prime Permalink: http://dlmf.nist.gov/24.19.E2 Encodings: TeX, TeX, pMML, pMML, png, png See also: Annotations for §24.19(i), §24.19 and Ch.24

If $\widetilde{N}_{2n}$ denotes the right-hand side of (24.19.1) but with the second product taken only for $p\leq\left\lfloor(\pi e)^{-1}2n\right\rfloor+1$, then $N_{2n}=\left\lceil\widetilde{N}_{2n}\right\rceil$ for $n\geq 2$. For proofs and further information see Fillebrown (1992).

For other information see Chellali (1988) and Zhang and Jin (1996, pp. 1–11). For algorithms for computing $B_{n}$, $E_{n}$, $B_{n}\left(x\right)$, and $E_{n}\left(x\right)$ see Spanier and Oldham (1987, pp. 37, 41, 171, and 179–180).

## §24.19(ii) Values of $B_{n}$ Modulo $p$

For number-theoretic applications it is important to compute $B_{2n}\pmod{p}$ for $2n\leq p-3$; in particular to find the irregular pairs $(2n,p)$ for which $B_{2n}\equiv 0\pmod{p}$. We list here three methods, arranged in increasing order of efficiency.

• Tanner and Wagstaff (1987) derives a congruence $\pmod{p}$ for Bernoulli numbers in terms of sums of powers. See also §24.10(iii).

• Buhler et al. (1992) uses the expansion

 24.19.3 $\frac{t^{2}}{\cosh t-1}=-2\sum_{n=0}^{\infty}(2n-1)B_{2n}\frac{t^{2n}}{(2n)!},$

and computes inverses modulo $p$ of the left-hand side. Multisectioning techniques are applied in implementations. See also Crandall (1996, pp. 116–120).

• A method related to “Stickelberger codes” is applied in Buhler et al. (2001); in particular, it allows for an efficient search for the irregular pairs $(2n,p)$. Discrete Fourier transforms are used in the computations. See also Crandall (1996, pp. 120–124).