RabbitFarm

2022-04-10

Farey and Farey Again, but in a Mobius Way

The examples used here are from The Weekly Challenge problem statement and demonstrate the working solution.

Part 1

You are given a positive number, $n. Write a script to compute the Farey Sequence of the order $n.

Solution


use strict;
use warnings;

use POSIX;

sub farey{
    my($order) = @_;
    my @farey;
    my($s, $t, $u, $v, $x, $y) = (0, 1, 1, $order, 0, 0);
    push @farey, "$s/$t", "$u/$v";
    while($y != 1 && $order > 1){
        $x = POSIX::floor(($t + $order) / $v) * $u - $s;
        $y = POSIX::floor(($t + $order) / $v) * $v - $t;
        push @farey, "$x/$y";
        ($s, $t, $u, $v) = ($u, $v, $x, $y);
    }
    return @farey;
}

MAIN:{
    print join(", ", farey(7)) . "\n";
}

Sample Run


$ perl perl/ch-1.pl
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

Notes

Here is an iterative implementation of what seems to be a fairly standard recursive definition of the Farey Sequence. Well, "standard" may be over stating it as this sequence is seemingly fairly obscure. Fare-ly obscure? Ha! Anyway, this all seems fairly straightforward and the main thing to note here is that the sequence elements are stored as strings. This seems the most convenient way to keep them for display although in the next part of the challenge we'll use the sequence elements in a numerical way.

Part 2

You are given a positive number $n. Write a script to generate the Moebius Number for the given number.

Solution


use strict;
use warnings;

use POSIX;
use Math::Complex;

sub farey{
    my($order) = @_;
    my @farey;
    my($s, $t, $u, $v, $x, $y) = (0, 1, 1, $order, 0, 0);
    push @farey, "$s/$t", "$u/$v";
    while($y != 1 && $order > 1){
        $x = POSIX::floor(($t + $order) / $v) * $u - $s;
        $y = POSIX::floor(($t + $order) / $v) * $v - $t;
        push @farey, "$x/$y";
        ($s, $t, $u, $v) = ($u, $v, $x, $y);
    }
    return @farey;
}

sub mertens{
    my($n) = @_;
    my @farey = farey($n);
    my $mertens = 0;
    map {$mertens += exp(2 * M_PI * i * eval($_))} @farey;
    $mertens += -1;
    return Re($mertens);
}

sub moebius{
    my($n) = @_;
    return 1 if $n == 1;
    return sprintf("%.f", (mertens($n) - mertens($n - 1)));
}

MAIN:{
    map {print moebius($_) . "\n"} (5, 10, 20);
}

Sample Run


$ perl perl/ch-2.pl
-1
1
0

Notes

We can consider this second task of the challenge to be a continuation of the first. Here the Farey Sequence code is used again. But why? Well, in order to compute the Moebius Number we use an interesting property. The Mertens Function of $n is defined as the sum of the first $n Moebius Numbers. There is an alternative and equivalent definition of the Mertens Function, however, that use the Farey Sequence. In the alternative definition The Mertens Function is equivalent to what is shown in sub mertens: the sum of the natural logarithm base raised to the power of two times pi times i times the k-th element of the Farey Sequence. In Perl: map {$mertens += exp(2 * M_PI * i * eval($_))} @farey;

Thus to compute the n-th Moebius Number we compute the n-th and n-th - 1 Mertens Function and subtract as shown.

Be aware that this computation requires the use of Math::Complex, a core module which defines constants and operations on complex numbers. It's how we are able to use i in sub mertens.

References

Challenge 159

Farey Sequence

Mertens Function

Moebius Function

Math::Complex

posted at: 11:45 by: Adam Russell | path: /perl | permanent link to this entry