Find the number in the range 1 to 100 that has the most divisors [closed]

Question

How to find the smallest number in the the range 1 to 100 that has the most divisors? I know a trivial way would be to check the divisors of each number from 1 upto 100 and keep track of the number having maximum divisor. But is there an more efficient way?

Answer 1

For smallish bounds, using a sieve would be my good enough. From the fact

         r                   r
(1)  n = ∏ p_k^e_k => τ(n) = ∏ (e_k + 1)
        k=1                 k=1

it is clear that the number of divisors can easily be determined from the prime factorisation of n, and that τ(m*n) = τ(m) * τ(n) if gcd(m,n) = 1 (i.e. τ is a multiplicative function).

So we can cheaply compute τ(n) if we know any prime factor of n and all τ(m) for 1 <= m < n. Thus

int sieve[limit+1];
// initialise sieve
for(int i = 0; i <= limit; ++i) {
    sieve[i] = i;
}
// find a prime factor for all numbers > 1
int root = sqrt(limit); // limit is supposed to be not too large, so no fixup needed here
for(int p = 2; p <= root; ++p) {
    if (sieve[p] == p) {
        // this means p is prime, mark multiples
        for(int m = p*p; m <= limit; m += p) {
            sieve[m] = p;
        }
}
// Now sieve[n] is a prime factor of n
int p;
for(int n = 2; n <= limit; ++n) {
    if ((p = sieve[n]) == n) {
        // a prime, two divisors
        sieve[n] = 2;
    } else {
        // count the multiplicity of p in n and find the cofactor of p^multiplicity
        int m = 1, q = n;
        do {
            q /= p;
            ++m;
        }while(q % p == 0);
        sieve[n] = m*sieve[q];
    }
}
// Now sieve[n] contains τ(n), the number of divisors of n, look for the maximum
int max_div = 0, max_num = 0;
for(int n = 1; n <= limit; ++n) {
    if (sieve[n] > max_div) {
        max_div = sieve[n];
        max_num = n;
    }
}

finds the smallest number with the largest divisor count not exceeding N in O(N*log log N) time, with a relatively small constant factor (that could be reduced further by treating 2 separately and only marking odd multiples of odd primes).

That is a simple brute-force method that is fast enough for small N (the interpretation of "small" depends on the notion of "fast enough", could be <= 1000 or <= 1000000 for example).

For larger bounds, that is too slow and too memory intensive. For those, we need to do a bit more analysis.

From (1), we can deduce that among all numbers with the same structure of the prime factorisation (meaning the same number r of distinct prime factors, and the same multiset of exponents, but possibly in different order), that all have the same number of divisors, the smallest is the one where

• the prime factors are the r smallest primes
• the exponents appear in descending order (2 has the largest exponent, 3 the next largest, ...)

So we can find the smallest number with the most divisors <= N by considering all finite sequences

e_1 >= e_2 >= ... >= e_r > 0

with the property

                         r
N/2 < n(e_1, ..., e_r) = ∏ p_k^e_k <= N
                        k=1

and the sought number is one of the n(e_1, ..., e_r) produced by them. (If n(e_i) <= N/2 for a monotonic non-increasing finite sequence, the sequence with 1 added to e_1 would produce a number <= N with more divisors.)

The largest divisor count is produced for exponents that are roughly proportional to 1/log p_k. More precisely, for a fixed r, let

                   r
T(x_1, ..., x_r) = ∏ (x_k+1)
                  k=1

                   r
F(x_1, ..., x_r) = ∏ p_k^x_k
                  k=1

Then T assumes its maximal value on the set { x : F(x) = N and x_k > 0 for all k } in the point with

               r
x_k = (log N + ∑ log p_k)/(r * log p_k) - 1
              k=1

We only admit integer exponents, which complicates the matter, but straying too far from the proportionality produces numbers with fewer divisors than we find near the proportionality.

Let's illustrate it for N = 100000 (it's a bit too small to really exploit the proportionality, but small enough to completely do by hand):

1. r = 1: e_1 = 16, n(16) = 2^16 = 65536 has 17 divisors.

2. r = 2: Setting x_2 = x_1 * log 2 / log 3 and N = 2^x_1 * 3^x_2 = 2^(2*x_1), we obtain x_1 ≈ 8.3, x_2 ≈ 5.24. Now let's see what happens with e_1, e_2 close to x_1, x_2.

   2^7 *3^6 = 93312, τ(2^7 *3^6) =  (7+1)*(6+1) = 56
   2^8 *3^5 = 62208, τ(2^8 *3^5) =  (8+1)*(5+1) = 54
   2^10*3^4 = 82944, τ(2^10*3^4) = (10+1)*(4+1) = 55
   

   straying farther away from the proportionality reduces the divisor count quickly,

   2^11*3^3 = 55296, τ(2^11*3^3) = (11+1)*(3+1) = 48
   2^13*3^2 = 73728, τ(2^13*3^2) = (13+1)*(2+1) = 42
   2^15*3^1 = 98304, τ(2^15*3^1) = (15+1)*(1+1) = 32
   

   So the closest pair to the proportionality didn't produce the largest divisor count, but the ones with the large divisor counts were the closest three.

3. r = 3: Similarly, we obtain x_1 ≈ 5.5, x_2 ≈ 3.5, x_3 ≈ 2.4

   2^4 *3^3*5^3 = 54000, τ(2^4 *3^3*5^3) =  5*4*4 = 80
   2^5 *3^4*5^2 = 64800, τ(2^5 *3^4*5^2) =  6*5*3 = 90
   2^7 *3^3*5^2 = 86400, τ(2^7 *3^3*5^2) =  8*4*3 = 96
   2^8 *3^2*5^2 = 57600, τ(2^8 *3^2*5^2) =  9*3*3 = 81
   2^6 *3^5*5^1 = 77760, τ(2^6 *3^5*5^1) =  7*6*2 = 84
   2^7 *3^4*5^1 = 51840, τ(2^7 *3^4*5^1) =  8*5*2 = 80
   2^9 *3^3*5^1 = 69120, τ(2^9 *3^3*5^1) = 10*4*2 = 80
   2^11*3^2*5^1 = 92160, τ(2^11*3^2*5^1) = 12*3*2 = 72
   2^12*3^1*5^1 = 61440, τ(2^12*3^1*5^1) = 13*2*2 = 52
   

   again, the large divisor counts are achieved for exponents close to the proportionality.

4. r = 4: The rough approximations to the exponents are x_1 ≈ 4.15, x_2 ≈ 2.42, x_3 ≈ 1.79, x_4 ≈ 1.48. For e_4 = 2, there is only one choice,

   2^3*3^2*5^2*7^2 = 88200, τ(2^3*3^2*5^2*7^2) = 4*3*3*3 = 108
   

   For e_4 = 1, we have a few more choices:

   2^4*3^3*5^2*7^1 = 75600, τ(2^4*3^3*5^2*7^1) =  5*4*3*2 = 120
   2^5*3^2*5^2*7^1 = 50400, τ(2^5*3^2*5^2*7^1) =  6*3*3*2 = 108
   2^5*3^4*5^1*7^1 = 90720, τ(2^5*3^4*5^1*7^1) =  6*5*2*2 = 120
   2^6*3^3*5^1*7^1 = 60480, τ(2^6*3^3*5^1*7^1) =  7*4*2*2 = 112
   2^8*3^2*5^1*7^1 = 80640, τ(2^8*3^2*5^1*7^1) =  9*3*2*2 = 108
   2^9*3^1*5^1*7^1 = 53760, τ(2^9*3^1*5^1*7^1) = 10*2*2*2 =  80
   

5. r = 5: x_1 ≈ 3.3, x_2 ≈ 2.1, x_3 ≈ 1.43, x_4 ≈ 1.18, x_5 ≈ 0.96. Since 2*3*5*7*11 = 2310, the exponents of 7 and 11 must be 1, we find the candidates

   2^2*3^2*5^2*7*11 = 69300, τ(2^2*3^2*5^2*7*11) = 3*3*3*2*2 = 108
   2^3*3^3*5^1*7*11 = 83160, τ(2^3*3^3*5^1*7*11) = 4*4*2*2*2 = 128
   2^4*3^2*5^1*7*11 = 55440, τ(2^4*3^2*5^1*7*11) = 5*3*2*2*2 = 120
   2^6*3^1*5^1*7*11 = 73920, τ(2^6*3^1*5^1*7*11) = 7*2*2*2*2 = 112
   

6. r = 6: Since 2*3*5*7*11*13 = 30030, there is only one candidate here,

   2^2*3*5*7*11*13 = 60060, τ(60060) = 3*2^5 = 96
   

   and that produces a smaller divisor count than the best candidates using four or five primes.

So we investigated 28 candidates (and could have skipped several of them) to find that the smallest number <= 100000 with the most divisors is 83160 (98280 is the other number below 100000 with 128 divisors).

Here's a programme that finds the smallest number with the most divisors not exceeding a given limit < 2^64 practically instantaneously (no attempts at short-cutting have been made since it's fast enough as is for 64-bit integers, for arbitrary precision integers, that would become worthwhile at some point):

#include <stdlib.h>
#include <stdio.h>

typedef struct {
    unsigned long long number;
    unsigned long long divisors;
} small_max;

static const unsigned long long primes[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 };
static const unsigned long long primorials[] =
    { 2, 6, 30, 210, 2310, 30030, 510510, 9699690, 223092870, 6469693230,
      200560490130, 7420738134810, 304250263527210, 13082761331670030,
      614889782588491410 };

static const unsigned num_primes = sizeof primorials / sizeof primorials[0];

small_max max_divisors(unsigned long long limit);
small_max best_with(unsigned long long limit, unsigned index, unsigned multiplicity);
void factor(unsigned long long number);

int main(int argc, char *argv[]) {
    unsigned long long limit;
    limit = argc > 1 ? strtoull(argv[1],NULL,0) : 100000;
    small_max best = max_divisors(limit);
    printf("\nSmallest number not exceeding %llu with most divisors:\n",limit);
    printf("%llu with %llu divisors\n", best.number, best.divisors);
    factor(best.number);
    return 0;
}

small_max max_divisors(unsigned long long limit) {
    small_max result;
    if (limit < 3) {
        result.number = limit;
        result.divisors = limit;
        return result;
    }
    unsigned idx = num_primes;
    small_max best = best_with(limit,0,1);
    printf("Largest power of 2: %llu = 2^%llu\n", best.number, best.divisors-1);
    for(idx = 1; idx < num_primes && primorials[idx] <= limit; ++idx) {
        printf("Using primes to %llu:\n", primes[idx]);
        unsigned long long test = limit, remaining = limit;
        unsigned multiplicity = 0;
        do {
            ++multiplicity;
            test /= primorials[idx];
            remaining /= primes[idx];
            result = best_with(remaining, idx-1, multiplicity);
            for(unsigned i = 0; i < multiplicity; ++i) {
                result.number *= primes[idx];
            }
            result.divisors *= multiplicity + 1;
            if (result.divisors > best.divisors) {
                printf("New largest divisor count: %llu for\n  ", result.divisors); 
                factor(result.number);
                best = result;
            } else if (result.divisors == best.divisors && result.number < best.number) {
                printf("Smaller number with %llu divisors:\n  ", result.divisors); 
                factor(result.number);
                best = result;
            }
        }while(test >= primorials[idx]);
    }
    return best;
}

small_max best_with(unsigned long long limit, unsigned index, unsigned multiplicity) {
    small_max result = {1, 1};
    if (index == 0) {
        while(limit > 1) {
            result.number *= 2;
            ++result.divisors;
            limit /= 2;
        }
        return result;
    }
    small_max best = {0,0};
    unsigned long long test = limit, remaining = limit;
    --multiplicity;
    for(unsigned i = 0; i < multiplicity; ++i) {
        test /= primorials[index];
        remaining /= primes[index];
    }
    do {
        ++multiplicity;
        test /= primorials[index];
        remaining /= primes[index];
        result = best_with(remaining, index-1, multiplicity);
        for(unsigned i = 0; i < multiplicity; ++i) {
            result.number *= primes[index];
        }
        result.divisors *= multiplicity + 1;
        if (result.divisors > best.divisors) {
            best = result;
        } else if (result.divisors == best.divisors && result.number < best.number) {
            best = result;
        }
    }while(test >= primorials[index]);
    return best;
}

void factor(unsigned long long number) {
    unsigned long long num = number;
    unsigned idx, mult;
    printf("%llu =", number);
    for(idx = 0; num > 1 && idx < num_primes; ++idx) {
        mult = 0;
        while(num % primes[idx] == 0) {
            num /= primes[idx];
            ++mult;
        }
        printf("%s %llu ^ %u", idx ? " *" : "", primes[idx], mult);
    }
    printf("\n");
}

Answer 2

For each number from 1 to 100 you can check all of it's multiples and add the number of divisors. Depending on how you are checking the divisors of each number, it can be more efficient. Here is a python code that does this idea. The complexity is O(N log N)

count=[0]*101
for i in xrange(1,101):
  for j in xrange(1,100/i+1):
    count[i*j]+=1

print max(zip(count,xrange(101))) 

And here is the code in C

int i,j,count[101];
for(i=1;i<=100;i++) for(j=1;j<=100/i;j++) count[i*j]++;
int max=-1,pos;
for(i=1;i<=100;i++) if(count[i]>=max){
   max=count[i];
   pos=i;
}
printf("%d has %d divisors\n",pos,max);

Both versions keep the maximum number out of all the numbers with maximum divisors. In this case 96 has 12 divisors.