Highly Composite Numbers, Revisited
August 16, 2016
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.
Programming Praxis 
I implemented the proposed scheme in Python. It works indeed superfast. I am not sure if I made a mistake, but I notice that I am missing some hcn’s. The first is at n=815. The correct hcn is 10 6 4 2^5 1^25 (notation of , but the answer I get is 10 5 4 3 2^2 1^28 (which nr 816 on the “official” list). Could you please, run your code and check, if I made a mistake?
I implemented the proposed scheme in Python. It works indeed superfast. I am not sure if I made a mistake, but I notice that I am missing some hcn’s. The first is at n=815. The correct hcn is 10 6 4 2^5 1^25 (notation of , but the answer I get is 10 5 4 3 2^2 1^28 (which nr 816 on the “official” list). Could you please, run your code and check, if I made a mistake?
(I hope this format better)
I implemented the proposed scheme in Python. It works indeed superfast. I am not sure if I made a mistake, but I notice that I am missing some hcn’s. The first is at n=815. The correct hcn is 10 6 4 2^5 1^25 (notation of , but the answer I get is 10 5 4 3 2^2 1^28 (which is nr 816 on the “official” list). Could you please, run your code and check, if I made a mistake?
(I hope this format better and sorry for creating this mess)
I think, I found my mistake. I was only adding successors for every hcn found. It has to be done for every number tested, I guess. This reduces speed considerably and much more memory is needed. It is surprising that the incorrect way of adding successors gives correct hcn’s up to number 815.
I found a hack, that works: only add successors if the ratio between the number of divisors and the maximum number of divisors is higher than a cut-off (I tried 0.95). Then you can calculate the first 10000 hcn’s correctly in 668 secs, which is still great for such a simple scheme. If I do not use the hack and add successors only when finding an hcn the time is 21 secs, but the hcn’s are not correct. I will post code in Python later.
I posted Python3 code on ideone. The results were checked upto 30000 hcns. Running times are 13 secs for 5000, 75 secs for 10000 and 1250 secs for 30000.The cut-off value is set to 0.99. That means that every number that has a number of divisors, that is at least 0.99 times the maximum number of divisors found sofar will be used to add successors.
I did a few optimizations. The code runs new incredibly fast. It calculates the first 100,000 hcn’s in about 5 minutes. A dramatic speedup compared to the 15 minutes for 540 hcn’s that @matthew reported in his first post.
I checked to results with the data of Achim Flammenkamp up to 770,000, which is about as high as his list gets. Still correct. Amazing.
Is there a C++ implementation?
[…] 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: highly abundant […]