Problem Statement

This task is a variation of the short story by Arthur C. Clarke. (Solvers should be aware of the consequences of completing this task.) In detail, to specify what is meant by a   “name”:

Display the first 25 rows of a number triangle which begins: Where row

n

{\displaystyle n}

corresponds to integer

n

{\displaystyle n}

,   and each column

C

{\displaystyle C}

in row

m

{\displaystyle m}

from left to right corresponds to the number of names beginning with

C

{\displaystyle C}

. A function

G ( n )

{\displaystyle G(n)}

should return the sum of the

n

{\displaystyle n}

-th   row. Demonstrate this function by displaying:

G ( 23 )

{\displaystyle G(23)}

,

G ( 123 )

{\displaystyle G(123)}

,

G ( 1234 )

{\displaystyle G(1234)}

,   and

G ( 12345 )

{\displaystyle G(12345)}

.
Optionally note that the sum of the

n

{\displaystyle n}

-th   row

P ( n )

{\displaystyle P(n)}

is the     integer partition function. Demonstrate this is equivalent to

G ( n )

{\displaystyle G(n)}

by displaying:

P ( 23 )

{\displaystyle P(23)}

,

P ( 123 )

{\displaystyle P(123)}

,

P ( 1234 )

{\displaystyle P(1234)}

,   and

P ( 12345 )

{\displaystyle P(12345)}

.

If your environment is able, plot

P ( n )

{\displaystyle P(n)}

against

n

{\displaystyle n}

for

n

1 … 999

{\displaystyle n=1\ldots 999}

.

Let's start with the solution:

(define (f m n)
  (define (sigma g x y)
    (define (sum i)
      (if (< i 0) 0 (+ (f x (- y i) ) (sum (- i 1)))))
    (sum y))
  (cond ((eq? m n) 1)
        ((eq? n 1) 1)
        ((eq? n 0) 0)
        ((< m n) (f m m))
        ((< (/ m 2) n) (sigma f (- m n) (- m n)))
        (else (sigma f (- m n) n))))
(define (line m)
  (define (connect i)
    (if (> i m) '() (cons (f m i) (connect (+ i 1)))))
  (connect 1))
(define (print x)
  (define (print-loop i)
    (cond ((< i x) (begin (display (line i)) (display "\n") (print-loop (+ i 1)) ))))
  (print-loop 1))
(print 25)