Perl Weekly Challenge: Week 159
Challenge 1:
Farey Sequence
You are given a positive number,
$n.Write a script to compute
Farey Sequenceof the order$n.
Example 1:
Input: $n = 5
Output: 0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1.
Example 2:
Input: $n = 7
Output: 0/1, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 2/5, 3/7, 1/2, 4/7, 3/5, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 1/1.
Example 3:
Input: $n = 4
Output: 0/1, 1/4, 1/3, 1/2, 2/3, 3/4, 1/1.
I had no idea what a Farey sequence is and even after reading this Wikipedia page I was none the wiser. Luckily, the page also included some Python code for calculating the sequences and with a small amount of effort, I was able to translate and adapt it. This is the Raku version.
my ($a, $b, $c, $d) = (0, 1, 1, $n);
print "$a/$b ";
while $c <= $n {
my $k = ($n + $b) div $d;
($a, $b, $c, $d) = ($c, $d, $k * $c - $a, $k * $d - $b);
print "$a/$b ";
}
print "\n";
I don't do a lot of Python so one thing in the original code which confused me at first was the use of the // operator. Apparently it is 'division with floor'. Raku has it (because of course Raku has everything) but calls it div.
This is the Perl version:
my ($a, $b, $c, $d) = (0, 1, 1, $n);
print "$a/$b ";
while ($c <= $n) {
my $k = floor(($n + $b) / $d);
($a, $b, $c, $d) = ($c, $d, $k * $c - $a, $k * $d - $b);
print "$a/$b ";
}
print "\n";
Almost exactly the same except there is no div so we have to implement it ourselves using the floor()
function which you can get with use POSIX qw/ floor /;
Challenge 2:
Moebius Number
You are given a positive number $n.
Write a script to generate the Moebius Number for the given number. Please refer to the Wikipedia page for more information.
Example 1:
Input: $n = 5
Output: -1
Example 2:
Input: $n = 10
Output: 1
Example 3:
Input: $n = 20
Output: 0
To solve this challenge in Perl, we need a routine that provides prime factors for a particular number. I had code to do that written for previous challenges but I'm going to show it again because it has been a very long time since I mentioned it and also because I had to adapt it slightly. The original version excluded 1 and (possibly) the number itself as prime factors whereas in this problem we do want the number itself assuming it is prime. 1 is still out though.
sub factorize {
my ($n, $primeFactors) = @_;
if ($n < 2) {
return;
}
my $p = nextPrime(1);
while ($p <= $n) {
if ($n % $p == 0) {
push @{$primeFactors}, $p;
factorize($n / $p, $primeFactors);
}
$p = nextPrime();
}
}
factorize() is recursive. As it was reasonably fast for the numbers I threw at it, I did not bother with memoization. It requires the use of nextPrime() which in turn uses isPrime() but as I have used those two functions extensively in past challenges and talked about them, I'm not going to discuss them now.
Once we know about the prime factors of $n we can calculate the Moebius number for it.
if (squared(\@factors)) {
say 0;
If it has atleast 1 squared factor we print 0. I gather 'squared factor' means two or more prime factors are the same number i.e. 4 has 2 and 2 because 2 x 2 = 4. This necessitated another change to factorize() because the original only returned unique prime factors not all of them. I worked out if there were duplicate prime factors in
another function called squared().
sub squared {
my ($factors) = @_;
my %count;
for my $factor (@{$factors}) {
$count{$factor}++;
}
return (scalar grep { $count{$_} > 1} keys %count) > 0;
}
squared() adds the factors to a hash and looks for keys that have a value greater than 1. If there is atleast 1
such key, the function returns true.
If there are no squared factors, we count how many prime factors there are and if that number is odd, print -1, or if it is even, print 1.
} else {
say 0 + (scalar @factors % 2) ? -1 : 1;
}
The 0 + is there to prevent a warning from Perl.
This is what factorize() looks like in Raku:
sub factorize(Int $n, @primeFactors) {
if $n < 2 {
return;
}
my $i = 0;
my @primes = (1 .. ∞).grep({ .is-prime });
my $p = @primes[$i];
while $p <= $n {
if $n %% $p {
@primeFactors.push($p);
factorize($n div $p, @primeFactors);
return;
}
$p = @primes[$i++];
}
}
Because Raku already has .is-prime() there is no need to provide our own code for that or nextPrime().
@primes is a lazy list so this is quite efficient.
And this is how we calculate the Moebius number.
my @factors;
factorize($n, @factors);
if (@factors.categorize({ $_ })).values.any > 1 {
say 0;
} else {
say (@factors.elems % 2) ?? -1 !! 1;
}
.categorize() does the job of creating the hash we used in the Perl version and .any() replaces the grep so
we don't need a separate squared() function at all.