Results 1 to 4 of 4

Thread: The maximum number of divisors

  1. #1

    Thread Starter
    Addicted Member
    Join Date
    Oct 2013
    Posts
    212

    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.

  2. #2
    Only Slightly Obsessive jemidiah's Avatar
    Join Date
    Apr 2002
    Posts
    2,431

    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.

  3. #3

    Thread Starter
    Addicted Member
    Join Date
    Oct 2013
    Posts
    212

    Re: The maximum number of divisors

    This is not just an answer, but a course in itself.
    Thanks a lot, jemidiah.

  4. #4

    Thread Starter
    Addicted Member
    Join Date
    Oct 2013
    Posts
    212

    Re: The maximum number of divisors

    Duplicate removed.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Click Here to Expand Forum to Full Width