-
Apr 12th, 2014, 06:10 AM
#1
Thread Starter
Addicted Member
The maximum number of divisors
In this problem all numbers are integers.
In the range [1 - 100], find the number, or numbers, that have the maximum number of divisors.
Example:
-Divisors of 5 are: 1-5. The number of divisors is 2.
-Divisors of 6 are: 1-2-3-6. The number of divisors is 4.
Then 6 is the number that has the maximum number of divisors.
-
Apr 12th, 2014, 01:07 PM
#2
Re: The maximum number of divisors
Let D(n) denote the number of divisors of n. Our first goal is to show D is "multiplicative". That is, suppose n and m are relatively prime. We'll show D(nm) = D(n)D(m).
If d divides n and d' divides m, then certainly dd' divides nm. This gives us a way to translate from pairs of divisors (d, d') of n, m to a divisor of nm. To get D(n)D(m) = D(nm), we'll show this translation is invertible. Indeed, say f divides nm. Thinking in terms of prime factorizations, this says we can split f up into two pieces, d and d', where we make d out of the prime factors of f which are also prime factors of n, and we make d' out of the prime factors of f which are also prime factors of m. (This is the step that uses the assumption that n and m are relatively prime.) Hence f = dd' and d divides n, d' divides m. It's easy to check that this gives us the inverse to the first operation.
Our second goal is to compute D(p^k) for prime p and k>=1. This is easy: the divisors are just 1, p, p^2, ..., p^k, giving (k+1) in all.
Putting these formulas together, suppose N has prime factorization p1^a1 ... pn^an. Then
D(N)
= D(p1^a1 ... + pn^an)
= D(p1^a1)*...*D(pn^an)
= (a1+1)*...*(an+1)
So, to maximize D, find numbers whose prime factorizations' exponents maximize this quantity. [You can also jump straight to this formula by considering divisors' prime factorizations, but multiplicative functions are common, so I figured I would go that route.]
One strategy for maximizing this quantity is to make a1 large using powers of 2, and to add single copies of other distinct primes to multiply the large term from a1 as much as possible. This suggests considering N=2^2 * 3 * 5=60, which has 3*2*2=12 divisors. Is this as good as possible?
Since 3*5*7 = 105 > 100, any *odd* 1 <= N <= 100 has at most two prime factors, so D(N) = (a1+1)*(a2+1) (allow a1 or a2=0 if N has fewer than 2 prime factors). Since 3^5 > 100, a1 and a2 <= 4. Indeed, if a1=4, we're forced to have 3^4 = 81 in N's factorization, since 5^4 > 100, but then we can't have any other prime factors; since this doesn't beat 12 divisors, take a1 and a2 <= 3. We can't have a1=a2=3 since 3^3*5^3 > 100, or even a1=3, a2=2 since 3^5*5^2 > 100. Hence (a1+1)(a2+1) <= (2+1)(2+1) = 9 in the remaining cases, which again doesn't beat 12 divisors.
Now consider even 1 <= N <= 100. Consider cases based on the exponent of 2 in N's prime factorization.
6: 2^6 = 64 has 7 < 12 divisors
5: 2^5 = 32 has 6 divisors, 2^5*3 = 96 has 6*2=12 divisors [tied with N=60]
4: 2^4 = 16 has 5 divisors, 2^4*3 = 48 has 5*2=10 divisors, 2^4*5 = 90 has 5*2=10 divisors, 2^4*7 > 100; no others.
3: 2^3 = 8: easiest to just look at multiples of 8 not already considered, i.e. multiples of 8 that aren't multiples of 16, namely 8, 24, 40, 56, 72, 88, which are 2^3, 2^3*3, 2^3*5, 2^3*7, 2^3*3^2, 2^3*11 and which have 4, 4*2=8, 4*2=8, 4*2=8, 4*3=12 [tied with N=60], 4*2=8 divisors.
2: 2^2 = 4: 100/4 = 20; we'll have 1 <= N/2^2 <= 25; maximize the problem with an upper bound of 25 for odd values; 3*5 and 3*7 are the answer; 2^2 * 3 * 5 = 60 was found above, 2^2 * 3 * 7 = 84 [tied with N=60].
1: maximize the problem with an upper bound of 50 for odd values as in the previous case; 3^3 = 27, 3^2*5 = 45 win, giving 2*3^3 = 54 and 2*3^2*5 = 90 with 2*4 and 2*3*2=12 [tied with N=60] divisors.
In all, 90, 60, 72, 84, 96 all have 12 divisors. Or, you could just do
[n for n in range(1, 101) if len(divisors(n)) >= 12]
in Sage, which returns the above list instantly.
Last edited by jemidiah; Apr 12th, 2014 at 03:44 PM.
The time you enjoy wasting is not wasted time.
Bertrand Russell
<- Remember to rate posts you find helpful.
-
Apr 12th, 2014, 01:44 PM
#3
Thread Starter
Addicted Member
Re: The maximum number of divisors
This is not just an answer, but a course in itself.
Thanks a lot, jemidiah.
-
Apr 12th, 2014, 01:56 PM
#4
Thread Starter
Addicted Member
Re: The maximum number of divisors
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|