Programming Praxis

Given a number n, the possible successors are given by the following function:

(define (next n)
  (let loop ((front (list)) (back (powers n)) (xs (list)))
    (cond ((null? back)
            (map prod (cons (reverse (cons 1 front)) xs)))
          ((null? front)
            (loop (cons (car back) front) (cdr back)
                  (cons (cons (+ (car back) 1) (cdr back)) xs)))
          ((< (car back) (car front))
            (loop (cons (car back) front) (cdr back)
                  (cons (append (reverse (cons (+ (car back) 1) front))
                                (cdr back))
                        xs)))
          (else (loop (cons (car back) front) (cdr back) xs)))))

Thus, (next 293318625600) yields the successor list 6746328388800, 3226504881600, 1466593128000, 879955876800, 586637251200. Then we manage the priority queue and find records like this:

(define (hcn limit)
  (let loop ((k 1) (n 1) (pq (pq-insert 1 pq-empty)) (record 0))
    (when (<= k limit)
      (let ((divs (apply * (map add1 (powers n)))))
        (cond ((< record divs)
                (display k) (display " ") (display (powers n))
                (display " ") (display n) (newline)
                (loop (+ k 1) (pq-first pq)
                      (pq-insert-all (next n) (pq-rest pq))
                      divs))
              (else (loop k (pq-first pq)
                          (pq-insert-all (next n) (pq-rest pq))
                          record)))))))

Here’s the function in action:

> (hcn 40)
1 () 1
2 (1) 2
3 (2) 4
4 (1 1) 6
5 (2 1) 12
6 (3 1) 24
7 (2 2) 36
8 (4 1) 48
9 (2 1 1) 60
10 (3 1 1) 120
11 (2 2 1) 180
12 (4 1 1) 240
13 (3 2 1) 360
14 (4 2 1) 720
15 (3 1 1 1) 840
16 (2 2 1 1) 1260
17 (4 1 1 1) 1680
18 (3 2 1 1) 2520
19 (4 2 1 1) 5040
20 (3 3 1 1) 7560
21 (5 2 1 1) 10080
22 (4 3 1 1) 15120
23 (6 2 1 1) 20160
24 (4 2 2 1) 25200
25 (3 2 1 1 1) 27720
26 (4 4 1 1) 45360
27 (5 2 2 1) 50400
28 (4 2 1 1 1) 55440
29 (3 3 1 1 1) 83160
30 (5 2 1 1 1) 110880
31 (4 3 1 1 1) 166320
32 (6 2 1 1 1) 221760
33 (4 2 2 1 1) 277200
34 (5 3 1 1 1) 332640
35 (4 4 1 1 1) 498960
36 (5 2 2 1 1) 554400
37 (6 3 1 1 1) 665280
38 (4 2 1 1 1 1) 720720
39 (3 3 1 1 1 1) 1081080
40 (5 2 1 1 1 1) 1441440

You can run the program at http://ideone.com/A9ewx3, where you will see the code for priority queues, generating prime numbers, and computing the power-representation of the highly composite numbers.

The priority queue algorithm isn’t especially fast. Part of the problem is our simplistic implementation, which does too much manipulation of the exponents and needlessly recomputes prime numbers. But a bigger problem is that the priority queue grows very quickly, and that’s not so easy to fix. We’ll see other algorithms for computing the sequence of highly composite numbers in future exercises.

Pages: 1 2