How to calculate smallest number with certain number of divisors?
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
factorCountnumber 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.
You should use the formula for the number of divisors of integer n:
d(n) = (a1+1)(a2+1)...(ak+1)
where
n = p1a1 * p2a2 *p3a3 *...*pkak
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 p1x1 * p2x2 *p3x3 *...*pkxk, where each of xi is between 0 and ai, so there are ai + 1 possibilities for choosing each of xi. 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) = (a1+1)(a2+1)...(ak+1) = 16 = 24.
This means that you have at most 4 different primes, therefore:
x = 2a1 * 3a2 *5a3 * 7a4
where ai >= 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 a1), or to use 7 (i.e. take a4=1 instead of a4=0)? Well, it's simple to check, 2*3*5*7 > 23 * 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, 22, 32, 24 etc. Why? Because 16 = 24, so each of (ai+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 2500500 divisors. Heap is initialized with first k primes (in the problem statement, k = 500500), and in each step, when you pop px from the heap, p2x is returned and result is multiplied by px. Step-by-step solution for d(x) = 16 = 24:
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.