Abundant number implementation

Question

I have implementted a simple JavaScript function to find the list of abundant numbers and print them on the screen.

an abundant number is a number for which the sum of its proper divisors is greater than the number

The function printAbundantNumbers(), takes an argument, which is a range that tells the function how many abundant numbers that it should find and print out on the screen. The function also includes several smaller functions to ensure the readability of the code - so that each functionality will be performed with no conflicts to the other code.

I think the code is quite long. Is there a way to shorten it?

Here is the code:

function printAbundantNumbers(num) {
 const concatAbundantNumbers = function(){ 
const finalArray = collectAbundantNumbers().map(arr=>arr[1]*arr[arr.length-1]);
return finalArray; // Return the final array.
 }
// Collects all abundant numbers.
 const collectAbundantNumbers = function (){
let listOfFactors = collectFactorsForEachNumbers(num).filter(e=>addArray(e)>(e[1]*e[e.length-1])); // Find all the factors and loop through them. If the sum of these factors is greater than the number, then assign them to a variable.
return listOfFactors;
 }
 // Collect factors for each number.
 const collectFactorsForEachNumbers = function (num){
let listOfIndividualElementFactors = [];
for(let i=2;i<=num;i++) {
 let factors = findFactor(i); // find factors.
 listOfIndividualElementFactors.push([...factors]); // Making a 2-d array out of this and assign to the variable.
}
return listOfIndividualElementFactors;
 }
 // find factors.
 const findFactor = function (num){
let listOfFactors = [];
for(let i=1; i<num;i++) {
 if(num%i===0)listOfFactors.push(i);
}
return listOfFactors;
 }
 // add arrays
 const addArray = function(arr){
let sum=0;
arr.forEach(e=>sum+=e); // loop through the array and them.
return sum;
 }
 concatAbundantNumbers().forEach(e=>console.log(e+"\n")); // writes the abundant to the screen.
}
printAbundantNumbers(200);

Answer 1

Is there a way to shorten it?

I'll do you one better: make it shorter overall and more efficient.

You need the sum of (proper) divisors of each number that is being tested. It seems to make sense to compute the divisors and then sum them.. but number theory being number theory, there is a shortcut. Using the shortcut, we save some code, and at the same time make it more efficient.

The shortcut uses the prime factorization of the number. That seems as difficult as listing the divisors, but it is usually easier: there are typically many more divisors than prime factors, and listing the prime factors in a simple way is significantly more efficient than listing the divisors in a simple way (the difference can be reduced by, you may have guessed it, generating the divisors from the prime factorization). A core difference is that we only need to iterate trial-division up to the square root of n, in the worst case, and in better cases we can divide n by each factor that is found, decreasing the loop bound as we go.

A sum-of-divisors function based on the prime factorization p can be based on this formula:

formula of sigma_x(n) = product [i from 1 to r] of (sum [j from 0 to a[i]]) pow(p[i], jx)

Where p[i] is the i'th prime factor and a[i] is its corresponding exponent. The x in this function will be 1 for our purposes, different values of x create different kinds of divisor function. With x = 1 this calculates the sum of divisors, to turn it into the sum of proper divisors we just subtract n later on.

To summarize what's happening in that formula: suppose we find a find factor p of our number n, with exponent a, then we want the sum of all powers of p from 0 to a inclusive. Do that for all factors, and take the product of those sums.

Here is one attempt in Javascript, evaluating that sigma formula while finding prime factors: (your software engineering instinct may tell you to separate all the things, that would just add complication here)

function sumOfDivisors(n)
{
 var s = 1;
 for (var p = 2; p * p <= n; p++) {
 var inner_sum = 1;
 var power_of_p = 1;
 while (n % p === 0) {
 n /= p;
 power_of_p *= p;
 inner_sum += power_of_p;
 }
 s *= inner_sum;
 }
 
 if (n > 1)
 s *= (1 + n);
 return s;
}

Admittedly that function is somewhat long, but now the rest can be much simpler, with no need to sum anything from this point on or to reconstruct numbers from their divisors:

function printAbundantNumbers(n) {
 var abundantNumbers = [...Array(n + 1).keys()].filter(i => i && sumOfDivisors(i) - i > i);
 abundantNumbers.forEach(e => console.log(e));
}

Where [...Array(n + 1).keys()] is a trick to get the numbers 0 .. n (inclusive) in an array, and the filter condition includes i && to remove zero. By the way I only wrote it that way because I thought that might fit your style.

I like that this spells out the condition sumOfDivisors(i) - i > i as opposed to addArray(e)>(e[1]*e[e.length-1]) which is equivalent but more mysterious.

As for efficiency, this implementation can easily list the abundant numbers up to a million.

• user555045: @TobyHarnish sorry I don't understand that question
• slepic: You can do trial division for p=2 separately. Then continue with p=3 and p+=2 on each iteration. Skipping all even numbers other than 2, because those numbers are definitely not primes.
• user555045: @slepic and you can check 2 and 3 separately, and then check only numbers of the form 3*k-1 and 3*k+1, bringing it down from checking 50% of the numbers to 33%, and you can go even further, but all of this goes against the goal of making the code short

Answer 2

Here is one way we can simplify your code:

1. needCount - it is right amount of abundant numbers

2. define an array abundants where we will save abundant numbers

3. define a currNum variable - it is the current number which we will check

4. start the infinite loop - because we don't know when we will meet last required abundant number, so we will list all the numbers

5. define an array divisors where we will save all divisors of current number

6. proper divisors starts from 1 (so our for loop starts from 1) till the number (so our for loop ends at num - 1)

7. currNum % d - here we get remainder. The values of reminder are [0, d-1]. We will get 0 only if the d is proper divisor of currNum. If we find proper divisor we add it into divisors array else check next d

8. after for loop we need to count the sum of all divisors. We can easily find the sum of all numbers in array using reduce. Here is the detailed explanation of how we count the sum using the reduce

9. now we just compare current number with the sum of divisors. If the sum is bigger current number we add this number into the abundants array

10. if we reached the need count of abundant numbers then we stop the infinite loop else we check next number

11. at the end we just return the all abundant numbers

Code:

const getAbundantNumbers = needCount => {
 const abundants = [];
 let currNum = 1;
 while (true) {
 const divisors = [];
 for (let d = 1; d < currNum; ++d) {
 if (currNum % d === 0) divisors.push(d);
 }
 const divisorsSum = divisors.reduce((sum, d) => sum + d, 0);
 if (divisorsSum > currNum) abundants.push(currNum);
 if (abundants.length === needCount) break;
 ++currNum;
 }
 
 return abundants;
}
console.log(getAbundantNumbers(8));