Programming Praxis

In a recent exercise, we used a priority queue to calculate highly composite numbers. That worked, but it was too slow and required too much memory to compute very large highly composite numbers. In today’s exercise we will use the same algorithm but a new data structure that permits us to compute very large highly composite numbers.

We make two changes. First, we record both highly composite numbers and candidates that are being considered as new highly composite numbers in a data structure called number-divisors-exponents, or ndxs for short, which has a number n in its car, the number of divisors d of n in its cadr, and the exponents of the prime factors of n in its cddr; carrying those numbers around rather than recomputing them as needed saves a little bit of time. The second change is more important; we use the distinct priority queue of a previous exercise to eliminate duplicate candidates, which greatly reduced the amount of computation needed to find highly composite numbers (since each candidate is considered only once) and the amount of memory require to store the candidates (because duplicates are not stored).

Your task is to write a program to compute highly composite numbers, as described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2