How to calculate smallest number with certain number of divisors?

Question

From Project Euler problem 500

The number of divisors of 120 is 16. In fact 120 is the smallest number having 16 divisors.

Find the smallest number with 2**500500 divisors. Give your answer modulo 500500507.

It's simple enough to count the divisors of n, eg. in Python len([i for i in range(1,n+1) if n % i == 0]). This is O(n).

I tried brute force search and found the smallest number with 32 divisors is 840, but it's much too slow for the problem above. From the inequality count_divisors(n) <= n, the number is going to be massive.

What do you think? Any ideas? How to calculate smallest number with certain number of divisors?

---

Edit: I don't think this is a duplicate. This question is more specific, it concerns a particular class of much larger numbers. The other question asks generally. Its answers aren't applicable to this problem, it's a different magnitude.

Vastah

[Check this ][1]. [1]: #8862494 – Ali

How about directly constructing the number by adding the smallest divisors, and stoping when arrived to 16, 32... // 1: 1 = 1 // 2 : 1*2 = 2 // 3: 1*2*2 = 4 // ... – Underpinning

The first answer in MrocKK's link is useful, although hard to understand. A better source may be here: you can calculate the number of divisors directly from the prime factorization of the number. Since you're looking for exactly a power of 2 divisors, this tells you that every prime factor in your answer must occur one less than a power of 2. – Diffluent

@EmmanuelJay that will not work because for number of divisors d0<d1 are the value of n=LCM(all divisors) not only increasing ... for example for d=5 divisors the lowest n=16 and for d=6 divisors lowest n=12 !!! – Basswood

Fun fact: the puzzle asks for the answer modulo 500500507 (which saves time typing it) but in full it's 3078556 digits long. – Vastah

Answer 1

You should use the formula for the number of divisors of integer n:

d(n) = (a₁+1)(a₂+1)...(a_k+1)

where

n = p₁^a₁ * p₂^a₂ *p₃^a₃ *...*p_k^a_k

is a unique representation of every integer through powers of its prime divisors. This is a well-known formula, but if one wonders how to get it, note that d divides n if and only if d is of the form p₁^x₁ * p₂^x₂ *p₃^x₃ *...*p_k^x_k, where each of x_i is between 0 and a_i, so there are a_i + 1 possibilities for choosing each of x_i. Now just apply the product rule and you get the desired formula.

For fixed d(n) (as in your case), the minimum value of n is obviously obtained by carefully selecting powers of existing primes, or by adding new primes. Let's work through this simple example, 16:

d(x) = (a₁+1)(a₂+1)...(a_k+1) = 16 = 2⁴.

This means that you have at most 4 different primes, therefore:

x = 2^a₁ * 3^a₂ *5^a₃ * 7^a₄

where a_i >= 0. The question is now - in order to get minimum value of x, is it better to increase the powers of 2 (i.e., increment a₁), or to use 7 (i.e. take a₄=1 instead of a₄=0)? Well, it's simple to check, 2*3*5*7 > 2³ * 3 * 5 = 120, that's why the 120 is answer in this case.

How to generalize this approach? You should create min-heap where you'll put the powers of primes, taking care that the number of divisors reaches the specified value. In case of 16, this min-heap would contain numbers 2, 3, 5, 7, 2², 3², 2⁴ etc. Why? Because 16 = 2⁴, so each of (a_i+1) has to divide 16, i.e. it has to be power of 2. Every time when you add new power, it should increase the left hand side (i.e., the variable d(x)) by power of 2, since your final goal is to find the smallest number with 2⁵⁰⁰⁵⁰⁰ divisors. Heap is initialized with first k primes (in the problem statement, k = 500500), and in each step, when you pop p^x from the heap, p^2x is returned and result is multiplied by p^x. Step-by-step solution for d(x) = 16 = 2⁴:

Step    Heap    d(x)    x
==========================
0      2,3,5,7    1     1
1      3,4,5,7    2     2
2      4,5,7,9    4     6
3      5,7,9,16   8     24
4      7,9,16,25  16    120

HTH.

Barite

Neat! You explain well. That's exactly how I calculated it, with a min-heap. – Vastah

This is only a half of the problem for larger d(n), I believe. The other half is in the meat of choosing the powers of primes. – Ineffectual

@Ineffectual That's not a big issue. Start with a min-heap full of primes which you will get with e.g. Sieve of Eratosthenes. Once when you pop a power of prime from the min-heap, push the square of that power back to the heap. It is the only way to keep d(x) power of 2. – Barite

Hm, even though I get the overall idea, I don't quite understand the part after "How to generalize this approach". How exactly is the heap initialized, how is it updated, when does the updating stop and why would this procedure produce the right answer?! I guess I need to think some more. – Ehling

@Ehling Added a step-by-step example in the answer, hope it is clear now. – Barite

Yes, I just realized myself that it works by some thinking and by some efforts with paper and pencil. IMHO it was just too cryptic before. Now it's much better. Thanks a lot. – Ehling

@Ehling Glad that is more understandable now. You are welcome. – Barite

Answer 2

Not full answer some hints instead:

1. the max integer divisor of n is n/2

   so no need to check all divisors up to n

2. can use prime decomposition

   max prime divisor is sqrt(n) so no need to test up to n instead test up to sqrt(n) or up to number than has half of the n bits

   m=(2^(ceil(ceil(log2(n))/2)+1))-1
   

   that should speed up things a bit but you need to add the computation of non prime divisors

3. this looks like some kind of series (prime decomposition)

   divisors  | prime_divisors | non_prime_divisors              | LCM(all divisors)
   1         | 1               |                                 | 1
   2         | 1,2             |                                 | 2
   3         | 1,2             | 4                               | 4
   4         | 1,2,3           | 6                               | 6
   5         | 1,2             | 4,8,16                          | 16
   6         | 1,2,3           | 4,6,12                          | 12
   7         | 1,2             | 4,8,16,32,64                    | 64
   8         | 1,2,3           | 4,6,8,12,24                     | 24
   ...
   16        | 1,2,3,5        |4,6,8,10,12,15,20,24,30,40,60,120 | 120
   

   so try to find the equation that generates this order and then simply compute the n-th iteration in modulo arithmetics (simple PI operation ... modmul). I can see the even and odd elements have separate equation ...

[edit1] decomposition up to 16 divisors

  1:    1
  2:    1,   2
  3:    1,   2,   4
  4:    1,   2,   3,   6
  5:    1,   2,   4,   8,  16
  6:    1,   2,   3,   4,   6,  12
  7:    1,   2,   4,   8,  16,  32,  64
  8:    1,   2,   3,   4,   6,   8,  12,  24
  9:    1,   2,   3,   4,   6,   9,  12,  18,  36
 10:    1,   2,   3,   4,   6,   8,  12,  16,  24,  48
 11:    1,   2,   4,   8,  16,  32,  64, 128, 256, 512,1024
 12:    1,   2,   3,   4,   5,   6,  10,  12,  15,  20,  30,  60
 13:    1,   2,   4,   8,  16,  32,  64, 128, 256, 512,1024,2048,4096
 14:    1,   2,   3,   4,   6,   8,  12,  16,  24,  32,  48,  64,  96, 192
 15:    1,   2,   3,   4,   6,   8,   9,  12,  16,  18,  24,  36,  48,  72, 144
 16:    1,   2,   3,   4,   5,   6,   8,  10,  12,  15,  20,  24,  30,  40,  60, 120

Basswood

"so try to find the equation that generates this order". That's kind of the point. I think the only time efficient approach uses the formula for the number of divisors. – Diffluent

@Diffluent yep I agree ... checked answer is the way (it was added while I was writing this) – Basswood

Slight correction: max integer divisor of n is indeed n/2, but max prime integer divisor is sqrt(n) [ and of course you should check p*p <= n, not p < sqrt(n) ] – Plop

@AdrianRedgers yes and the answer state it too (bullet #2) However I often use half of bits instead of sqrt(n) or p*p tests ... – Basswood

Answer 3

Here is the high level gist of my Javascript - where factorCount represents the number of divisors:

• Find the prime factor decomposition of the factorCount
• Generate every unique combination of these prime factors
• For each combination, extract these combination values from the original prime factor array and add one value to this array that is the extracted values multiplied together. Then sort elements in descending order.
• For each array created by the previous step, check which yields the minimal number when computing 2^(b1-1)*3^(b2-1)5^(b3-1)...
• This minimum number computed is the smallest number with factorCount number of divisors

Here's a high level code breakdown of my JavaScript functions:

var primeFactors = findPrimeFactors(factorCount);
var primeFactorCombinations = removeDuplicateArrays(generateCombinations(primeFactors, 1));
var combinedFactorCandidates = generateCombinedFactorCombinations(primeFactors, primeFactorCombinations);
var smallestNumberWithFactorCount = determineMinimumCobination(combinedFactorCandidates);

---

And here's the full sha-bang:

function smallestNumberByFactorCount(factorCount) {

  function isPrime(primeCandidate) {
    var p = 2;
    var top = Math.floor(Math.sqrt(primeCandidate));
    while(p<=top){
      if(primeCandidate%p === 0){ return false; }
      p++;
    }
    return true;
  }

  function findPrimeAfter(currentPrime) {
    var nextPrimeCandidate = currentPrime + 1
    while(true) {
      if(isPrime(nextPrimeCandidate)){
        return nextPrimeCandidate;
      } else {
        nextPrimeCandidate++;
      }
    }
  }

  function findPrimeFactors(factorParent) {
    var primeFactors = [];
    var primeFactorCandidate = 2;
    while(factorParent !== 1){
      while(factorParent % primeFactorCandidate === 0 && factorParent !== 1 ){
        primeFactors.push(primeFactorCandidate);
        factorParent /= primeFactorCandidate;
      }
      primeFactorCandidate = findPrimeAfter(primeFactorCandidate);
    }
    return primeFactors;
  }

  function sortArrayByValue(a,b){
    return a-b;
  }

  function clone3DArray(arrayOfArrays) {
    var cloneArray = arrayOfArrays.map(function(arr) {
      return arr.slice();
    });
    return cloneArray;
  }

  function doesArrayOfArraysContainArray(arrayOfArrays, array){
    var aOA = clone3DArray(arrayOfArrays);
    var a = array.slice(0);
    for(let i=0; i<aOA.length; i++){
      if(aOA[i].sort().join(',') === a.sort().join(',')){
        return true;
      }
    }
    return false;
  }

  function removeDuplicateArrays(combinations) {
    var uniqueCombinations = []
    for(let c=0; c<combinations.length; c++){
      if(!doesArrayOfArraysContainArray(uniqueCombinations, combinations[c])){
        uniqueCombinations[uniqueCombinations.length] = combinations[c];
      }
    }
    return uniqueCombinations;
  }

  function generateCombinations(parentArray, minComboLength) {
    var generate = function(n, src, got, combinations) {
      if(n === 0){
        if(got.length > 0){
          combinations[combinations.length] = got;
        }
        return;
      }
      for (let j=0; j<src.length; j++){
        generate(n - 1, src.slice(j + 1), got.concat([src[j]]), combinations);
      }
      return;
    }
    var combinations = [];
    for(let i=minComboLength; i<parentArray.length; i++){
      generate(i, parentArray, [], combinations);
    }
    combinations.push(parentArray);
    return combinations;
  }

  function generateCombinedFactorCombinations(primeFactors, primeFactorCombinations) {
    var candidates = [];
    for(let p=0; p<primeFactorCombinations.length; p++){
      var product = 1;
      var primeFactorsCopy = primeFactors.slice(0);
      for(let q=0; q<primeFactorCombinations[p].length; q++){
        product *= primeFactorCombinations[p][q];
        primeFactorsCopy.splice(primeFactorsCopy.indexOf(primeFactorCombinations[p][q]), 1);
      }
      primeFactorsCopy.push(product);
      candidates[candidates.length] = primeFactorsCopy.sort(sortArrayByValue).reverse();
    }
    return candidates;
  }

  function determineMinimumCobination (candidates){
    var minimumValue = Infinity;
    var bestFactorCadidate = []
    for(let y=0; y<candidates.length; y++){
      var currentValue = 1;
      var currentPrime = 2;
      for(let z=0; z<combinedFactorCandidates[y].length; z++){
        currentValue *= Math.pow(currentPrime,(combinedFactorCandidates[y][z])-1);
        currentPrime = findPrimeAfter(currentPrime);
      }
      if(currentValue < minimumValue){
        minimumValue = currentValue;
        bestFactorCadidate = combinedFactorCandidates[y];
      }
    }
    return minimumValue;
  }

  var primeFactors = findPrimeFactors(factorCount);
  var primeFactorCombinations = removeDuplicateArrays(generateCombinations(primeFactors, 1));
  var combinedFactorCandidates = generateCombinedFactorCombinations(primeFactors, primeFactorCombinations);
  var smallestNumberWithFactorCount = determineMinimumCobination(combinedFactorCandidates);

  return smallestNumberWithFactorCount;
}

---

Paste the above code block into your browser console and you can test it out yourself:

> smallestNumberByFactorCount(3) --> 4
> smallestNumberByFactorCount(4) --> 6
> smallestNumberByFactorCount(5) --> 16
> smallestNumberByFactorCount(6) --> 12
> smallestNumberByFactorCount(16) --> 120
> smallestNumberByFactorCount(100) --> 45360
> smallestNumberByFactorCount(500) --> 62370000
> smallestNumberByFactorCount(5000) --> 4727833110000
> smallestNumberByFactorCount(100000000) --> 1.795646397225103e+40

My algorithm starts shitting the bed when the input gets up to around 100 million... so for Project Euler problem 500 where the input would be 2^500500 (a really, really, really big number) you would need another approach. However, this is a good general approach that gets you pretty far. Hope it helps.

Please leave comments with efficiency optimization suggestions. I would love to hear them.

Lentissimo

I'm having trouble following what your code wants to do. But if it can only do a simplistic version of the original task, is it really an answer to the question? – Diffluent

This does answer the question: 'How to calculate smallest number with certain number of divisors?" up to over 100,000,000 divisors. The Project Euler question referenced is asking for a number absurdly large (try typing 2^500500 into your calculator). – Lentissimo

@Diffluent And my code isn't "trying to do" anything, it's doing it! ;) – Lentissimo

Answer 4

The highest divisor any number has, other than itself, is the half of the number. For example, 120 has a max divisor of 60 other than itself. So, you can easily reduce the range from (n+1) to (n/2).

More over, for a number to have m divisors, the number must be atleast ((m-1) * 2) following the above logic (-1 because the m th number is itself). For example, a number with 4 divisors has to be atleast 6. So, your search for n has a smaller range now.

These two will reduce the runtime a little.

Forestay

I'm having trouble following this. Are you ending up reducing the space from (n+1) to some factor of n? I don't think that will help in the end. – Diffluent

I reduce the range from n+1 to n/2 because any number will have n/2 as its max divisior. Example, 44 has 22 as the max divisor, 100 has 50 as his max divisor. For odd numbers it will be lesser. So, it makes no sense to check till n+1 when you can only check till its half. I understand this does not improve the algorithm much, but one portion of the algorithm(the part which computes the divisor) now has to perform 1/2 the number for iterations it was originally performing. – Forestay

I understand that. But you're reducing what had been a runtime of 500 hours to a runtime of 250 hours (to make up some numbers). You have to approach the problem from a completely different direction if you want a hope of solving it. – Diffluent

Actually you can reduce it to (integer part of) square root of n. If a * b = n, and a <= b , then a <= sqrt(n), and b >= sqrt(n). Note handy optimising tip: don't check that a <= sqrt(n), instead check that a^2 <= n – Plop

Answer 5

As Miljen Mikic explains, the divisor counting function is determined by the prime factorisation. To calculate n, start at 1 and use a greedy algorithm to double the number of divisors k times, choosing the cheapest factor at each step. The initial costs are the prime numbers, replaced by their square when you use them. After precomputing the first k prime numbers, you can do this quickly with a min-heap. In Python

import primesieve # pip install primesieve
import heapq

def solve(k, modulus=None):
    """Calculate the smallest number with 2**k divisors."""
    n = 1

    costs = primesieve.generate_n_primes(k) # more than necessary

    for i in range(k):
        cost = heapq.heappop(costs)
        heapq.heappush(costs, cost**2)
        n *= cost
        if modulus:
            n %= modulus

    return n

assert solve(4) == 120

if __name__ == "__main__":
    print(solve(500500, 500500507))

Vastah

Answer 6

Phew, I just solved it in java. My "smallest number with 2^n divisors" ended up being represented as a map of primes and their powers.

This puzzle is as much about optimization as anything: get your code working and then refactor hard. It's definitely worth testing up to about 2^30 divisors as there is room for all sorts of second-order bugs to creep in when optimizing. Re-use the results of earlier calculations, try not to sort anything, and stop iterating as soon as you can (NavigableSet and LinkedHashMap were useful). I'm not going to teach my grandmother to efficiently test for primality.

I used java long throughout, but with numbers of this size it's easy to go over Long.MAX_VALUE in the middle of a calculation, remember: (A^2 * B) % C = (A * ((A * B) % C)) % C.

Hope all this motivates rather than gives the game away. Keep going!

Plop

Answer 7

This is my Code. You can use Sieve to generate Prime numbers. If you have any suggestions to my code please suggest.

def findfactors(num):
    list1=[]
    for i in range(num,1,-1):
        if num%i==0:
            list1.append(i)
    return list1

def getcombinations(num):
    factors=findfactors(num)
    list1=[]
    if num==1:
        return 1
    for i in factors:
        if getcombinations(num//i)!=1:
            list1.append([i,getcombinations(num//i)])
        else:
            list1.append(i)
    return list1

def unloadlist(list1):
    list2=[]
    if type(list1).__name__=="list":
        for i in list1[1]:
            if type(i).__name__=="list":
                i=unloadlist(i)
            if type(i).__name__=="list":
                flag=True
                for j in i:
                    if type(j).__name__=="list":
                        list2.append([list1[0]]+j)
                        flag=False
                if flag==True:
                    list2.append([list1[0]]+i)
            else:
                list2.append([list1[0],i])
        if len(list2)==1:
            list2=list2[0]
    else:
        list2=list1
    return list2

def mergeitems(list1):
    list2=[]
    for i in list1:
        if type(i).__name__=="int":
            list2.append((i,))
        elif type(i).__name__=="list":
            if type(i[0]).__name__!="list":
                list2.append(tuple(sorted(i,reverse=True)))
            else:
                for j in i:
                    list2.append(tuple(sorted(j,reverse=True)))
    set1=set(list2)
    return set1

def find_smallest_number(num):
    #start writing your code here
    list1=getcombinations(num)
    for i in range(0,len(list1)):
        list1[i]=unloadlist(list1[i])
    mainlist=mergeitems(list1)
    possibles=[]
    primes=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227]
    for i in mainlist:
        num=1
        for j in range(0,len(i)):
            num*=primes[j]**(i[j] - 1)
        possibles.append(num)
    return min(possibles)

num=7
print("The number of divisors :",num)
result=find_smallest_number(num)
print("The smallest number having",num," divisors:",result)

Xerosis

Welcome to SO. Could you explain your code? I'm finding it hard to follow. Better variable names may also help - list1, list2, i, num, set1, mainlist, possibles are all somewhat vague. getcombinations seems to be either a list or a number, neither of which is related to the usual idea of combinations (eg docs.python.org/3.6/library/…). Does this run fast enough? findfactors has me worried, but I can't tell. – Diffluent

Answer 8

The Prime Factorization (PF), in abbreviated form, for the smallest integer having 2**500,500 divisors is shown below:

2**31 * (3...7)**15 * (11...47)**7 * (53...2,713)**3 * (2,719...7,370,029)

The smallest positive integer having 2^n divisors is the product of the sequence of the first n primes and powers of primes. Powers of primes (pp) are primes raised to the 2^(2^e) power (powers are 2,4,8,16...). First 3 pp are 4,9 and 16 (2^2,3^2 and 2^4).

Since only prime factors are used in a PF, you will notice that the pp are aggregated with the prime factors. For n = 500,550 here are some stats or counts: 5 terms in the PF (powers 31,15,7,3,1). Total Primes (P) = 500,084 Powers of primes(pp) = 416 Total P + pp = n = 500,500 See theorem above.

Single primes (the last term of the PF) total 499,688.

You can calculate this PF (and others for 2^n) using Sage Math and Excel (although with Excel you'll need a prime counting function).

Also, you should check your PF solution. This can be done several ways by assigning weights to the various pp and single primes to check the original n.

Alyssaalyssum

Answer 9

Fully functional code.

def find_smallest_number(num):
    number2=0

    if(num%8==0):
        number2=min(2**((num/4)-1)*3**1*5**1 , 2**((num//2)-1)*3**1)
    elif(num%9==0):
        number2=2**((num/9)-1)*3**2*5**2   
    elif(num%2==0 and num%3==0):
        number2=2**((num/6)-1)*3**2*5**1   
    elif((num%4==0)):
        number2=2**((num/4)-1)*3**1*5**1
    elif(num%2==0):
        number2=2**((num/2)-1)*3**1
    else:
        number2=2**(num-1)         

    return number2   


num=32
print("The number of divisors :",num)
result=find_smallest_number(num)
print("The smallest number having",num," divisors:",result)

Prankster

If you register with Project Euler and read the FAQ [projecteuler.net/about], which looks different after you have signed in, it explains why you should not spoil people's learning journey by publishing answers to the questions. – Plop