Quandaries and Queries
im completely stuck on this math question that i was given. the question is: Of all the whole numbers less than or equal to 5000, which one has the most factors?
I started off with numbers 1-50 listing off all of the factors. I got 24 and 30 with 8 factors and 36 and 48 with 9 factors. I just can't figure out how to get the most factors????
is there any help you can give me?
To find the number of factors of a number N you write N as a product of distinct primes powers. For instance, 48 = 16*3 = 24 * 31. You then add 1 to each exponent and take the product of the resulting numbers to get the number of factors of N. In this case you get 48 = 24 * 31 and (4+1)*(1+1) = 10, so 48 has 10 factors (1, 2, 4, 8, 16,3, 6, 12, 24, 48), rather than 9 as you claimed.
So, to find a number less
than 5000 which has as many factors as possible, you would like to
find a number with as many prime factors as possible (to have many
to multiply) and exponents as large as
possible (to have large terms to multiply). Also the prime factors must
be as small as possible to keep their product as low as possible; for
the same reason the larger exponents must be on the smallest factors.
That is the most prime factors you can have. if you take more factors the smallest number you can get is 2*3*5*7*11*13 = 30030, which is more than 5000.
In case e), with five prime factors, you notice that
you still have some
which is still less than 5000 and has (2+1)*(1+1)*(1+1)*(1+1)*(1+1)
This is the only way to increase the exponents without going over 5000, so the highest number of factors you can reach with a number that has five prime factors is 48, reached by the number 4620.
In case d) with the four factors 2, 3, 5, 7, there is much more leeway to increase the factors: you can increase the exponent of 2 to 5 to get
which has 6*2*2*2 = 48, so you get as many factors as in case e). However you have other possibilities: you can decrease the exponent 2 to increase the exponent of 3. If you increase the exponent or 3 to 2, you need to decrease the exponent of 2 to stay below 5000. You easily see that you need to decrease it to 3, so you get the number (23)*(3*2)*5*7 = 2520, which has 4*3*2*2 = 48 factors. After that, you don't need to consider increasing the exponent of 3 again, because then the exponent of 3 would be higher than that of 2, and it makes more sense to keep the larger exponents on the smaller factors. So the only other possibility is to keep the exponent of 3 at 2 and reduce the exponent of 2 to increase the exponent of 5. The smallest number you could get in that way would be (22)*(32)*(52)*7 = 6300, which is larger than 5000. So the conclusion in case d is that you get new examples of numbers with 48 factors, but no number with more factors.
You then go on to case c) and then case b) and case a), to see if you get any number with more factors. I will leave you fhe fun of finding out for yourself.