 mersenneforum.org > Math Number of divisors of n?
 Register FAQ Search Today's Posts Mark Forums Read 2006-02-06, 21:41 #1 Citrix   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!   2006-02-06, 22:18 #2 grandpascorpion   Jan 2005 Transdniestr 7678 Posts Try figuring it out. It's easy.   2006-02-07, 00:20 #3 marc   Jun 2004 UK 139 Posts For a power of a prime f(p**n) = n+1 and f is multiplicative. Easy peasy.   2006-02-07, 00:36   #4
ewmayer
2ω=0

Sep 2002
República de California

2×3×29×67 Posts Quote:
 Originally Posted by Citrix 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.
Uh...6 has prime divisors 2 and 3, and thus has proper divisors 2,3,6, which number 3, not 22.   2006-02-07, 00:39 #5 Citrix   Jun 2003 2×7×113 Posts You forgot 1   2006-02-07, 01:16 #6 philmoore   "Phil" Sep 2002 Tracktown, U.S.A. 21378 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.   2006-02-07, 03:10 #7 Citrix   Jun 2003 2×7×113 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!   2006-02-07, 20:45 #8 ewmayer ∂2ω=0   Sep 2002 República de California 2×3×29×67 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.   2006-02-08, 02:11 #9 Citrix   Jun 2003 2×7×113 Posts Thanks for responding, but I never said the divisors had to be proper.    2006-02-08, 04:05 #10 philmoore   "Phil" Sep 2002 Tracktown, U.S.A. 45F16 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.   2006-02-08, 04:09   #11
mfgoode
Bronze Medalist

Jan 2004
Mumbai,India

22·33·19 Posts Number of divisors of n?

Quote:
 Originally Posted by Citrix 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! Allow me to quote Garo's post no. 228 in 'Special Whole numbers' as a reply to my query on the same subject.

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 Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post paulunderwood Miscellaneous Math 1 2016-01-24 01:41 Drdmitry Computer Science & Computational Number Theory 0 2014-11-28 14:51 firejuggler Prime Sierpinski Project 2 2012-01-10 17:14 CyD Factoring 4 2011-05-31 11:24 grandpascorpion Math 65 2006-02-16 15:20

All times are UTC. The time now is 04:36.

Fri Oct 22 04:36:27 UTC 2021 up 90 days, 23:05, 1 user, load averages: 1.20, 1.24, 1.38