Questions about the world of GMAT Math from other sources and general math related questions.
gt7er
 
 

is there a formula to calculate the number of factors?

by gt7er Sat Mar 08, 2008 1:35 pm

what is the number of factors for 441? It breaks down into 3, 3, 7, 7 ...how do you find the total number of factors? what's the formula?
H_to_750
 
 

no formula

by H_to_750 Sat Mar 08, 2008 3:39 pm

There is no formula you just take a look at how many different combinations there are of prime factors

So in this case

WE have 3, 7, (7 x 7 = 49), (7 x 3 = 21), (3 x 3 = 9) (9 x 7 = 63), (49 x 3 = 147) , 441, and 1

So for 441 we have total of 9 factors. Just always remember that 1 and the number it self is also a factor.
David Pollack
 
 

A nice formula for the number of factors

by David Pollack Sun Mar 09, 2008 1:25 am

Sure, there is! It just depends on how many prime factors your number has, and how many times each one appears.

Suppose your number factors as a product p^a * q^b * .... *r^k. Then to get any factor you want you should take _up to_ a copies of p, _up to_ b copies of q, etc. and multiply them all together. The number of ways you can choose _up to_ a copies of p is (a+1) since you could choose 0 copies, 1 copy, 2 copies, ..., a copies. Likewise there are (b+1) ways to choose how many q's to include, etc.

So the number of factors for your number would be (a+1)*(b+1)*...(k+1).

For example, if your number is 441 = 3^2 * 7^2 then the number of factors is (2+1)*(2+1)=3*3=9.

One more example: if your number is 360 = 8*9*5 = 2^3 * 3^2 * 5^1 then the number of factors is (3+1)*(2+1)*(1+1)=24.
RonPurewal
ManhattanGMAT Staff
 
Posts: 15557
Joined: Tue Aug 14, 2007 8:23 am
 

Re: A nice formula for the number of factors

by RonPurewal Wed Mar 12, 2008 3:59 am

David Pollack wrote:Sure, there is! It just depends on how many prime factors your number has, and how many times each one appears.

Suppose your number factors as a product p^a * q^b * .... *r^k. Then to get any factor you want you should take _up to_ a copies of p, _up to_ b copies of q, etc. and multiply them all together. The number of ways you can choose _up to_ a copies of p is (a+1) since you could choose 0 copies, 1 copy, 2 copies, ..., a copies. Likewise there are (b+1) ways to choose how many q's to include, etc.

So the number of factors for your number would be (a+1)*(b+1)*...(k+1).

For example, if your number is 441 = 3^2 * 7^2 then the number of factors is (2+1)*(2+1)=3*3=9.

One more example: if your number is 360 = 8*9*5 = 2^3 * 3^2 * 5^1 then the number of factors is (3+1)*(2+1)*(1+1)=24.


this is just awesome. very well done.

i have some unsolicited advice for you:
step 1) drop whatever you're doing
step 2) write a textbook
step 3) resume whatever you're doing

thank you for saving us the time required to answer this ourselves. :)
Guest
 
 

Re: A nice formula for the number of factors

by Guest Thu Mar 20, 2008 3:08 am

RPurewal wrote:
David Pollack wrote:Sure, there is! It just depends on how many prime factors your number has, and how many times each one appears.

Suppose your number factors as a product p^a * q^b * .... *r^k. Then to get any factor you want you should take _up to_ a copies of p, _up to_ b copies of q, etc. and multiply them all together. The number of ways you can choose _up to_ a copies of p is (a+1) since you could choose 0 copies, 1 copy, 2 copies, ..., a copies. Likewise there are (b+1) ways to choose how many q's to include, etc.

So the number of factors for your number would be (a+1)*(b+1)*...(k+1).

For example, if your number is 441 = 3^2 * 7^2 then the number of factors is (2+1)*(2+1)=3*3=9.

One more example: if your number is 360 = 8*9*5 = 2^3 * 3^2 * 5^1 then the number of factors is (3+1)*(2+1)*(1+1)=24.


this is just awesome. very well done.

i have some unsolicited advice for you:
step 1) drop whatever you're doing
step 2) write a textbook
step 3) resume whatever you're doing

thank you for saving us the time required to answer this ourselves. :)


That explanation less the examples read more like directions to fix a pinball machine in chinese
Dlew 686
 
 

by Dlew 686 Thu Mar 20, 2008 11:40 pm

Yeah I agree.
iil-london
 
 

Prime factors ... quickest way ?

by iil-london Mon Mar 24, 2008 6:36 am

Hi there ...

what is the quickest way to find the prime factors for a number ?
How would you find the prime factors of 3841, for example ?
Does anyone know of a quick way to do it.

Thanks for the help. Appreciate it.
upa
 
 

Re: Prime factors ... quickest way ?

by upa Mon Mar 24, 2008 9:49 pm

iil-london wrote:Hi there ...

what is the quickest way to find the prime factors for a number ?
How would you find the prime factors of 3841, for example ?
Does anyone know of a quick way to do it.

Thanks for the help. Appreciate it.


I guess there is not. If anybody has I appreciate him/her for his/her brilliant idea.

Just factorize it. I know it is not easy and doesnot have factors 2, 3, 5, 7, 11, 13, 17, and 19. but 23 divides it.


3841 = 23 x 167

i guess 167 is also a prime cuz if it were not a prime it has to be divided by 2, 3, 5, 7, or son. none of them divides 167, so its a prime.
this is a tough one.
StaceyKoprince
ManhattanGMAT Staff
 
Posts: 8018
Joined: Wed Oct 19, 2005 9:05 am
Location: San Francisco
 

by StaceyKoprince Thu Mar 27, 2008 2:29 am

David - I agree, nice process. And for those of you who weren't quite sure how to follow the theory - don't worry about it! Just follow the examples :)

I don't know of a shortcut to find the complete set of prime factors for a number very quickly. I'm guessing there isn't one because one of the weird things about primes is that they pretty much defy our attempts to reduce things to typical patterns or formulas.
Stacey Koprince
Instructor
Director of Online Community
ManhattanGMAT
Guest
 
 

finding primes

by Guest Wed Jan 21, 2009 9:10 am

Not exactly a shortcut to finding the primes, but to help determine a large prime. Take the square root of the number. You only have to try the primes up through the one just larger than the square root.

In other words, sqrt 167 = 12.9... so you only have to try dividing it by the prime numbers through 13. Since none of those work, it is prime.
JonathanSchneider
ManhattanGMAT Staff
 
Posts: 477
Joined: Wed Dec 12, 2007 5:40 am
Location: Durham, NC
 

Re: is there a formula to calculate the number of factors?

by JonathanSchneider Fri Feb 13, 2009 3:49 pm

Good point - glad you added that!
zxtonizx
Course Students
 
Posts: 1
Joined: Tue Nov 22, 2011 1:45 am
 

Re: is there a formula to calculate the number of factors?

by zxtonizx Sun Jan 01, 2012 2:04 pm

Cannot tell you the time David Pollack's shortcut has saved. Thank you sir!
tim
ManhattanGMAT Staff
 
Posts: 5211
Joined: Tue Sep 11, 2007 9:08 am
Location: Southwest Airlines, seat 21C
 

Re: is there a formula to calculate the number of factors?

by tim Tue Jan 10, 2012 7:28 pm

cool
Tim Sanders
Manhattan GMAT Instructor

Follow this link for some important tips to get the most out of your forum experience:
https://www.manhattanprep.com/gmat/forums/a-few-tips-t31405.html
jp.jprasanna
Students
 
Posts: 202
Joined: Thu Nov 03, 2011 3:48 am
 

Re: is there a formula to calculate the number of factors?

by jp.jprasanna Tue May 15, 2012 12:11 pm

Hi - I undestand the below method, which gives me total factors, but is there a way I can find the numbers itself? Apart from listing them out!

One more example: if your number is 360 = 8*9*5 = 2^3 * 3^2 * 5^1 then the number of factors is (3+1)*(2+1)*(1+1)=24

Cheers
tim
ManhattanGMAT Staff
 
Posts: 5211
Joined: Tue Sep 11, 2007 9:08 am
Location: Southwest Airlines, seat 21C
 

Re: is there a formula to calculate the number of factors?

by tim Tue May 22, 2012 3:43 am

no, you just have to list them out..
Tim Sanders
Manhattan GMAT Instructor

Follow this link for some important tips to get the most out of your forum experience:
https://www.manhattanprep.com/gmat/forums/a-few-tips-t31405.html