The first task of this weeks challenge reads:

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.