Perl Weekly Challenge 116: Sum of Squares

The challenge can be split up into two different tasks: summing the squares of the digits, and determining whether the result is a perfect square or not.

Summing the squares of the digits is straightforward.

We offer four different ways to determine whether the sum of the squares of the digits is a square number. We'll call the sum of the squares of the digits $S$.

First option is take the square root. We cannot simply check whether the square root is an integer: we're now dealing with floating point numbers. Instead, we round the square root to the nearest integer, square that, and compare that with $S$. If they're the same, we have a perfect square.

The advantange of this method is that quick. The disadvantage is that we have to deal with floating point numbers. Which means we may have rounding errors.

The second method we offer is to start counting from $1$, and squaring each number. If we hit $S$, $S$ is a perfect square. If we go past $S$, $S$ is not a perfect square.

This may sound inefficient, but it's not. If the input has $N$ digits, then $S\le 81\cdot N$ (if the number contains only $9$s). So, we at most have to count till $9\sqrt{N}$ before we know whether $S$ is a perfect square. Even if we have million digits, we at most have to check 9000 numbers. So, the counting part can be done in $\mathcal{O}(\sqrt{N})$ time, which is less than the $\mathcal{O}(N)$ which is required to calculate $S$.

Instead of counting from $1$, we can start at $1$ and doubling the number till its square exceeds $S$. Say, we have doubled $k$ times, and now we have $2^{k-1}\le S<2^k$. We can now use binary search to find a number $2^{k-1}\le l<2^k$ such that $l^2=S$. If such a number exists, $S$ is a perfect square, else it's not.

Since $k=\mathcal{O}(\log \sqrt{N})$, the running time of this is $\mathcal{O}(\log \sqrt{N})$.

We can precalculate the first 9000 squares. Then, given an $S$, we can see check whether this is a square by checking it against the precomputed numbers. This is fast, particular if we have many numbers we want to check. The disadvantage is that it doesn't get all the numbers. But the first $S$ for which this goes wrong is 81,018,001. And a number needs more than 1,000,222 digits before the sum of the squares of its digits can exceed 81,018,001.

We have the input number in $_.

First, calculating the sum of the squares of the numbers:

my $sum_of_squares = sum map {$_ * $_} /[1-9]/g;

Note that we ignore 0s, and the square of 0 is 0.

First, we find a number whose square is larger than $sum_of_squares:

my $root_min = 0;
my $root_max = 1;
$root_max *= 2 while $root_max * $root_max < $sum_of_squares;

Then we use binary search to zoom into the square root of $sum_of_squares. Either we hit it (and hence, the square root of $sum_of_squares is an integer, and thus, $sum_of_squares is a perfect square), or we don't (and then, $sum_of_squares is not a perfect square):

while ($root_min < $root_max) {
    my $root_mid = int (($root_min + $root_max) / 2);
    my $square_mid = $root_mid * $root_mid;
    if ($square_mid == $sum_of_squares) {
        $is_square = 1;
        last;
    }
    if ($square_mid < $sum_of_squares) {
        $root_min = $root_mid + 1;
    }
    else {
        $root_max = $root_mid;
    }
}

First, the preprocessing:

my %squares = map {$_ * $_ => 1} 1 .. 9000;

Then it's just a matter of a lookup:

$is_square = $squares {$sum_of_squares};

Find the full program on GitHub.