I’ve been doing the Perl Weekly
Challenges. The
latest
involved GCDs and magic squares. (Note that this is open until 6
December 2020.)

TASK #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`

.

There doesn't appear to be an obvious optimisation listed at
OEIS, so I did this naïvely.

```
sub gs {
my $n=shift;
my $tot=$n-1; # gcd(1,2)+gcd(1,3)+...+gcd(1,n)
foreach my $a (2..$n-1) {
$tot+=sum(map {gcd($a,$_)} ($a+1..$n));
}
return $tot;
}
```

Perl doesn't have a built-in `gcd`

, so rather than use one from CPAN I
implemented Stein's
algorithm (on the
basis that I've written Euclid's before). This is rather more complex
than the main problem, but I made it non-recursive for clarity..

```
sub gcd {
my ($a,$b)=@_;
if ($a==0) {
return $b;
}
if ($b==0) {
return $a;
}
my $d=0;
while (1) {
if ($a == $b) {
return $a << $d;
}
my $aa=($a % 2 == 0);
my $bb=($b % 2 == 0);
```

We do different things based on whether they're both even, only one
is, or neither is.

```
if ($aa && $bb) {
$a >>= 1;
$b >>= 1;
$d++;
} elsif ($aa) {
$a >>= 1;
} elsif ($bb) {
$b >>= 1;
} else {
my $c=abs($a-$b);
$a=min($a,$b);
$b=$c >> 1;
}
}
}
```

Raku came out basically the same, except that `sum`

and `min`

are
built-in and its binary shift operators look weird. Python has its own
`gcd`

, as does Ruby, and they basically look the same too. But Rust…
all right, I had to write a `min`

function too. (Or steal it out of
the Blandy/Orendorff *Programming Rust*.)

TASK #2 › Magical Matrix

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

i.e. a 3×3 magic square. But there is only one 3×3 magic square
(modulo reflections and rotations) and that would have been boring. So
instead I used the Siamese algorithm (de la Loubère, 1688), with a
minor variation so that indices were always incremented (so as to
avoid, when I got to the Rust version, the conversions I had to do
last time).

This should produce a magic square of any odd-numbered size, with any
starting number and increment.

```
sub ms {
my ($order,$start,$inc)=@_;
my $m;
foreach (1..$order) {
push @{$m},[(0) x $order];
}
my ($x,$y)=(int($order/2)+1,int($order/2));
my $n=$start;
while (1) {
$m->[$x][$y]=$n;
$n+=$inc;
my ($xa,$ya)=(($x+1) % $order,($y+1) % $order);
if ($m->[$xa][$ya]>0) {
($xa,$ya)=(($x+2) % $order,$y);
if ($m->[$xa][$ya]>0) {
last;
}
}
($x,$y)=($xa,$ya);
}
return $m;
}
```

Actually printing it out is a job for library code.

Raku, Python and Ruby were similar, and even Rust is recognisably the
same algorithm:

```
fn ms(order: usize, start: i64, inc: i64) -> Vec<Vec<i64>> {
let mut m=vec![vec![0; order]; order];
let mut x: usize=(order/2)+1;
let mut y: usize=order/2;
let mut n=start;
loop {
m[x][y]=n;
n += inc;
let mut xa=(x+1) % order;
let mut ya=(y+1) % order;
if m[xa][ya] > 0 {
xa=(x+2) % order;
ya=y;
if m[xa][ya] > 0 {
break;
}
}
x=xa;
y=ya;
}
return m;
}
```

Full code on
github.

Comments on this post are now closed. If you have particular grounds for adding a late comment, comment on a more recent post quoting the URL of this one.