Highly Composite Numbers, Using Priority Queues

July 15, 2016

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

4 Responses to “Highly Composite Numbers, Using Priority Queues”

  1. matthew said

    I seemed to have jumped the gun here. You only need to add the successors with a new exponent added or the last exponent incremented – this will drastically reduce the growth of the priority queue.

  2. […] seen programs to compute the sequence of highly composite numbers in two previous exercises. Today, we look at a third algorithm, based on the Sieve of […]

  3. […] a recent exercise, we used a priority queue to calculate highly composite numbers. That worked, but it was too slow […]

  4. […] studied highly composite numbers in a series of several previous exercises, and had a lot of fun. In today’s exercise we look at a related concept: […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: