Optimizing a Function to Check Pronic Numbers in JavaScript

Question

I've written a function in JavaScript to check whether a given number is a Pronic number. A Pronic number, also known as an oblong number, rectangular number, or heteromecic number, is a number which is the product of two consecutive integers, that is, n(n + 1). The first few Pronic numbers are 0, 2, 6, 12, 20, 30, 42 etc.

My function works correctly, but it's not efficient for large numbers. For example, it takes a significant amount of time to process the number 120,000. I'm looking for ways to optimize my function to improve its performance with large numbers.

Here's my current function:

function isPronic(n) {
  if (n == 0) {
    return true;
  }
  let res = [];
  let isPronic = false;
  for (let i = 1; i <= n; i++) {
    let arr = [];
    for (let j = i; j <= n; j++) {
      if (i * j == n) {
        arr.push(i, j);
      }
    }
    if (arr.length > 0) {
      res.push(arr);
    }
  }
  for (let i = 0; i < res.length; i++) {
    if (Number(res[i][0]) + 1 == res[i][1]) {
      isPronic = !isPronic;
    }
  }
  return isPronic;
}

I'm looking for suggestions on how to improve this function's performance. Any insights or advice would be greatly appreciated!

Answer 1

Add guard

The function requires a unsigned integer as an argument.

A JS number is a floating point double (64bit floating point value).

Guard function against bad input by checking

• is argument positive?
• is argument an integer?
• is argument within a usable range (for doubles) n <= Number.MAX_SAFE_INTEGER?

You have added one guard (early exit) by checking for zero and returning true. To be safe check all the above.

const isSafeUint = n => n >= 0 && n <= Number.MAX_SAFE_INTEGER && (n % 1) === 0;

Personally the guard should be outside the function (Single role) but you present the function as stand alone so would be best to wrap in check.

const isSafePronic = n => isSafeUint(n) && isPronic(n);

Early exit

You have an early exit by checking for the argument 0 and returning true 0 * 1 == 0.

However there is a second early exit based on the fact that all pronic numbers are even so if argument is not even the return false.

function isPronic(n) {
  if (n === 0) { return true }  // use === not ==
  if (n % 2) { return false }   // not a pronic if n is odd

More than brute force

Your function uses a solution methodology we call a brute force approach. Check every possible combination of m until to m * (m + 1) === n. Do this until we are sure that there are no more possibilities.

You have assumed that if the value to check is less than or equal to the argument n it should be part of the set of values to check.

However this will check way more than needed. We could halve this max value and still be sure that we checked every root of the pronic.

In fact the minimum brute force needed is ~ sqrt(n)

Storage!!!

Your inner loop (first loop) checks if the two integers i * j === n but because you do not know if j === i + 1 you store the value in an array so that in another loop you can check if the two values were within one unit.

This is very wasteful of memory and CPU cycles.

We can create a minimum brute force solution by only checking values of m and m + 1 and only values up to sqrt(n)

Example minimum brute force with some testing code.

const isSafeUint = n => n >= 0 && n <= Number.MAX_SAFE_INTEGER && (n % 1) === 0;
const isSafePronic = n => isSafeUint(n) && isPronic(n);
function isPronic(n) {
    if (n === 0) { return true }           // use === not ==
    if (n % 2) { return false }            // not a pronic if n is odd
    for (let i = 1; i < n ** 0.5; i++) {  // n ** 0.5 is same as Math.sqrt(n)
        if (i * (i + 1) === n) { return true; } // found a match proof that n is
                                                // pronic so return true
    }
    return false;  // not found must not be pronic
}

//====================================================================================================
// Testing 

function test(n, expected) {
   const res = isSafePronic(n);
   console.log("Value " + n + " is pronic: " + res + (res !== expected ? " Result not as expected " + expected +"!" : " OK."));
}

// known set of pronics
[0, 2, 6, 12, 20, 30, 42, 56, 72, 90, 110, 132, 156, 182, 210, 240, 272, 306, 342, 380, 420, 462]
    .forEach(n => test(n, true));
// test known set of non pronics
[3, 6, 12, 20, 30, 42, 56, 72, 90, 110, 132, 156, 182, 210, 240, 272, 306, 342, 380, 420, 462]
    .forEach(n => (test(n + 2, false), test(n - 2, false)));

The above solution will be much faster than you original. We have optimised the storage needs from quasilinear \$O(n log(n))\$ to constant \$O(1)\$, But the complexity has only been slightly improved, quasilinear \$O(n log(n))\$ to linear \$O(n)\$

I know (from experience) that there is a better than linear time solution, but we do not always know that such a simple solution existes.

This is why we always keep our problem solving skills fresh.

A constant solution?

Looping over many values (as done in brute force above) can be avoided if we look at the problem in different ways.

Let's look at the algebraic definition of a pronic. A value n is pronic if the pronic root m satisfies the following functions...

• m * (m + 1) = n same as...

• m * m + m = n same as...

• m ** 2 = n - m same as...

• m = (n - m) ** 0.5 (where ** 0.5 is sqrt) or an approximation...

  m ~ n ** 0.5

Now we know that a solution is finding and checking a value of m that is less than and very close to (approximately) sqrt(n) and m * (m + 1) === n is true.

I don't have a proof but testing the code below shows that for a small set of known pronics, (and hence a set of known non pronics) that the below function suits our needs.

// once n has passed checks
const isPronic = Math.floor(n ** 0.5) * (Math.floor(n ** 0.5) + 1) === n

The solution is also the best we can get, constant time \$O(1)\$ ^{(* special note)}

const isSafeUint = n => n >= 0 && n <= Number.MAX_SAFE_INTEGER && (n % 1) === 0;
const isSafePronic = n => isSafeUint(n) && isPronic(n);
function isPronic(n) {
    if (n === 0) { return true }      // use === not ==
    if (n % 2) { return false }       // not a pronic if n is odd
    const m = Math.floor(n ** 0.5);   // make an educated guess
    return m * (m + 1) === n; 
}

//= Testing ===================================================================================================
var foundFail = false;
function test(n, expected) {
   const res = isSafePronic(n);
   if (res !== expected) {
       foundFail = true;
       console.log("Value " + n + " is pronic: " + res + (res !== expected ? "; Result not as expected " + expected +"!" : "; OK."));
   }
}
// known set of pronics
const knownPronics = [0,2,6,12,20,30,42,56,72,90,110,132,156,182,210,240,272,306,342,380,420,462,506,552,600,650,702,756,812,870,930,992,1056,1122,1190,1260,1332,1406,1482,1560,1640,1722,1806,1892,1980,2070,2162,2256,2352,2450,2550];
knownPronics.forEach(n => test(n, true));

// remove first two items and add value 5
knownPronics.shift();
knownPronics.shift();
knownPronics.unshift(5);

// Test known set of non pronics
knownPronics.forEach(n => (test(n + 3, false), test(n - 2, false)));
console.log(foundFail ? "A test/s did not pass." : "All tests passed" );

* Special NOTE!

Please note that the square root function is not a constant time complexity function and is in fact logarithmic \$O(log(n))\$ , thus the example function stated as constant time is in fact logarithmic.

However there are many (constant time) approximations of sqrt and it may well be possible for a exact match (constant time) solution for pronic square roots to exist.

I leave that to the OP if interested

Answer 2

quadratic complexity

how to improve this function's performance

The time complexity of these loops is out of control!

  for (let i = 1; i <= n; i++) {
    ...
    for (let j = i; j <= n; j++) {

What human would think about the problem in this way? Or did an LLM suggest that approach?

This suffices, in \$O(1)\$ constant time:

  root = Math.sqrt(n).toFixed()
  return n == root * (root + 1)

recycled names

function isPronic(n) {
  ...
  let isPronic = false;

These are distinct names, drawn from distinct namespaces. It doesn't matter to the machine. But it does matter to humans, especially during a telephone conversation about the code.

Don't change the meaning of a symbol part way through the computation. Prefer to invent a new symbol for a new concept. Here, a function is not a boolean, even when we're talking about a boolean predicate function. (JS is not Fortran and is not Matlab.)