TL;DR

Here we are with TASK #1 from the Perl Weekly Challenge #089. Enjoy!

The challenge

You are given a positive integer $N. Write a script to sum GCD of all possible unique pairs between 1 and $N.

The questions

I can only guess that an input of 1 yields a 0, which is probably something that can be argued. Is the sum of “nothing” 0?

But apart from this and what to do with invalid input… I can’t find anything particularly naggy to ask.

The solution

I have to be honest: I hate manwar.

Oh wait! Don’t get me wrong! My hate is in the same spirit as lazyness, impatience and hubris are the virtues of a programmer - i.e. I do in a very particular (and humorous) sense.

Well… where does this hatred come from? It’s simple: not only these challenges force me to think, but more often than I’m willing to admit they make me feel a combination of stupid and lazy (in a bad sense).

For so many of them there’s an inner voice that tells me that my simple, boring, immediate go-to solution is not really what we are supposed to come up with. Then there’s another inner voice that argues that it’s a solution and it might be good in a lot of situation, so until we (at this point it’s a mess of inner personas talking) know that it’s not sufficient the problem is not worth any more time.

And yet there’s an inner party (yes, all these personas had to organize and elect a leader because there were too many of them) that argues that these challenges are supposed to emerge our thought process, and I tend to lean on the boring, inefficient side a bit too much.

So there I am thinking a lot, with a plethora of persona arguing in my head, and with the sensation that yes, there’s got to be a better way to do the task. OK, I’ll wait to read it from Abigail’s solution this week too 😂

So… let’s come to the task at hand. This time I’ll go straight to the solution:

#!/usr/bin/env perl
use 5.024;
use warnings;
use experimental qw< postderef signatures >;
no warnings qw< experimental::postderef experimental::signatures >;

sub gcd { my ($A, $B) = @_; ($A, $B) = ($B % $A, $A) while $A; return $B }

sub GCD_sum ($N) {
   my $sum = $N - 1; # gcd(1, $x) = 1
   for my $lo (2 .. $N - 1) {
      $sum += gcd($lo, $_) for $lo + 1 .. $N;
   }
   return $sum;
}

say GCD_sum(shift || 4);

The gcd function is just Euclid’s algorithm in a one-liner.

The main function starts the sum from $N - 1 because the greatest common divisor by any positive integer and 1 is just… 1. We are dealing with distinct pairs, so we cannot count $(1, 1)$.

The two nested loops make sure that there’s no pair of integers, and just calculates the greatest common divisor betewen any possible applicable pair.

I guess this might be enhanced but… well, go back to the start of this section!