## The First Computer Program

### February 8, 2011

Here is our version of the Countess’ program:

`(define (bernoulli limit)`

(let loop ((n 1) (bs '(-1/2)) (ns '()) (d 1) (ds '()))

(if (= limit n) bs

(let* ((2n (* n 2)) (2n-1 (- 2n 1)) (2n+1 (+ 2n 1))

(ns (cons 2n (map (lambda (x) (* 2n 2n-1 x)) ns)))

(b (- (apply + (map * bs (cons 2n-1 (but-last ns)) (map / (cons 2n+1 ds))))))

(bs (append bs (list b)))

(d (* d 2n 2n-1))

(ds (append ds (list d))))

(loop (+ n 1) bs ns d ds)))))

Here, *n* is as in the formula, *ns*, *ds* and *bs* are the accumulating lists of numerators, denominators, and Bernoulli numbers, and 2*n*, *d*, and *b* are the next elements of *ns*, *ds* and *bs*, respectively. Note that the order in which the elements are computed in the `let*`

is important.

We used an auxiliary function `but-last`

that is like `cdr`

except that it operates at the end of the list instead of the beginning; `but-last`

is useful from time to time, but not frequently enough to warrant inclusion in the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/USXM9t9Y, where you can also see the source code for `but-last`

.

This is a great programming assignment, and I’ll enjoy trying it, but I thought I’d mention that Michael Greene is the current holder of the Lucasian Chair, Hawking stepped down in 2009.

Oops, Green, not Greene. Silly typo =(

My Python solution.

The first version is a translation of the provided solution into scheme. The

second is a memoized version of the recursive relation that for B_n that can be

found in a bunch of places (I got mine from p. 180 of the “CRC Handbook of

Discrete and Combinatorial Mathematics”). I had to throw in the filter statement

due to differing ideas about the proper enumeration of the Bernoulli numbers.

Note: requires the

`fractions`

module for rational numbers.A solution in Common Lisp.

A solution in Haskell.