by Arne Sommer

# Magical Sum with Raku and Perl

 Published 4. December 2020.

This is my response to the Perl Weekly Challenge #089.

## Challenge #089.1: GCD Sum

You are given a positive integer `@N`.

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

Example 1 ```Input: 3 Output: 3 gcd(1,2) + gcd(1,3) + gcd(2,3) ``` Example 2 ```Input: 4 Output: 7 gcd(1,2) + gcd(1,3) + gcd(1,4) + gcd(2,3) + gcd(2,4) + gcd(3,4) ```

#### Divisors

Raku does not have a built-in function for this, but I did in fact implement a procedure for this in my Centenary Sequences with Raku - Part 5: Divisors and Factors article. We can reuse it, as is.

File: gcd-sum ```#! /usr/bin/env raku subset PositiveInt of Int where * > 0; #  unit sub MAIN (PositiveInt \$N, :v(:\$verbose)); #  say (1..\$N).combinations(2).map( *.&gcd ).sum; #  sub gcd (@numbers) #  { my %common = divisors(@numbers) (&) divisors(@numbers); # [3a] my @common = %common.keys.sort; # [3b] my \$gcd = @common[* -1]; # [3c] say ":: GCD(@numbers, @numbers) -> \$gcd" if \$verbose; return \$gcd; # [3d] } sub divisors (\$number, :\$not-self, :\$not-one) #  { my @divisors; for (\$not-one ?? 2 !! 1) .. \$number/2 -> \$candidate { @divisors.push: \$candidate if \$number %% \$candidate; } @divisors.push: \$number unless \$not-self; return @divisors; } ```

 Positive integers only.

 Take all the combinations of two numbers among the numbers `1` to `\$N`, and apply the «gcd» procedure on those combinations (with `map`. Note the `.&` syntax for calling a procedure with a method invocation look-alike syntax. This in effect reduces the list of pairs to a list of single values. And finally we apply `.sum` to add those values together.

 Get the list of divisors from both numbers, and get the intersection of them (the values present in both lists) [3a]. The result is a hash-like structure, so we must use `.keys` to get the actual values. The keys are unsorted, so we remedy that with `.sort` [3b]. The last value in the array is the largest, and thus the greatest common divisor [3c, 3d].

 Copied verbatim, as said in the preamble.

See docs.raku.org/language/operators#methodop_.& for more information about the special procedure invocation syntax `.&`.

See docs.raku.org/routine/(&), infix ∩ for more information about the intersection operator `(&)`, also available as the Unicode character `∩`.

Running it:

```\$ ./gcd-sum 3 3 \$ ./gcd-sum 4 7 ```

With verbose mode:

```\$ ./gcd-sum -v 3 :: GCD(1, 2) -> 1 :: GCD(1, 3) -> 1 :: GCD(2, 3) -> 1 3 \$ ./gcd-sum -v 4 :: GCD(1, 2) -> 1 :: GCD(1, 3) -> 1 :: GCD(1, 4) -> 1 :: GCD(2, 3) -> 1 :: GCD(2, 4) -> 2 :: GCD(3, 4) -> 1 7 ```

### A Perl Version

This is straight forward translation of the Raku version.

File: gcd-sum-perl ```#! /usr/bin/env perl use strict; use feature 'say'; use feature 'signatures'; no warnings qw(experimental::signatures); use Algorithm::Combinatorics 'combinations'; use List::MoreUtils 'duplicates'; use Getopt::Long; my \$verbose = 0; GetOptions("verbose" => \\$verbose); my \$N = \$ARGV // die "Please specify an integer > 0"; die "Please specify an integer > 0" unless \$N =~ /^[1-9]\d*\$/; my @all = (1 .. \$N); my \$sum = 0; for my \$pair (combinations(\@all, 2)) { \$sum += gcd(@\$pair); } say \$sum; sub gcd (\$a, \$b) { my @a = divisors(\$a); my @b = divisors(\$b); my @common = duplicates(@a, @b); #  my \$gcd = \$common[\$#common]; # [1a] say ":: GCD(\$a, \$b) -> \$gcd" if \$verbose; return \$gcd; } sub divisors (\$number) { my @divisors = (1); for my \$candidate (2 .. \$number/2) { push(@divisors, \$candidate) if \$number % \$candidate == 0; } push(@divisors, \$number); return @divisors; } ```

 Instead of the Intersection (in Raku), I use «List::MoreUtils::duplicates» which gives the values that occur more than once. The order of the values is left as is, so the largest value is at the end [1a].

##### List::MoreUtils Problems

The program above crashed for me, as Perl was unable to locate «duplicates»:

```./gcd-sum-perl 4 Could not find sub 'duplicates' exported by List::MoreUtils at ./gcd-sum-perl line 9. BEGIN failed--compilation aborted at ./gcd-sum-perl line 9. ```

I have no idea why it failed. But a workaround is to remove the «use» line, and add the procedure to the program.

A version of the program («gcd-sum-perl-errorfix») doing just that, is included in the zip file.

Note that I had the excact same problem in my article Two Triplets with Raku and Perl.

Running it gives the same result as the Raku version:

```\$ ./gcd-sum-perl-errorfix 3 3 \$ ./gcd-sum-perl-errorfix 4 4 \$ ./gcd-sum-perl-errorfix -v 3 :: GCD(1, 2) -> 1 :: GCD(1, 3) -> 1 :: GCD(2, 3) -> 1 3 \$ ./gcd-sum-perl-errorfix -v 4 :: GCD(1, 2) -> 1 :: GCD(1, 3) -> 1 :: GCD(1, 4) -> 1 :: GCD(2, 3) -> 1 :: GCD(2, 4) -> 2 :: GCD(3, 4) -> 1 7 ```

## Challenge #089.2: Magical Matrix

Write a script to display matrix as below with numbers `1 - 9`. Please make sure numbers are used once.

```[ a b c ] [ d e f ] [ g h i ] ``` So that it satisfies the following: ```a + b + c = 15 d + e + f = 15 g + h + i = 15 a + d + g = 15 b + e + h = 15 c + f + i = 15 a + e + i = 15 c + e + g = 15 ```
File: magical-matrix ```#! /usr/bin/env raku unit sub MAIN (:v(:\$verbose), :a(:\$all));  for (1..9).permutations -> @candidate  { say ":: @candidate[]" if \$verbose; my (\$a, \$b, \$c, \$d, \$e, \$f, \$g, \$h, \$i) = @candidate; #  next unless \$a + \$b + \$c == 15; # [2a] next unless \$d + \$e + \$f == 15; next unless \$g + \$h + \$i == 15; next unless \$a + \$d + \$g == 15; next unless \$b + \$e + \$h == 15; next unless \$c + \$f + \$i == 15; next unless \$a + \$e + \$i == 15; next unless \$c + \$e + \$g == 15; say "[ { @candidate[0..2] } ]"; #  say "[ { @candidate[3..5] } ]"; say "[ { @candidate[6..8] } ]"; say "" if \$all; last unless \$all; #  } ```

 This is a brute force approach. I generate all the possible permutations of the numbers 1 to 9 (with the three matrix rows laid out after each other in a single list).

 Then I assign the values to the variables given in the equations in the challenge, and check that they are satisfied [2a].

 If they are, we have a match.

 Stop after the first match, unless asked for all of them.

Running it:

```\$ ./magical-matrix [ 2 7 6 ] [ 9 5 1 ] [ 4 3 8 ] ```

Running it with verbose mode will generate a lot of output, so I'll refrain from showing it. The «-a» (all) option shows all the matches, and not just the first:

```\$ ./magical-matrix -a [ 2 7 6 ] [ 9 5 1 ] [ 4 3 8 ] [ 2 9 4 ] [ 7 5 3 ] [ 6 1 8 ] [ 4 3 8 ] [ 9 5 1 ] [ 2 7 6 ] [ 4 9 2 ] [ 3 5 7 ] [ 8 1 6 ] [ 6 1 8 ] [ 7 5 3 ] [ 2 9 4 ] [ 6 7 2 ] [ 1 5 9 ] [ 8 3 4 ] [ 8 1 6 ] [ 3 5 7 ] [ 4 9 2 ] [ 8 3 4 ] [ 1 5 9 ] [ 6 7 2 ] ```

### Perl

This is also a straight forward translation of the Raku version.

File: magical-matrix-perl ```#! /usr/bin/env perl use strict; use feature 'say'; use Getopt::Long; use Algorithm::Combinatorics 'permutations'; my \$verbose = 0; my \$all = 0; GetOptions("verbose" => \\$verbose, "all" => \\$all); my @source = 1..9; for my \$list (permutations(\@source)) { my @candidate = @\$list; say ":: " . join(@candidate, ", ") if \$verbose; my (\$a, \$b, \$c, \$d, \$e, \$f, \$g, \$h, \$i) = @candidate; next unless \$a + \$b + \$c == 15; next unless \$d + \$e + \$f == 15; next unless \$g + \$h + \$i == 15; next unless \$a + \$d + \$g == 15; next unless \$b + \$e + \$h == 15; next unless \$c + \$f + \$i == 15; next unless \$a + \$e + \$i == 15; next unless \$c + \$e + \$g == 15; say "[ " . join(" ", @candidate[0..2]) . " ]"; say "[ " . join(" ", @candidate[3..5]) . " ]"; say "[ " . join(" ", @candidate[6..8]) . " ]"; say "" if \$all; last unless \$all; } ```

Running it gives the same result as the Raku version:

```\$ ./magical-matrix-perl [ 2 7 6 ] [ 9 5 1 ] [ 4 3 8 ] \$ ./magical-matrix-perl -a [ 2 7 6 ] [ 9 5 1 ] [ 4 3 8 ] [ 2 9 4 ] [ 7 5 3 ] [ 6 1 8 ] [ 4 3 8 ] [ 9 5 1 ] [ 2 7 6 ] [ 4 9 2 ] [ 3 5 7 ] [ 8 1 6 ] [ 6 1 8 ] [ 7 5 3 ] [ 2 9 4 ] [ 6 7 2 ] [ 1 5 9 ] [ 8 3 4 ] [ 8 1 6 ] [ 3 5 7 ] [ 4 9 2 ] [ 8 3 4 ] [ 1 5 9 ] [ 6 7 2 ] ```

And that's it.