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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s