# Perl Weekly Challenge 116: Sum of Squares

by Abigail

## Challenge

You are given a number $N >= 10. Write a script to find out if the given number $N is such that sum of squares of all digits is a perfect square. Print 1 if it is otherwise 0.

### Examples

Input: $N = 34 Ouput: 1  $$3^2 + 4^2 = 9 + 16 = 25 = 5^2$$ Input:$N = 50
Output: 1


$$5^2 + 0^2 = 25 + 0 = 25 = 5^2$$

Input: $N = 52 Output: 0  $$5^2 + 2^2 = 25 + 4 = 29$$ ## Solution 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$$. #### Taking the square root 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. #### Counting upwards 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 \leq 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$$. #### Binary search 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} \leq S < 2^k$$. We can now use binary search to find a number $$2^{k-1} \leq 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}})$$. #### Preprocessing 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. ### Perl 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. #### Taking the square root $is_square = $sum_of_squares == int (.5 + sqrt$sum_of_squares) ** 2


We'r taking the square root of $sum_of_squares, rounding it to the nearest integer, squaring that, and comparing it to $sum_of_squares. If equal, $sum_of_squares is a square, else, it is not. #### Counting upwards my$root = 0;
$root ++ while$root * $root <$sum_of_squares;
$is_square =$sum_of_squares == $root *$root;


We simply count upwards as long as the square of our number is less thatn $sum_of_squares. Then we check whether we overshot or not: if we did, it's not a square, else it is. #### Binary search 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; } }  #### Preprocessing 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.

### Other languages

We have implemenations based on the Taking the square root method in AWK, C, Lua, Node.js, Python and Ruby. And an implemenation based on Binary search in Bash.