FactoringDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/