Algorithm for finding smallest number with given number of factors

Question

What's the most efficient algorithm anyone can think of that, given a natural number n, returns the least natural number x with n positive divisors (including 1 and x)? For example, given 4 the algorithm should result in 6 (divisors: 1,2,3,6); i.e. 6 is the smallest number having 4 distinct factors. Similarly, given 6, the algorithm should result in 12 (divisors: 1,2,3,4,6,12); i.e. 12 is the smallest number having 6 distinct factors

In terms of real-world performance, I'm looking for a scalable algorithm which can give answers of the order of 10²⁰ within 2 seconds on a machine which can do 10⁷ computations per second.

Cronus

@Cronus I'm afraid you create a wrong impression of an arrogant person. – Adventurer

that one was for Preet...he deleted his comment..I have edited the question for you to make it more clear – Cronus

I downvoted you for the poor question asking strategy. What you've got here is a statement; it can't hurt to be a little bit more clear on why you're doing this, what language, etc ... – Spook

Do you mean to say distinct factors? – Epley

@Cronus it doesn't matter. It was a good-humored joke with an attempt to show you that your question is poorly phrased. You told him off — not a good idea if you're looking for help. – Adventurer

I guess we are looking for different factors. Not a real algorithm but the solution seems to be to start from 1 and iterate over the numbers keeping the least common multiple of your index and your current number until you have the required number of factors. – Cocytus

math.SE would be a better fit for this. However, make sure to specify the problem fully and rigorously. – Altheta

In the specific case the number of divisors is a power of 2, you can use a greedy algorithm, see projecteuler.net/problem=500 and https://mcmap.net/q/624596/-how-to-calculate-smallest-number-with-certain-number-of-divisors – Dextrous

Answer 1

http://www.primepuzzles.net/problems/prob_019.htm

b) Jud McCranie, T.W.A. Baumann & Enoch Haga sent basically the same procedure to find N(d) for a given d:

1. Factorize d as a product of his prime divisors: d = p₁^a₁ * p₂^a₂ *p₃^a₃ *...
2. convert this factorization in another arithmetically equivalent factorization, composed of non-powered monotonically decreasing and not necesarilly prime factors... (uf!...) d = p₁^a₁ * p₂^a₂ *p₃^a₃ *... = b₁ * b₂ * b₃... such that b₁ ≥ b₂ ≥ b₃...
   You must realize that for every given d, there are several arithmetically equivalent factorizations that can be done: by example:
   if d = 16 = 2⁴ then there are 5 equivalent factorizations: d = 2*2*2*2 = 4*2*2 = 4*4 = 8*2 = 16
3. N is the minimal number resulting of computing 2^b₁-1 * 3^b₂-1 * 5^b₃-1 * ... for all the equivalent factorizations of d. Working the same example:
   N(16) = the minimal of these {2 * 3 * 5 * 7, 2³ * 3 * 5, 2³ * 3³, 2⁷ * 3, 2¹⁵} = 2³ * 3 * 5 = 120

Update: With numbers around 10²⁰, pay attention to the notes by Christian Bau quoted on the same page.

Adventurer

Answer 2

//What is the smallest number with X factors?
function smallestNumberWithThisManyFactors(factorCount) {

  Number.prototype.isPrime = function() {
    let primeCandidate = this;
    if(primeCandidate <= 1 || primeCandidate % 1 !== 0) return false
    let i = 2;
    while(i <= Math.floor(Math.sqrt(primeCandidate))){
      if(primeCandidate%i === 0) return false;
      i++;
    }
    return true;
  }

  Number.prototype.nextPrime = function() {
    let currentPrime = this;
    let nextPrimeCandidate = currentPrime + 1
    while(nextPrimeCandidate < Infinity) {
      if(nextPrimeCandidate.isPrime()){
        return nextPrimeCandidate;
      } else {
        nextPrimeCandidate++;
      }
    }
  }

  Number.prototype.primeFactors = function() {
    let factorParent = this;
    let primeFactors = [];
    let primeFactorCandidate = 2;
    while(factorParent !== 1){
      while(factorParent % primeFactorCandidate === 0){
        primeFactors.push(primeFactorCandidate);
        factorParent /= primeFactorCandidate;
      }
      primeFactorCandidate = primeFactorCandidate.nextPrime();
    }
    return primeFactors;
  }

  Number.prototype.factors = function() {
    let parentNumber = this.valueOf();
    let factors = []
    let iterator = parentNumber % 2 === 0 ? 1 : 2

    let factorCandidate = 1;
    for(factorCandidate; factorCandidate <= Math.floor(parentNumber/2); factorCandidate += iterator) {
      if(parentNumber % factorCandidate === 0) {
        factors.push(factorCandidate)
      }
    }
    factors.push(parentNumber)
    return factors
  }

  Array.prototype.valueSort = function() {
    return this.sort(function (a,b){ return a-b })
  }

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

  function does3DArrayContainArray(arrayOfArrays, array){
    let aOA = clone3DArray(arrayOfArrays);
    let 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) {
    let uniqueCombinations = []
    for(let c = 0; c < combinations.length; c++){
      if(!does3DArrayContainArray(uniqueCombinations, combinations[c])){
        uniqueCombinations[uniqueCombinations.length] = combinations[c];
      }
    }
    return uniqueCombinations;
  }

  function generateCombinations(parentArray) {
    let 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;
    }
    let combinations = [];
    for(let i=1; i<parentArray.length; i++){
      generate(i, parentArray, [], combinations);
    }
    combinations.push(parentArray);
    return combinations;
  }

  function generateCombinedFactorCombinations(primeFactors, primeFactorCombinations) {
    let candidates = [];
    for(let p=0; p<primeFactorCombinations.length; p++){
      let product = 1;
      let 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.valueSort().reverse();
    }
    return candidates;
  }

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

  let primeFactors = factorCount.primeFactors();
  let primeFactorCombinations = removeDuplicateArrays(generateCombinations(primeFactors));
  let combinedFactorCandidates = generateCombinedFactorCombinations(primeFactors, primeFactorCombinations);
  let smallestNumberWithFactorCount = determineMinimumCobination(combinedFactorCandidates);
  console.log('The smallest number with ' + factorCount + ' factors is: ')
  console.log(smallestNumberWithFactorCount)
  console.log('With these factors being: ')
  console.log(smallestNumberWithFactorCount.factors())

  return smallestNumberWithFactorCount;
}

smallestNumberWithThisManyFactors(10)

Incumbency