modulomathy.com

#math trivia for #August28: #240 is highly composite: it has more divisors than any smaller number. How many? What was the previous record?

— Burt Kaliski Jr. (@modulomathy) August 29, 2013

The number 240 has 20 divisors:  1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 20, 24, 30, 40, 48, 60, 80, 120 and 240.

A more formal way to show that there are 20 is by starting with the factorization of 240 into primes:

240 = 2⁴*3*5 .

The divisors of 240 must have the form

2ⁱ*3^j*5^k,

where i is between 0 and 4, j is 0 or 1, and k is 0 or 1.  There are 5*2*2 = 20 possible combinations of exponents (i,j,k).  Each produces a distinct divisor because of there is a unique factorization of every integer into primes.  (See the solution to #168 for a little more detail on how to count divisors.)

The previous record can be found by applying the formal approach in reverse, trying possible divisor counts, starting with 19 and moving lower as needed.  Let x denote the previous record holder.

Suppose the record were 19.  Then x would need to have the form x = p¹⁸ for some prime p, so that there would be 19 factors, corresponding to the exponents between 0 and 18. (There is no way to factor 19 into combinations of two or more exponents, because 19 is prime.)  Such an x would be at least 2¹⁸, which is much larger than 240, so the previous record can’t be 19.

Now try a divisor count of 18. In this case, x would need to have one of the forms

x = p¹⁷
x = p⁸*q
x = p⁵*q²
x = p²*q²*r

for distinct primes p, q and r. None of the first three forms would give a smaller record holder, because x would be at least 2¹⁷, 2⁸*3, or 2⁵*3*2, all of which are larger than 240. But the fourth form is a possibility. The smallest value of x with this form will set the record, so we’ll want the primes with the larger exponents to be the first two primes, i.e., p = 2, q = 3, and the prime with the smaller exponent to be the next prime, r = 5. The record holder is thus

x = 2²*3²*5 = 180,

which has 18 divisors:  1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90, and 180.