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
posted at: 11:45 by: Adam Russell | path: /perl | permanent link to this entry