Counting the Number of Factors

Date: 01/04/99 at 08:14:53
From: Colin Dunning
Subject: How to Factor

Is there an easier way other than trial and error to find the number 
less than 100 that has the greatest number of factors?

Date: 01/04/99 at 11:04:48
From: Doctor Rob
Subject: Re: How to Factor

Thanks for writing to Ask Dr. Math!

Yes, there is an easier way.

If you factor a number into its prime power factors, then the total
number of factors is found by adding one to all the exponents and
multiplying those results together. Example: 108 = 2^2*3^3, so the 
total number of factors is (2+1)*(3+1) = 3*4 = 12. Sure enough, the
factors of 108 are 1, 2, 3, 4, 6, 9, 12, 18, 27, 36, 54, and 108.
This happens because to be a factor, a number must have the same 
primes, and raised to the same or lower powers. Each factor of 108 must 
be a power of 2 times a power of 3, and the exponent of 2 can be 0, 1, 
or 2, and the exponent of 3 can be 0, 1, 2, or 3. There are three 
choices for the exponent of 2 and 4 choices for the exponent of 3, for 
a total of 3*4 = 12 possible choices. Each gives a different factor, so 
there are 12 factors.

Now to create small numbers with many factors, you should use the
smallest primes. The larger the exponents, the more factors you will
have, but you have to keep the number less than 100, so the exponents
cannot be too large.

If there is only one prime, it should be 2. To stay less than 100,
the exponent can be at most 6, since 2^7 = 128 > 100. 2^6 = 64 has
6+1 = 7 factors.

If there are two primes, they should be 2 and 3. To stay less than 100, 
the exponent of 3 can be at most 4, since 3^5 = 243 > 100. Consider 
numbers of the form a power of 2 times 3, 3^2, 3^3, or 3^4. Pick the 
power of 2 as large as possible while staying under 100. Compute the 
number of factors, and keep the champion(s).

If there are three primes, they should be 2, 3, and 5. To stay less
than 100, the exponent of 5 can be at most 2, since 5^3 = 125 > 100.
Consider numbers of the form a power of 2 times a power of 3 times 5 or 
5^2. Pick a power of 3 which keeps you under 100, then pick the power 
of 2 as large as possible while staying under 100. Compute the number 
of factors, and keep the champion(s).

There cannot be four or more primes, because 2*3*5*7 = 210 > 100.

You get the following table, in which you can complete the last
column:

Exponent of 2   Exponent of 3   Exponent of 5    N   Number of Factors
      6               0               0         64           7
      5               1               0         96
      3               2               0         72
      0               4               0         81           5
      4               0               1         80
      2               1               1         60
      1               2               1         90
      1               0               2         50           6
      0               1               2         75           6

This systematic procedure is better than trial and error.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/