laurent_r

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.

Task 1: Farey Sequence

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

Task 2: Möbius Number

You are given a positive number $n.

Write a script to generate the Moebius Number for the given number. Please refer to Wikipedia page for more informations.

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.