Counting the Number of FactorsDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/