Highly Factorable Numbers

Now that we have implemented various methods to count ordered and unordered factorizations, we will put them to use to produce lists of numbers that have a greater number of factorizations than any smaller positive integer.

We say that a natural number is highly factorable with respect to the function , if for all , . In [8], Canfield, Erdös, and Pomerance computed a list of highly factorable numbers with respect to the function . Since the functions and depend on the prime exponents but not the primes themselves, it is clear that a highly factorable number must be of the form with and where denotes the th prime number. We use Partitions to generate a list of acceptable exponents and then define a function ExponentsToNumber to produce a natural number using the exponents from the partition and the corresponding first few primes.

To produce all numbers of this form less than a given value bound, we must consider all partitions of numbers 1 to Log[2,bound], as the smallest number arising from a partition of is .

For example, let us find all the highly factorable numbers less than 1000.

Now eliminate numbers greater than bound in our list, compute the value of the function for each number in the list, and eliminate the values that are not highly factorable using a replacement rule.

Now we use GridBox to display our table of highly factorable numbers.

Replacing by leads to the following list of highly factorable numbers with respect to .

Erdös, Canfield, and Pomerance were able to compute a table of all highly factorable numbers less than with respect to in their paper [8]. The approach just used gives a much faster method to find the 118 highly factorable numbers less than with respect to as well as the 124 highly factorable numbers less than with respect to .

Numbers Highly Factorable with Respect to Both P and H

There appear to be many numbers common to both of the displayed lists. To find these common numbers, join the two lists and extract the first elements (the common values of ). Find the pairs by using Split. Then extract the common numbers as the first element of the sublists of length 2.

So up to 1000, most highly factorable numbers appear in both lists. However, common numbers seem to become less frequent as we increase our bound. For example, we find that there are 55 common highly factorable numbers less than , the largest of these being 43545600.