RogerBW's Blog

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.