Factoring

Date: 02/09/99 at 13:40:20
From: kevin tesler
Subject: Factoring

I am trying to find out how to find the smallest number (integer) that 
has 30 factors.

Is there an equation or a table that lists this information? Can you 
help? How is it solved?

Kevin Tesler

Date: 02/09/99 at 16:38:33
From: Doctor Rob
Subject: Re: Factoring

There is a formula that tells you how many factors a number N has in 
terms of the prime power factorization of N. If the number of factors 
is F, and

          k
   N = PRODUCT p[i]^e[i],
         i=1
then
          k
   F = PRODUCT (e[i]+1).
         i=1

This is because to each factor of N there corresponds a k-tuple of 
exponents of the primes p[i], such that the exponent of p[i] in the 
prime power factorization of the factor is between 0 and e[i], 
inclusive. For each i from 1 to k, there are e[i] + 1 choices for the 
exponent of p[i] in the factor. The total number of choices for 
exponents is the total number of factors; hence the formula for F given 
above.

The last equation above means that the factorization of F is important.  
(Factors of 1 correspond to e[i] = 0, so p[i]  does not divide N, so 
they can be ignored.) In your case F = 30, which is a constraint on the 
e's.

   30 = (29+1),
      = 15*2 = (14+1)*(1+1),
      = 10*3 = (9+1)*(2+1),
      = 6*5 = (5+1)*(4+1),
      = 5*3*2 = (4+1)*(2+1)*(1+1),

are the relevant expressions. Thus all the numbers N with exactly 30 
factors are of one of the five forms 

   N = p^29,
   N = p^14 * q^1,
   N = p^9 * q^2,
   N = p^5 * q^4,
   N = p^4 * q^2 * r^1,

where p, q, and r are any prime numbers.  Thus, for example, 7^14 * 79 
has exactly 30 factors, as does 11^5 * 23^4.

It is also easy to see that if you have a certain collection of e's, 
the best order to minimize N is to put the largest e's on the smallest 
primes. This is because if p < q, and a < b, then

   p^(b-a) < q^(b-a),
   p^(b-a) * [p^a * q^a] < q^(b-a) * [p^a * q^a],
   p^b * q^a < p^a * q^b.

Thus you should sort the e's in decreasing order, and assign them to 
the primes 2, 3, 5, 7, 11, and so on, in increasing order.

This means that there are just five numbers, one of each form, which 
have a chance of being the smallest N. You can easily compute them and 
figure out which one is the winner.

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

Date: 02/11/99 at 02:30:09
From: Kevin Tesler
Subject: Re: Factoring

Now I am more confused than before? Please help?

Here is something I understand:

28 has 6 factors: 1, 2, 4, 7, 14, 28

I am trying to find out the number while only knowing that it has 30 
factors. I am also trying to find the smallest number that has 30 
factors. I was told that the number is between 100 and 1000. I could 
spend hours doing factor trees, but it is not efficient. I am curious 
as to what the answer is?

Kevin Tesler

Date: 02/11/99 at 08:34:19
From: Doctor Rob
Subject: Re: Factoring

28 has 6 factors because 28 = 2^2 * 7^1, and 2 and 7 are prime numbers. 
If you add one to each exponent, and multiply those results together, 
you get

   (2+1)*(1+1) = 3*2 = 6,

which is the number of factors. This always works. If the number is of 
the form p^2 * q^1, no matter what prime numbers p and q you choose, 
there will always be 6 factors. You can arrange them this way:

     | 0     1      2
   --------------
   0 | 1     p     p^2
   1 | q    p*q   p^2*q

For example, if p = 11 and q = 5, the same thing works:

     | 0     1       2
   --------------------
   0 | 1     11     121
   1 | 5     55     605

Across the top is the exponent of p; down the left is the exponent of 
q. The numbers across the top run from 0 to 2, which is the power of p 
that divides p^2 * q^1, and the numbers down the left run from 0 to 1, 
which is the power of q that divides p^2 * q^1. There are two rows and 
three columns, so 6 entries in this table.

If you change the exponents, the table will get wider or longer but its 
dimensions will still be one more than the exponent of the powers of p 
and q that divide the number. For example, if the number has the form 
p^3 * q^4, then the table will be (3+1) = 4 by (4+1) = 5, and there 
will be 4*5 = 20 divisors.

If you increase to three prime numbers dividing the number, the 
rectangular table becomes three-dimensional, and its dimensions are 
just one more than the exponents of the powers of the primes dividing 
the number.

Now your problem is to find exponents a, b, and c such that

   (a+1)*(b+1)*(c+1) = 30,

and such that

   2^a * 3^b * 5^c = N

is smallest.  2, 3, and 5 are chosen as the prime numbers because they 
are the smallest ones. I explained in the previous message that for N 
to be smallest, you must have a >= b >= c.

There are five sets of a, b, and c that work in the first equation 
above, and have a >= b >= c:

   a = 29,  b = 0,  c = 0,  N = 2^29,
   a = 14,  b = 1,  c = 0,  N = 2^14 * 3,
   a =  9,  b = 2,  c = 0,  N = 2^9 * 3^2,
   a =  5,  b = 4,  c = 0,  N = 2^5 * 3^4,
   a =  4,  b = 2,  c = 1,  N = 2^4 *3^2 * 5.

They arise from the factorizations

   30 = 30*1*1 = 15*2*1 = 10*3*1 = 6*5*1 = 5*3*2,

respectively. One of those N's is your answer.

If you understand all of this, go back and try to reread the previous 
message.

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