20060206, 21:41  #1 
Jun 2003
2×7×113 Posts 
Number of divisors of n?
Given a number n and it's factorization how do you calculate the number of divisors. I know if all factors are distinct, ie. number n is square free then number of divisors =2^#of factors.
Please provide the formula. Thanks! 
20060206, 22:18  #2 
Jan 2005
Transdniestr
503 Posts 
Try figuring it out. It's easy.

20060207, 00:20  #3 
Jun 2004
UK
139 Posts 
For a power of a prime f(p**n) = n+1 and f is multiplicative. Easy peasy.

20060207, 00:36  #4  
∂^{2}ω=0
Sep 2002
República de California
19·613 Posts 
Quote:


20060207, 00:39  #5 
Jun 2003
2×7×113 Posts 
You forgot 1

20060207, 01:16  #6 
"Phil"
Sep 2002
Tracktown, U.S.A.
3·373 Posts 
It even took Mersenne awhile to figure this one out, so don't feel bad if you don't get it right away. Try the example of 48, and you'll probably see the pattern.

20060207, 03:10  #7 
Jun 2003
11000101110_{2} Posts 
Thanks, I figured it out. It wasn't hard, just me being lazy.
Q2)This is kind of hard for me. How many numbers under 2^n are composed of factors that are under n? What is the formula? Thanks! 
20060207, 20:45  #8 
∂^{2}ω=0
Sep 2002
República de California
19·613 Posts 
Ah, I was confusing my proper factors and proper divisors. And it seems this discussion is not about either, since "proper divisors" includes 1 but excludes n, e.g. 6 has 3 of those (but 1,2,3 rather than 2,3,6 as I stated initially.) What do I know, I usually only give a rat's a** about the *prime* divisors.

20060208, 02:11  #9 
Jun 2003
2·7·113 Posts 
Thanks for responding, but I never said the divisors had to be proper.

20060208, 04:05  #10 
"Phil"
Sep 2002
Tracktown, U.S.A.
1119_{10} Posts 
Your second question is hard. I think you are asking how many numbers less than 2^n are "n smooth", is that correct? The Dickson function gives the probability that a number is smooth, so you are looking for an integral of it, but the Dickson function is already computed by numerical integration, so I doubt that there is any convenient closed form for the expression you want.

20060208, 04:09  #11  
Bronze Medalist
Jan 2004
Mumbai,India
2^{2}×3^{3}×19 Posts 
Number of divisors of n?
Quote:
The number of factors of any number that has a prime factor representation of: p_1^n_1 * p_2^n_2......p_r^n_r where p_1,p_2,....p_r are it's prime factors and n_1,n_2,...n_r are their respective exponents, is: (n_1+1)*(n_2+1)*.....(n_r+1). This includes 1 and the number itself, so you can remove those two if you do not wish to count them. So for 2^6×3^5×5^3×7^2×11×13×17×19×23×29×31×37×41×43×47 the total number of factors would be: 7*6*4*3*2^11 = 1,032,192 It is easy to see why the number of factors follows the relation given above. Note that each factor can have p_i in it from 0 to n_i times for a total of (n_i +1). See C&P ch. 1 for more details.  Last edited by garo : 28 Dec 05 at 12:01 AM. Reason: typos Mally 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Question about Mersenne divisors  paulunderwood  Miscellaneous Math  1  20160124 01:41 
Finding all divisors kn + 1 of P(n) for various polynomials P  Drdmitry  Computer Science & Computational Number Theory  0  20141128 14:51 
Looking for fermat divisors, n=90120  firejuggler  Prime Sierpinski Project  2  20120110 17:14 
Fermat number and Modulo for searching divisors  CyD  Factoring  4  20110531 11:24 
Odds a largish number has N divisors?  grandpascorpion  Math  65  20060216 15:20 