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:

#lang racket

(define (cdr-empty ls) (if (empty? ls) empty (cdr ls)))

(define (names-of n)
  (define (names-of-tail ans raws-rest n)
    (if (zero? n)
        ans
        (names-of-tail (cons 1 (append (map + 
                                            (take ans (length raws-rest)) 
                                            (map car raws-rest))
                                       (drop ans (length raws-rest))))
                       (filter (compose not empty?)
                               (map cdr-empty (cons ans raws-rest)))
                       (sub1 n))))
  (names-of-tail '() '() n))

(define (G n) (foldl + 0 (names-of n)))

(module+ main
  (build-list 25 (compose names-of add1))
  (newline)
  (map G '(23 123 1234)))