Bernoulli Number - An Algorithmic View: The Seidel Triangle

An Algorithmic View: The Seidel Triangle

The sequence Sn has another unexpected yet important property: The denominators of Sn divide the factorial (n − 1)!. In other words: the numbers Tn = Sn(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 En are given immediately by T2n + 1 and the Bernoulli numbers B2n are obtained from T2n by some easy shifting, avoiding rational arithmetic.

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

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 T2n and recommended this method for computing B2n and E2n ‘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