0
$\begingroup$

The method is based on the following observation: an integer $N=n^2$ is a square which can also be written as $N=n^2=(a+b)^2=a^2+2ab+b^2$ with:
$a=(n−1)/2$
$b=(n+1)/2$

We need to consider two cases, $N$ odd and $N$ even. The first case is simpler. Let's consider $N=n^2=9^2=81$. The value of $ab$ is given by $ab=(N−1)/4$.
Since $2ab=2(n−1)(n+1)/4=2(n^2−1)/4=2(N−1)/4=40$.
So $ab=20$ and $N=81=9^2=a^2+2∗20+b^2$.

At this point we don't know the values of a and b. However we know that their sum is $a^2+b^2=81−2∗20=41$. We also know that $a^2<ab<b^2$ since we assume $b>a$.

The important property is that $ab=2T_{k}$ with $T_{k}=k(k+1)/2$ a triangular number whose index $k$ needs to be determined.
This property is that of all numbers lying on the diagonal immediately below the main diagonal which contains all the integers square.

An important property of triangular numbers is $T_{k}^2= 1^3 + 2^3 + 3^3 + ... + k^3$, that is the square of a triangular number is the sum of the cubes from $1$ to $k$.
This property allows us to calculate the index of $T_{k}=ab/2=10$.

$T_{k}^2=10^2=100=1^3 + 2^3 + 3^3 + 4^3$. We can infer that $k=4$ and $T_{4}=4(4+1)/2=4*5/2=10$.

Knowing the numerical value of the index of $T_{k}$, we can immediately conclude that:

$a^2=4^2$ and $b^2=5^2$ and their sum is $s=4^2 + 5^2=41$.

So $N=81= 4^2 + 2*20 + 5^2= (4+5)^2=9^2$.

Basically this method allows to determine if an integer $N$ is a square without using the square root calculation and the complex algorithm of calculating the sum of two squares.

Since all numbers $ab$ on the diagonal below the main diagonal which contains the squares are always even we can use a simple test to discard odd integers that cannot be a square if the value of $ab$ is odd. For example $61$ cannot be a square since $(61-1)/4=15$. The same apply to $29$ and $85$.

For even numbers $N$, there is an additional step. For even numbers, we first calculate $M=N/4$. If $M$ is odd, then we decompose $M$ as was done before for $N$.
Example: $N=100$, then $M/4=25$. We try to decompose $M=25=a^2 + 2ab + b^2$ and we find $M=2^2 + 2*6 + 3^2=5^2$. Since $N=4M=4*5^2=2^2*5^2=10^2$.

In some cases with even numbers $N$, $N/4=M_1$ with even $M_1$. In this case, we calculate $M_2=M_1/4$. If $M_2$ is odd, we apply the method for odd potential squares.
An example is $N=144$, $N/4=M_1=36$ so we need another step. We calculate $M_2=36/4=9$. Since 9 is odd, we decompose 9 as done above. In the end, we just need to keep track of how many divisions by 4 we did so they can be incorporated in the final result.

How fast is this method?
How does it compare with other classical methods of checking for squareness of an integer?

$\endgroup$
3
  • 2
    $\begingroup$ You haven't really explained how you find the index $k$ such that $T_k=\frac{ab}2$. A linear search by adding consecutive cubes will not be fast for large numbers. Calculating a square root using the Newton Raphson method is blazingly fast however. $\endgroup$ Aug 20, 2021 at 15:36
  • $\begingroup$ @JaapScherphuis, you add consecutive cubes and check against the value of $T_{k}^2$. We could use a table of values $(T_{k},k)$ to speed up the process. But since I am not a programmer I wouldn't know the best way to speed up the method. $\endgroup$
    – user25406
    Aug 20, 2021 at 18:52
  • $\begingroup$ One way to make the method more efficient is to use a sparse table of $(T_{n}^2,n^3)$. $\endgroup$
    – user25406
    Oct 9, 2021 at 14:15

2 Answers 2

1
$\begingroup$

Up to about 2**13, the rate at which Sum(i**3, (i, 1, k)) = (k*(k + 1)/2)**2 grows faster than 2**x. Past 13, it grows slower and takes longer and longer to determine the value of k for a given value of (ab/2)**2. This means that bisection for the bracketing square root of the number being tested will be faster; conversely, the number of Tk values needed to reach the desired value will be (too) large and costly to compute/store. e.g. try the method for n = primorial(30)**2 = 31610054640417607788145206291543662493274686990**2

The following is my implementation of the method in Python (using SymPy to compute the multiplicity of the factor of 2 (i.e. with trailing):

from bisect import bisect_left
from sympy import trailing

_tk2 = [1]
def tk2(i):
    # T(k)**2 = Sum(i**3, (i, 1, k)) = (k*(k+1)/2)**2
    k = len(_tk2)
    while i > _tk2[-1]:
        k += 1
        _tk2.append(k**3 + _tk2[-1])
    k = _tk2[bisect_left(_tk2, i)]
    if k == i:
        return k

def tk2_bin(i):
    if i == 1: return 1
    if i == 2: return
    if i == 3: return 2
    kold = k = 1
    j = 1
    while j<i:
        kold = k
        k*=2
        j = k*(k+1)//2
    if j == i:
        return k
    while k - kold > 1:
        dk = (k - kold)//2
        kk = kold + dk
        j = kk*(kk+1)//2
        if j > i:
            k = kk
        elif j < i:
            kold = kk
        else:
            return kk

def nr(n):
    x = n//2
    while 1:
        x2 = (x + n//x)//2
        if abs(x2 - x) < .5:
            return round(x)**2 == n
        x = x2

def isq(n):
    if not n:
        return True
    if n < 0:
        return False
    assert n == int(n)
    # remove powers of 4
    if not n % 2:
        t = trailing(n)
        if t % 2:
            return False
        n >>= t
    if n == 1:
        return True
    ab, r = divmod(n - 1, 4)
    if r:
        return False
    if ab % 2:
        return False
    k = tk2_bin(ab//2)  # tk2((ab//2)**2)
    return k is not None
$\endgroup$
7
  • $\begingroup$ Can the speed of calculating $T_{k}^2$ be increased if we use a sparse table of $(T_{k}^2,k^3)$. $\endgroup$
    – user25406
    Jan 29, 2022 at 15:13
  • $\begingroup$ I don't think so. I think that is what I implemented in _tk2 which is a list whose kth entry is Tk^2. For a big odd number the number of terms to calculate Tk^2 is unwieldy and other methods are much faster. The Newton Raphson check for primorial(30)**2 is very fast whereas the routine I tried above does not complete successfully. I wonder how doing a binary search for k using T(k)**2 = Sum(i**3, (i, 1, k)) = (k*(k+1)/2)**2 would work... $\endgroup$
    – smichr
    Jan 29, 2022 at 15:33
  • $\begingroup$ The binary search for k almost competes with naïve NR but takes about 3X longer in my tests of squares of numbers with 10 to 100 digits. Neither compares to the optimized routines in mpmath for implementing a NR method of computing a sqrt and remainder for a number github.com/fredrik-johansson/mpmath/blob/…. This is what SymPy uses and the is_square function is orders of magnitude faster than the naive NR. $\endgroup$
    – smichr
    Jan 29, 2022 at 16:50
  • $\begingroup$ I updated the code with the naive NR method that I used and the binary search for k, tk2_bin. $\endgroup$
    – smichr
    Jan 29, 2022 at 16:55
  • $\begingroup$ Thanks for the effort and the tests you did. I will accept your answer and hope that one day someone will find a way to make the method competitive with Newton-Raphson. $\endgroup$
    – user25406
    Jan 30, 2022 at 12:45
0
$\begingroup$

Here's a method of checking if a number is a square that is much faster that the one based on the use of a sum of cubes given in the post above.

It uses the same decomposition of a potential square $N=n^2$. That decompostion also provides the decomposition of numbers having the same sum of factors as $N$ itself.
The numbers with the same sum of factors of $N=81$ (used in the post above) are: $80$, $77$, $72$, $65$, $56$...These numbers can be written as $N-1^2$, $N-2^2$, $N-3^2$, $N-4^2$...It's easier to use numbers which differ from $N$ by an odd square $1^2,3^3,5^2$...that is the even numbers.
In the post above, it was shown that $N=81$ can be written as:
$N=81=a^2 +2*20 + b^2= a^2 + 2*(2*T_{k}) + b^2$.
The even numbers aligned with $2T_{k}=20$, that is $(20-2=18), (18-4=14), (14-6=8)$ are just the even numbers aligned (sharing the same sum of factors) with $N=81$ divided by $4$. That is $(80=4*20)$, $(72=4*18)$, $(56=4*14)$ and $(32=4*8)$.
These numbers can be written as:
$80=81-1^2$
$72=81-3^2$
$56=81-5^2$
$32=81-7^2$
The simple fact that these numbers differ by a square from $N=81$ prove that $N=81$ itself is a square. This test can be used for large numbers since it is enough to consider $3$ even numbers and show that they differ by a square from $N$. This test doesn't provide the square root of N of course but it definitely shows if $N$ is a square.

The odd numbers sharing the same sum of factors as $N=81$ can also be shown to differ by a square from $N=81$.
For example $77=(18+20) + (15+24)=38 + 39 = 81 - 2^2$. The numbers $18, 20$ are known but not $15, 24$ but their sum is known to differ from $(18+20)$ by $1$ since $77$ can be written as $77= (77-1)/2 + (77+1)/2 =38 + 39$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .