mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2006-02-06, 21:41   #1
Citrix
 
Citrix's Avatar
 
Jun 2003

110001100012 Posts
Default 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!
Citrix is offline   Reply With Quote
Old 2006-02-06, 22:18   #2
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

503 Posts
Default

Try figuring it out. It's easy.
grandpascorpion is offline   Reply With Quote
Old 2006-02-07, 00:20   #3
marc
 
marc's Avatar
 
Jun 2004
UK

139 Posts
Default

For a power of a prime f(p**n) = n+1 and f is multiplicative. Easy peasy.
marc is offline   Reply With Quote
Old 2006-02-07, 00:36   #4
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

22·3·7·139 Posts
Default

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.
ewmayer is offline   Reply With Quote
Old 2006-02-07, 00:39   #5
Citrix
 
Citrix's Avatar
 
Jun 2003

5×317 Posts
Default

You forgot 1
Citrix is offline   Reply With Quote
Old 2006-02-07, 01:16   #6
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

3·373 Posts
Default

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.
philmoore is offline   Reply With Quote
Old 2006-02-07, 03:10   #7
Citrix
 
Citrix's Avatar
 
Jun 2003

110001100012 Posts
Default

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!
Citrix is offline   Reply With Quote
Old 2006-02-07, 20:45   #8
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

266348 Posts
Default

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.
ewmayer is offline   Reply With Quote
Old 2006-02-08, 02:11   #9
Citrix
 
Citrix's Avatar
 
Jun 2003

5·317 Posts
Default

Thanks for responding, but I never said the divisors had to be proper.
Citrix is offline   Reply With Quote
Old 2006-02-08, 04:05   #10
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

3×373 Posts
Default

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.
philmoore is offline   Reply With Quote
Old 2006-02-08, 04:09   #11
mfgoode
Bronze Medalist
 
mfgoode's Avatar
 
Jan 2004
Mumbai,India

22·33·19 Posts
Lightbulb 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
mfgoode is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Question about Mersenne divisors paulunderwood Miscellaneous Math 1 2016-01-24 01:41
Finding all divisors kn + 1 of P(n) for various polynomials P Drdmitry Computer Science & Computational Number Theory 0 2014-11-28 14:51
Looking for fermat divisors, n=90-120 firejuggler Prime Sierpinski Project 2 2012-01-10 17:14
Fermat number and Modulo for searching divisors CyD Factoring 4 2011-05-31 11:24
Odds a largish number has N divisors? grandpascorpion Math 65 2006-02-16 15:20

All times are UTC. The time now is 02:08.


Fri Dec 3 02:08:35 UTC 2021 up 132 days, 20:37, 2 users, load averages: 1.16, 1.07, 1.02

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.