Perl solution for week 89/part 1

1 files changed, 56 insertions, 0 deletions

diff --git a/challenge-089/abigail/perl/ch-1.pl b/challenge-089/abigail/perl/ch-1.pl
new file mode 100644
index 0000000000..4b1cf61229
--- /dev/null
+++ b/challenge-089/abigail/perl/ch-1.pl
@@ -0,0 +1,56 @@
+#!/opt/perl/bin/perl
+
+use 5.032;
+
+use strict;
+use warnings;
+no  warnings 'syntax';
+
+use experimental 'signatures';
+use experimental 'lexical_subs';
+
+#
+# Challenge:
+#
+# You are given a positive integer $N.
+#
+# Write a script to sum GCD of all possible unique pairs between 1 and $N.
+#
+
+#
+# Back in challenge 82, we needed a GCD subroutine as well.
+# We copied that one, and added caching.
+#
+
+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);
+}
+
+
+#
+# Iterate over all pairs, sum the gcd.
+#
+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;
+}
+
+__END__