Finding highly composite numbers

There are a number of methods for finding highly composite numbers. Most of them rely on the fact that for all highly composite numbers all subsets of prime factors and their exponents are also optimally composite for those prime factors.
Brute-force method
With the brute-force method, one starts at 1 and then tests each number to see if it is highly composite. It is not necessary to completely factorise each number, but enough processing has to be performed to eliminated numbers which are not highly composite. This method has the disadvantage that it is quite inefficient.
Increasing steps method
The increasing steps method is a refinement of the brute-force method. Obviously, apart from 1, all highly composite numbers are divisible by 2, so from 2 onwards, it is sufficient to only examine the even numbers. If we can show that from above certain thresholds, all highly composite numbers have to be divisible by 6, then 12, then 60 and so forth, we save ourselves looking at a lot of numbers. This can be done by looking at pairs of prime factors and those numbers that only have that pair of prime factors and have more divisors than all smaller numbers with that pair of prime factors. Here are a few examples of how this works:
* For prime factors 2 and 3 the only optimally composite powers of 2 are 2 and 4 (6 is smaller than 8, 12 is smaller than 32 and so forth). Therefore, after 4, all highly composite numbers have to contain the prime factor 3 (as well as 2) and therefore will have to be divisible by 6.
* For prime factors 2 and 3 all optimally composite number after 6 are divisible by 4. Also for all pairs of prime factors that include 2 and 5 or higher, all optimally composite numbers, apart from 2, are divisible by 4 (4 is smaller than 5 and 8 is smaller than 10). Therefore, after 6, all highly composite numbers have to be divisible by 4 and therefore 12.
* For prime factors 2 and 5 the highest optimally composite power of 2 is 16 (20 is smaller than 32, 40 is smaller than 128 and so forth). For prime factors 3 and 5, the highest optimally composite power of 3 is 9 (15 is smaller than 27). Therefore, there can be no highly composite number after 144 (16 times 9) that is not divisible by 5 and therefore 60. As it happens, the last highly composite number that is not divisible by 5 is 48, but with this method we only know this after we have checked all factors of 12 up to 144.
Successive prime factors method
If we wanted to find all highly composite numbers up to some upper limit, we would start with all the powers of 2 (the first prime factor), up to our upper limit. Then we would combine the powers of 2 with various powers of 3 (the second prime number), including the zero power (although we would not generate any number where the exponent of 3 is greater than the exponent for 2). We would immediate eliminate the numbers which exceed our upper limit. After sorting the remaining numbers we would then keep those which have more prime factors than any smaller number from our set. The numbers we have now left are not all highly composite but they have more divisors than any smaller number that only has prime factors 2 and/or 3.
We would then combine our set with various powers of 5. Again, we eliminate numbers which exceed our upper limit, sort and keep only those numbers which have more divisors than any smaller number in the set.
We would repeat this process for every prime factor, until we get to a prime factor which does not lead to the inclusion of new numbers in our set. We now have all highly composite numbers up to our upper limit.

Main Menu

See Also

Main Menu