# Perl Weekly Challenge 89, Part 1

You are given a positive integer `\$N`.

Write a script to sum `GCD` of all possible unique pairs between `1` and `\$N`.

### Overview

This is a pretty simple exercise. Using two nested loops, we can easily iterate over all unique pairs. And only a few weeks ago we needed to calculate the greatest common divisor, so we can reuse the code we wrote then.

## Perl

To calculate the `gcd`, we will be using Stein’s Algorithm, which is an improvement over the traditional way of calculating the `gcd`, by factoring out factors of `2` as much as possible. Since we need to calculate the `gcd` many times, and the algorithm is recursive, we use a cache:

```sub stein;
sub stein (\$u, \$v) {
state \$cache;
\$\$cache {\$u, \$v} //= sub (\$u, \$v) {
return \$u if \$u == \$v || !\$v;
return \$v if             !\$u;
my \$u_odd = \$u % 2;
my \$v_odd = \$v % 2;
return stein (\$u >> 1, \$v >> 1) << 1 if !\$u_odd && !\$v_odd;
return stein (\$u >> 1, \$v)           if !\$u_odd &&  \$v_odd;
return stein (\$u,      \$v >> 1)      if  \$u_odd && !\$v_odd;
return stein (\$u - \$v, \$v)           if  \$u     >   \$v;
return stein (\$v - \$u, \$u);
} -> (\$u, \$v);
}
```

If both arguments are even, it divides both of them by `2`, and recurses, multiplying the result by `2`. If one argument is even, it divides that argument by `2`, and recurses. Otherwise (that is, when both arguments are odd), the smaller argument is subtracted from the larger, and we recurse.

Now it’s just a matter of reading the target number, creating loops, and summing the results:

```while (my \$N = <>) {
chomp \$N;
my \$sum = 0;
foreach my \$i (1 .. \$N) {
foreach my \$j (\$i + 1 .. \$N) {
\$sum += stein \$i, \$j;
}
}
say \$sum;
}
```

Find the complete program on GitHub.