Highly Composite Numbers, Using Priority Queues

July 15, 2016

A different solution to the previous exercise exploits the form of highly composite numbers, which always consists of small primes to large exponents, so we can specify the highly composite number using only the exponents; for instance, 64221111 represents the number 26 · 34 · 52 · 72 · 111 · 131 · 171 · 191 = 293318625600. Since the exponents must be non-increasing, there are five possibilities for a larger highly composite numbers, represented using the power-notation as 74221111, 65221111, 64321111, 64222111, and 642211111. Thus, we find composite numbers by starting with the null power-list, which equates to the number 20 = 1, then add all possible successors to a priority queue, pop the successors in order, check each for a new record number of divisors, and push the successors of that number back on to the priority queue.

Your task is to generate the sequence of highly composite numbers using a priority queue. 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

3 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 […]

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: