## Perl Weekly Challenge 159: Farey Sequence and Möbius Number

These are some answers to the Week 159 of the Perl Weekly Challenge organized by Mohammad S. Anwar.

Spoiler Alert: This weekly challenge deadline is due in a few days from now (on April 10, 2022 at 24:00). This blog post offers some solutions to this challenge, please don’t read on if you intend to complete the challenge on your own.

Write a script to compute Farey Sequence of 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.
``````

The Farey sequence of order n is the sequence of completely reduced fractions, either between 0 and 1, or without this restriction, which when in lowest terms have denominators less than or equal to n, arranged in order of increasing size. See this Wikipredia page for additional information.

With the restricted definition, each Farey sequence starts with the value 0, denoted by the fraction 0/1, and ends with the value 1, denoted by the fraction 1/1.

### Farey Sequence in Raku

In Raku, the Rat rational data type stores a rational number as a pair of a numerator and denominator. This makes things quite simple, since the same object can be used both for numeric comparison and for displaying it as a completely reduced fraction (using the `numerator` and `denominator` methods). We use two nested `for` loops to generate all possible fractions, store them in a `Set` to remove duplicates and sort them.

``````sub farey (Int \$n) {
my @out;
for 1..\$n -> \$den {
for 0..\$den -> \$num {
push @out, \$num/\$den;
}
}
return @out.Set;
}
for 3..7 -> \$test {
say "\$test -> ", map { .numerator ~ "/" ~ .denominator },  sort farey(\$test).keys;
}
``````

This program displays the following output:

``````\$ raku ./farey.raku
3 -> (0/1 1/3 1/2 2/3 1/1)
4 -> (0/1 1/4 1/3 1/2 2/3 3/4 1/1)
5 -> (0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1)
6 -> (0/1 1/6 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 5/6 1/1)
7 -> (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)
``````

### Farey Sequence in Perl

In Perl, we simulate Raku’s `Rat` data type by using anonymous arrays containing a numerator and a denominator. For sorting or storing in a hash (in order to remove duplicates), we use the numerical value of the fraction, whereas we use a string for output.

``````use strict;
use warnings;
use feature "say";

sub farey {
my \$n = shift;
my (@out, %seen);
for my \$den (1..\$n) {
for my \$num (0..\$den) {
next if exists \$seen{\$num/\$den};
push @out, [\$num, \$den];
\$seen{\$num/\$den} = 1;
}
}
return @out;
}
for my \$test (3..7) {
my @result = sort { \$a->[0]/\$a->[1] <=> \$b->[0]/\$b->[1] } farey(\$test);
print "\$test: ";
print "\$_->[0]/\$_->[1] " for @result;
say "";

}
``````

This program displays the following output.

``````\$ perl ./farey.pl
3: 0/1 1/3 1/2 2/3 1/1
4: 0/1 1/4 1/3 1/2 2/3 3/4 1/1
5: 0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1
6: 0/1 1/6 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 5/6 1/1
7: 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
``````

You are given a positive number `\$n`.

Example 1:

``````Input: \$n = 5
Output: -1
``````

Example 2:

``````Input: \$n = 10
Output: 1
``````

Example 3:

``````Input: \$n = 20
Output: 0
``````

For any positive integer n, the Möbius Function μ has values in {−1, 0, 1} depending on the factorization of n into prime factors:

• μ(n) = +1 if n is a square-free positive integer with an even number of prime factors.

• μ(n) = −1 if n is a square-free positive integer with an odd number of prime factors.

• μ(n) = 0 if n has a squared prime factor.

### Moebius Number in Raku

The `Möbius` subroutine performs the factorization of its input integer. If any of the exponents is larger than 1, then the input number is not square-free and the subroutine returns 0. Otherwise, the subroutine returns 1 if the number of prime factors is even and -1 if it is odd.

``````sub möbius (\$n is copy) {
my %factors;
for 2..\$n -> \$i {
while  \$n %% \$i {
%factors{\$i}++;
\$n /= \$i;
}
}
return 0 if %factors.values.any > 1;
return 1 if (%factors.keys.elems %% 2);
return -1;
}
say "\$_: ", möbius \$_ for 1..20;
``````

This program displays the following output:

``````\$ raku ./moebius.raku
1: 1
2: -1
3: -1
4: 0
5: -1
6: 1
7: -1
8: 0
9: 0
10: 1
11: -1
12: 0
13: -1
14: 1
15: 1
16: 0
17: -1
18: 0
19: -1
20: 0
``````

### Moebius Number in Perl

This is a port to Perl of the Raku program above: the `Moebius` subroutine performs the factorization of its input integer. If any of the exponents is larger than 1, then the input number is not square-free and the subroutine returns 0. Otherwise, the subroutine returns 1 if the number of prime factors is even and -1 if it is odd.

``````use strict;
use warnings;
use feature "say";

sub moebius {
my \$n = shift;
my %factors;
for my \$i (2..\$n) {
while  (\$n % \$i == 0) {
\$factors{\$i}++;
\$n /= \$i;
}
}
return 0 if grep \$_ > 1, values %factors;
return 1 unless (scalar keys %factors) % 2;
return -1;
}
say "\$_: ", moebius \$_ for 1..20;
``````

This program displays the following output:

``````\$ perl ./moebius.pl
1: 1
2: -1
3: -1
4: 0
5: -1
6: 1
7: -1
8: 0
9: 0
10: 1
11: -1
12: 0
13: -1
14: 1
15: 1
16: 0
17: -1
18: 0
19: -1
20: 0
``````

## Wrapping up

The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on April 17, 2022. And, please, also spread the word about the Perl Weekly Challenge if you can.