Finding Numbers with a Certain Number of Factors

Date: 3/12/96 at 16:18:46
From: Patrick Krause
Subject: Factoring Question

Dr. Math:

    I am stuck on the following question:

      Given that twelve is the least postive integer with six
      different positive factors (1,2,3,4,6,12).  What is the
      least positive integer with exactly twenty-four positive
      factors?

    I know by writing a factoring program that the answer is 
    360 (factors: 

1,2,3,4,5,6,8,9,10,12,15,18,20,24,30,36,40,45,60,72,90,120,180,360)

    but I cannot make the connection between the factors of 12 
    and the way to find a number with 24 positive factors.

    I have tried prime factorization, I have tried everything that 
    I can to make this connection, but I have cannot make the 
    connection.  I do not see what knowing the factors of 12 have 
    to do with the factors of 360.

    Can you give me some help with this?

Thank you.

Date: 5/30/96 at 11:38:32
From: Doctor Alain
Subject: Re: Factoring Question

Let P1, P2, ... , Pn be the prime factors of a given number X, and 
let E1, E2, ..., En be the greatest exponents of the respective 
prime factors such that their powers are still factors of X. That 
is to say that

X = P1^E1 * P2^E2 * ... * Pn^En.

Then all the positive factors F of X are in the form

F = P1^e1 * P2^e2 * ... * Pn^en,

where e1, e2, ... , en are all integer numbers greater or equal to 
zero and less than or equal to their respective Ei (e1 less than 
or equal to E1, e2 less than or equal to E2, ... , en  less than 
or equal to En). Any set of integers e1, e2, ... , en satisfying 
these conditions will produce a factor of X. The set of numbers 
satisfying these conditions is one-to-one onto with the set of 
positive factors of X. So the number N of positive factors of X 
is given by

N = (E1+1) * (E2+1) * ... * (En+1).

[There are E1+1 ways to chose e1, E2+1 ways to chose e2, ..., 
En+1 ways to chose en]

Now let's go back to your problem. You want a number with 24 
positive factors, 24 is 3*8 = 3*4*2 = 3*2*2*2 so the numbers E1, 
E2, ... , En will be either

(#1) E1=2 (E1+1=3), E2=7 (E2+1=8)       [24 = 3*8]
or
(#2) E1=2, E2=3, E3=1                   [24 = 3*4*2]
or
(#3) E1=2, E2=1, E3=1, E4=1.            [24 = 3*2*2*2]

These are the only ways you can get N = (E1+1) * (E2+1) * ... * 
(En+1)=24.

So all integers X with 24 positive factors can be written in one 
of the following forms

(#1) X = P1^2 * P2^7

(#2) X = P1^2 * P2^3 * P3

(#3) X = P1^2 * P2 * P3 * P4

The smallest number of form #1 is obviously 3^2 * 2^7 = 1152.
The smallest number of form #2 is obviously 3^2 * 2^3 * 5 = 360.
The smallest number of form #3 is obviously 2^2 * 3 * 5 * 7 = 420.

-Doctor Alain,  The Math Forum