Author 
Message 

Flofloflo
Member
Joined: 07 Nov 2007 Posts: 120

Posted: 25 Feb 2009 05:43:51 pm Post subject: 


Hello,
I've been trying to find the smallest number with the most divisors. (i.e. 15 has 3 dividers: 1,3,5,15)
Now, I had this idea to find a number that would at least approach it; by simply taking a number with a maximum amount of divisors, and doubling it enough times.
Basically I used my Ti to find these numbers:P The best I got was 315, having 12 divisors, I kept looking for better ones, but aafter a bit (I searched untill 715) it all got way too slow. So basically, I figured 80640 would be at least pretty close to the smallest number with 100 divisors.
I was wondering, is there some way of finding a number between say, 700 and 2000 with at least 13 divisors, or maybe between 700 and something like 10000 with more divisors then that?? 

Back to top 


calc84maniac
Elite
Joined: 22 Jan 2007 Posts: 770

Posted: 25 Feb 2009 06:17:17 pm Post subject: 


100=5*5*2*2
Thus 2^{51}*3^{51}*5^{21}*7^{21}=45,360 has 100 divisors.
This seems like the smallest which satisfies the conditions.
Edit:
How is 1,3,5,15 three numbers? I count four.
Last edited by Guest on 25 Feb 2009 06:19:49 pm; edited 1 time in total 

Back to top 


simplethinker snjwffl
Active Member
Joined: 25 Jul 2006 Posts: 700

Posted: 25 Feb 2009 06:23:47 pm Post subject: 


If a number's prime factorization is n=p_{1}^{a1}p_{2}^{a2}...p_{m}^{am}, then the number of divisors d(n) is the product of all the (1 + a_{m})'s. For example, 15=3^{1} * 5^{1}, so d(15)=(1+1)(1+1)=4. This means that the number of divisors depends on the exponents in its prime factorization rather than the factors, so if we find combinations of exponents that would equal 100, then we can permute them around the primes 2, 3, 5... until we find the lowest value (since 4=2^2 it can't be in the prime factorization)
As an example, let's find the smallest number with 12 divisors. 12 = 3*4 = (2+1)(3+1) = 2*2*3 = (1+1)(1+1)(2+1), so we can choose either (2, 3) or (1, 1, 2). To get the lowest number, the 3rd power should go to 2 (the smallest divisor other than one) and the second power goes to the next lowest prime, which is 3, which gives n=2^{3} * 3^{2}=72. We could also try (1, 1, 2), and by a similar argument we get 2^{2}3^{1}5^{1}=60. Since 60<72, this means that the smallest number with 12 divisors is 60, with divisors 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60.
The smallest number with 13 divisors is 4096, since 13 is prime it can only be written as 13=(12+1), so 2^12=4096.
[edit]Dang, I was beaten.
Last edited by Guest on 25 Feb 2009 06:24:32 pm; edited 1 time in total 

Back to top 


thornahawk μολών λαβέ
Active Member
Joined: 27 Mar 2005 Posts: 569

Posted: 25 Feb 2009 10:50:34 pm Post subject: 


You might wish to look at this...
thornahawk 

Back to top 


Weregoose Authentic INTJ
Super Elite (Last Title)
Joined: 25 Nov 2004 Posts: 3976

Posted: 26 Feb 2009 01:50:04 am Post subject: 


Here's the extended list, in case it's missed.
Last edited by Guest on 26 Feb 2009 01:50:15 am; edited 1 time in total 

Back to top 


Flofloflo
Member
Joined: 07 Nov 2007 Posts: 120

Posted: 26 Feb 2009 06:45:26 am Post subject: 


A, writing there are only three was pretty dumb .
But anyway, yeah, I now used my program to find something around 40.000 too (probably the same as you found), but now I really gotta see how you found it so fast
So, just to see if I get this:
15 = 3*5 = (2+1)(4+1) , I thought i'd have to rewrite the four but that seems impossible
2^4*3^2=144. Okay that seems right... And it is right according to the list (altough I understand nearly nothing from the whole OnLine Encyclopedia of Integer Sequences).
Thanks:P 

Back to top 


simplethinker snjwffl
Active Member
Joined: 25 Jul 2006 Posts: 700

Posted: 26 Feb 2009 10:20:49 am Post subject: 


Flofloflo wrote: So, just to see if I get this:
15 = 3*5 = (2+1)(4+1) , I thought i'd have to rewrite the four but that seems impossible
2^4*3^2=144. Okay that seems right... And it is right according to the list (altough I understand nearly nothing from the whole OnLine Encyclopedia of Integer Sequences).
Thanks:P
Yep. That's right A more detailed explanation of the formula for number of divisors can be found here. MathWorld is your friend! 

Back to top 


Flofloflo
Member
Joined: 07 Nov 2007 Posts: 120

Posted: 27 Feb 2009 10:44:13 am Post subject: 


Wait! I just realised the answer doesn't satisfy me.
Let's do the same thing as last time:
15 = 3^1 * 5^1, So it has (1+1)(1+1) divisors.
The reason this works is because there are four combinations to make:
3^0*5^0
3^0*5^1
3^1*5^0
3^1*5^1
That's why I think there are four divisors, that's correct right?
So how can I be 100% sure that for example 3^1*5^0 isn't the same as one of the others that I consider divisors? Maybe there are doubles!
Can that be proven too? 

Back to top 


simplethinker snjwffl
Active Member
Joined: 25 Jul 2006 Posts: 700

Posted: 27 Feb 2009 01:32:48 pm Post subject: 


Flofloflo wrote: So how can I be 100% sure that for example 3^1*5^0 isn't the same as one of the others that I consider divisors? Maybe there are doubles!
Can that be proven too?
Look at that link I gave you;) 

Back to top 


Flofloflo
Member
Joined: 07 Nov 2007 Posts: 120

Posted: 27 Feb 2009 04:05:34 pm Post subject: 


Okay, I read it all, took some time to figure out what d' meant
I gotta gotta check it out some more to see if this actually proofs that there cant be any doubles in there; it's not really obvious yet to me . But I understood everything untill the geometric mean part, I dunno if that's important, but I don't think it has anything to do with my question, so I guess I'm not gonna bother with it (yet). 

Back to top 


simplethinker snjwffl
Active Member
Joined: 25 Jul 2006 Posts: 700

Posted: 27 Feb 2009 06:48:20 pm Post subject: 


Every number has a distinct prime factorization, and any product of powers of primes corresponds to a single number. If you have a number n=a^{2}b^{1}, then the factors are a^{0}b^{0} a^{1}b^{0}, a^{2}b^{0}, a^{0}b^{1}, a^{1}b^{1}, a^{2}b^{1} which are all distinct. The fact that the number are prime guarantees that this is so (if you write something as 2^{a}4^{b} then it's a different story) 

Back to top 


