Determine if a number is a perfect square

Checking if a number is a perfect square is a trivial task when a square root function is available. Calculating the floored square root squared should result in the original number:

\[\sqrt{n}\in\mathbb{N}\Leftrightarrow\lfloor\sqrt{n}\rfloor^2 = n\]

On many systems, a calculation of a square root is costly, so the easiest way is a \(O(\sqrt{n})\) iteration like

function isPerfectSquare(n) {

  for (let i = 0; i * i <= n; i++) { 

    if (i * i === n) { 
      return true; 
    } 
  }
  return false; 
}

However, many numbers have certain patterns that can be exploited to make the best case performance \(O(1)\) by excluding whole ranges of numbers. The \(O(\sqrt{n})\) is then only required as a worst case fallback.

Check last digit

It is well known that in base 10, a perfect square can have the least significant digit to be only 0, 1, 4, 5, 6 or 9, which forbids 2, 3, 7 and 8 under modulo 10.

The proof is pretty straightforward. Let's say the least significant digit of our number \(n\in\mathbb{Z}\) is \(a\) and the remaining digits are called \(b\), we can then say \(n=10b+a\).

Now when squared, \(n^2=(10b+a)^2=100b^2+20ab+a^2\). It is clear that the first part \(100b^2+2ab\cdot 10\) does not affect the least significant digit, but only \(a\) does.

Listing all possible squares results in

\[\{a^2 : a\in[0, 9]\} = \{0,1,4,9,16,25,36,49,64,81\}\]

which ultimately shows that the only possible least significant digits of a perfect square are 0,1,4,5,6 and 9.

Check digital root

The digital root of a number \(n\) is the sum of all digits of that number. If the sum has more than one digit, the procedure is repeated until only one digit remains. Instead of implementing a recursive solution, we can use a trick. When we work in base \(b:= 10\), it is clear that for any \(k\) the following concurrence holds: \(b^k\equiv 1\pmod{b-1}\). As the number \(n\) consists of its digits \(n_i\) times \(10^i\), the following happens when we sum under the modular concruence 9:

\[ \begin{array}{rl} \text{dr}(n) &= \sum\limits_{i=0}10^i\cdot n_i \pmod{9}\\ &= \sum\limits_{i=0}1\cdot n_i \pmod{9}\\ &= \sum\limits_{i=0}n_i \pmod{9}\\ &= \begin{cases} n\pmod{9} & n\not\equiv 0\pmod{9}\\ 9 & n\equiv 0\pmod{9} \end{cases}\\ &= 1 + (n-1\pmod{9}) \end{array} \]

Using the digital root function, we can now check the behavior when getting a squared number:

\[\begin{array}{rl} \text{dr}(n^2) &= 1 + (n^2-1\pmod{9})\\ &= 1 + (n^2 + 8\pmod{9})\\ &= \underbrace{1 + \big(\underbrace{(n^2\pmod{9}}_{\in\{0, 1, 4, 7\}}) +8\pmod{9}\big)}_{\in\{9, 1, 4, 7\}}\\ \end{array}\]

That is interesting. It says, that a perfect square has only four possible digital roots (1, 5, 7 and 9) and even simpler, a perfect square has four possible digits (0, 1, 4 and 7) under modulo 9.

Improve findings over other modules

An interesting question that arises from these two findings is, can we find a better module, that covers a larger range of numbers, that is can we find a better module \(m\) to increase the coverage and reduce the number of checks?

\[n^2 \equiv k \pmod{m}\]

Since the possible digits repeat quickly, a simple brute force enumeration approach can give us possible candidates:

let res = [];
for (let m = 2; m < 500; m++) {
  const p = {};
  for (let i = 0; i < 3000; i++) {
    p[(i * i) % m] = true;
  }
  
  let k = Object.keys(pos);

  if (k.length < 10)
    res.push({module: m, coverage: (m - k.length) / m, candidates: k});
}

Sorting the result by coverage descending leads to the following table:

The most interesting result is module \(16\), which has only four possible residue classes and covers \(\frac{3}{4}\) of all numbers to give a best case performance of \(O(1)\).

A much better improved implementation to check for perfect squares is then

function isPerfectSquare(n) {
  let r = n & 15;
  if (r == 0 || r == 1 || r == 4 || r == 9) {
    for (let i = 0; i * i <= n; i++) { 

      if (i * i === n) { 
        return true; 
      } 
    }
  }
  return false; 
}

Interestingly, the two previous ideas of checking the last digit and the digit root - which brought up the whole idea - does not cover that much and requires many more individual checks.

The good thing on this method is, we can add additional checks, for example for \(m=7\) and \(m=9\) to further increase \(O(1)\) test coverage.

You might also be interested in the following

• Calculate the sum of divisors
• The Cleverness of Paper Size
• Connectedness of tree height, b-adic numbers and repunits
• How to map a Square to a Circle

Sorry, comments are closed for this article. Contact me if you want to leave a note.