Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
High School Discrete Mathematics
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/