# 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