Make loop and code more efficient to handle large numbers with loops

Question

this is an assignment on Codewars, in other words like a homework. :) I have to write a function that returns the amount of numbers between 1 and n (inclusive) that can be represented as the difference of two perfect squares. For example, 20 = 6² - 4² and 21 = 5² - 2². Many numbers can be written this way, but not all.

I wrote a function, it works well, but it needs to be able to handle n values up to 45000. Basically my code crashes when it gets to analyze numbers in the order of thousands. In order to make the code more efficient, I tried to reverse the initial loop, from n to 0 instead than from 0 to n. I have tried to divide the n by two until it gets small enough and then multiply the final result times 2 again, but didn't work. I also used a while loop, but then I realized that I simply don't know how to solve this issue, and after 3 days of pointless attempts to solve it with brute force, I am asking for help as I don't want to just give up on it . This is my code

function countSquareable(n){
  var y = []
  var c = []

  for (var i = 0; i <= n; i++) { // all numbers powered in range
  y.push(Math.pow(i,2))
  }

for(i = 0; i < y.length; i++) {
    c.push(y.map(a => y[i]-a)) //  all subtractions' combos

}

var d = c.toString().split(",").sort(function(a, b){return a-b}).filter(function(a) {return a>0 && a<=n}) // only the combos I need in the range

var a = [], b = [], prev; // remove duplicates
d.sort();
    for ( var i = 0; i < d.length; i++ ) {
        if ( d[i] !== prev ) {
            a.push(d[i]);
            b.push(1);
        } else {
            b[b.length-1]++;
        }
        prev = d[i];
    }

return console.log(a.length) // end result



};
countSquareable(500)

countSquareable(4) // should return 3 and it works
countSquareable(5) // should return 4 and it works
countSquareable(40) // should return 30 and it works
countSquareable(45000) // should return 33750 but crashes
countSquareable(6427), // should return 4820 but crashes

How do I make a code SO MUCH more efficient to solve the issue? The kata is here. thanks!!

Answer 1

This could do with a small dose of math.

If instead of counting the values, you can list them, say the thirty of them for 40, you get

[1, 3, 4, 5, 7, 8, 9, 11, 12, 13, 15, 16, 17, 19, 20, 21,
 23, 24, 25, 27, 28, 29, 31, 32, 33, 35, 36, 37, 39, 40]

If it's difficult to see the pattern there, try reading it aloud. The point is that these group easily as

[        1,
 3,  4,  5,
 7,  8,  9,
 11, 12, 13,
 15, 16, 17,
 19, 20, 21,
 23, 24, 25,
 27, 28, 29,
 31, 32, 33,
 35, 36, 37,
 39, 40, (41)]

In other words, every fourth number is missing, starting with 2. Here's code that follows that pattern:

const range = (lo, hi) => Array(...Array(hi - lo + 1)).map((_, n) => lo + n)

const countSquareable = (n) => range(1, n).filter(n => n % 4 !== 2).length

console.log(countSquareable(4))
console.log(countSquareable(5))
console.log(countSquareable(40))
console.log(countSquareable(45000))

So it matches the expectations. But we're in the territory of math now, so we need to prove things. We can do this in three cases:

Can n be represented as the difference of squares?

Case 1: n is odd

Let a = (n + 1) / 2, let b = (n - 1) / 2.

Since n is odd, n - 1 and n + 1 are even, so a and b are both integers.

a^2 = (n^2 + 2n + 1) / 4
b^2 = (n^2 - 2n + 1) / 4

so

a^2 - b^2 = 4n / 4 = n

Hence, an odd number can be represented as the difference of squares.

Case 2: n is divisible by 4

Let a = (n / 4 + 1), let b = (n / 4 - 1)

Since n is divisible by 4, (n / 4) is an integer and thusaandb` are integers.

Now

a^2 = (n^2/16 + 2n/4 + 1)
b^2 = (n^2/16 - 2n/4 + 1)

and

a^2 - b^2 = 4n/4 = n

Hence, a multiple of 4 can be represented as the difference of squares.

Case 3: A multiple of 2 that's not a multiple of 4

We can divide the integers up this way: (4n), (4n + 1), (4n + 2), (4n + 3).

squaring each of these, and choosing an appropriate k we get:

(4n)^2 = 16n^2 = 4 * 4n^2                             = (4k)
(4n + 1)^2 = (16n^2 + 8n + 1) = 4(4n^2 + 2n) + 1,     = (4k + 1)
(4n + 2)^2 = (16n^2 + 16n + 4) = 4(4n^2 + 4n + 1)     = (4k)
(4n + 3)^2 = (16n^2 + 24n + 9) = 4(4n^2 + 6n + 2) + 1 = (4k + 1)

So the only remainders possible when dividing a square by 4 are 0 and 1.

Subtracting those, we get (1 - 0) = 1, (1 - 1) = 0, (0 - 0) = 0, (0 - 1) = -1 (this last is the same as a remainder of 3: 4k - 1 = 4(k -1) + 3.)

So we can get remainders of 0, 1, or 3. But we cannot get 2.

Hence, a multiple of 2 that's not a multiple of 4 cannot be represented as the difference of squares.

Q.E.D. We've proven our intuition correct: Any integer can be written as the difference of squares except for those that are multiples of 2 but not of 4.

---

Update

My original code was a brute-force approach, noting that a^2 - b^2 = (a - b) * (a + b) and that hence the smaller factor ((a - b)) had to be less than the square root of our top number if the product would be less than n. Then I tried all the possible values of b, saving (a^2 - b^2) if it was less than n. This works, and seems efficient enough for the 45000 case. But it misses the analysis above.

In any case, here is that version:

const countSquareable = (n) => {
  const found = new Set()
   // a^2 - b^2 = (a - b)(a + b), so (a - b) can be no larger than sqrt(n)
  const topDiff = Math.sqrt(n)
  for (let diff = 1; diff <= topDiff; diff++) {
    const topB = n / 2 // can we get a tighter bound here?
    for (let b = 0; b < topB; b++) {
      let a = b +  diff
      const val = (a * a) - (b * b)
      if (val <= n) {
        found.add(val)
      }
    }
  }
  //console.log([...found].sort((a, b) => a - b))
  return found.size
}

console.log(countSquareable(45000))