Bernoulli Number - An Algorithmic View: The Seidel Triangle

An Algorithmic View: The Seidel Triangle

The sequence S_n has another unexpected yet important property: The denominators of S_n divide the factorial (n − 1)!. In other words: the numbers T_n = S_n(n − 1)! are integers.

Thus the above representations of the Bernoulli and Euler numbers can be rewritten in terms of this sequence as

$\begin{align} B_{n} &= (-1)^{\left\lfloor \frac{n}{2}\right\rfloor }\left \frac{n }{2^n-4^n}\, T_{n}\, \quad (n = 2, 3, \ldots) \\ E_{n} &= (-1)^{\left\lfloor \frac{n}{2}\right\rfloor }\left T_{n+1} \quad\quad\qquad(n = 0, 1, \ldots) \end{align}$

These identities make it easy to compute the Bernoulli and Euler numbers: the Euler numbers E_n are given immediately by T_{2n + 1} and the Bernoulli numbers B_2n are obtained from T_2n by some easy shifting, avoiding rational arithmetic.

What remains is to find a convenient way to compute the numbers T_n. However, already in 1877 Philipp Ludwig von Seidel (Seidel 1877) published an ingenious algorithm which makes it extremely simple to calculate T_n.

Start by putting 1 in row 0 and let k denote the number of the row currently being filled. If k is odd, then put the number on the left end of the row k − 1 in the first position of the row k, and fill the row from the left to the right, with every entry being the sum of the number to the left and the number to the upper. At the end of the row duplicate the last number. If k is even, proceed similar in the other direction.

Seidel's algorithm is in fact much more general (see the exposition of Dominique Dumont (Dumont 1981)) and was rediscovered several times thereafter.

Similar to Seidel's approach D. E. Knuth and T. J. Buckholtz (Knuth & Buckholtz 1967) gave a recurrence equation for the numbers T_2n and recommended this method for computing B_2n and E_2n ‘on electronic computers using only simple operations on integers’.

V. I. Arnold rediscovered Seidel's algorithm in (Arnold 1991) and later Millar, Sloane and Young popularized Seidel's algorithm under the name boustrophedon transform.

Read more about this topic: Bernoulli Number