Fareys Wear Boots

Wherein as we look beneath the surface and reveal a mystery…

THE WEEKLY CHALLENGE – PERL & RAKU #159 — Task 1

---

“I am your fairy tale. Your dream. Your wishes and desires, and I am your thirst and your hunger and your food and your drink.“

— Klaus Kinski

---

Farey Sequence

Submitted by: Mohammad S Anwar

You are given a positive number, $n.

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.

ANALYSIS

METHOD

The Fahey sequence of a given order n is an ascending, ordered list of all subunary fractions, with denominators up to the value of the order, inclusive of unity and reduced to their lowest terms. That’s admittedly a mouthful, but what it means is that, for say the order 3 we get the fractions 0/3, 1/3, 2/3 and 3/3, and in addition the fractions 0/2, 1/2, 2/2 from order 2 and 0/1 and 1/1 from order 1. Of course many of these fractions are equivalent and in those cases we pick the smallest terms to make the final list (0/1, 1/3, 1/2, 2/3, 1/1).

Years ago I came to the conclusion to never play with people’s names: no matter how clever you think you are the person you’re talking about has undoubtably heard whatever novel witticism you could possibly come up with. And its a cheap shot that generally make you look foolish and hence pretty much never worth the effort. That said Farey’s long dead and I can’t help looking at these lists of etherial fractions sprouting up and not think about Fairy Rings of mushrooms suddenly appearing after the night, connected subterraneously by tendrils of mycelium invisible and mysterious to those surveying from the surface.

Like the rings, the rules of construction for the Farey sequences do not themselves overtly reveal the hidden subterranean structure.

One interesting property of these sequences is that for any triplet of successive terms selected, the central term will be the mediant of the two outer. Which is to say we can obtain the ratio of the intermediate value by summing the two numerators and two denominators of the outside terms: for the two terms in example 2 above, 2/7 and 2/5, the intermediate numerator will be 2+2 and denominator 7+5, yielding 4/12, which can then be reduced to 1/3. This can be seen to be the case by examination of the example.

Two algorithms suggest themselves to produce the Fahey sequence for a given order: we can either construct all the fractions exhaustively, reduce them to their lowest terms, remove duplicates and sort them; or alternately we can expand our list systematically, bisecting sets of adjacent fractions from the previous order to construct the mediant, reducing them as possible along the way, until we complete the next level. Repeat as necessary.

The first technique is fairly straightforward to implement, and works well, and more so we can use the results to further explore the sequences. To avoid unnecessary suspense: it’s pretty wild.

Even though the addition of each new order n provides n+1 new fractions to the pool, one for every possible numerator, through reduction and cancellation only a smaller subset of these new fractions end up being added to the sequence. After the first (filthy) degenerate cases for 0 and 1, these additions always come in pairs and proceed in their own arcane fashion, as new prime numerators come into play.

And 1 over the new denominator; can’t forget that. And for each new prime we get a complementary negative numerator, subtracted from and mirrored downward from the denominator maximum. This is why we always get pairs. So for order 7 we get 3/7 and 5/7, the primes less than 7, but also 2/7 and 4/7, and although 1 is not prime per se, 1/7 and 6/7 — for a total of 6. Then again if the prime numerator is a factor of the denominator the fraction can be reduced and is going to already be present. The whole thing is, to use a technical term, a mess.

Actually I believe the real technical term that applies here is “hairy” — referring to all of the numerous edge cases that need to be confusingly handled.

The outside fractions are easy to place in the sequence, just above 0/1 and below 1/1, but internally the pattern is considerably less obvious. There does not seem to be a simple algorithm that doesn’t involve recomputing a lot of fractions into one or several common denominators. The most mathematically sounds answer seems to be that the factorial of the order would work in all cases, having all of the component orders as factors. This might be construed as the best method, that is, until the factorial becomes huge, which it will.quickly. Less precisely but more manageably we could compute decimal intermediates and insert the new elements using those values. Any floating-point errors wouldn’t meaningfully manifest themselves until we got to the highest orders. This is how we went about ordering the sequences in the exhaustive approach; even though the values will sometimes be less precise the subsequent ordering will be just fine for quite some time.

Thus we’ve come up with parts for two alternate approaches to go about constructing the sequences. Through one we can discover the new fractions to be added and fit them into the previously computed list — neither step being particularly easy. In the other, we look for the places the new fractions should fall in and compute them from their neighbors. Which, just to be clear, I see no obvious way of accomplishing.

In pursuit of this pattern I graphed out the lists up to order 12, using hexadecimal notation to keep the numerators and denominators to single digits, to explore the gaps. This results in a remarkable picture, rounded at the top before settling into a steady 1:1 slope on the outside as we always add a pair of fractions there. It’s quite pretty, fascinating really, albeit less-than-forthright in any deeper explanation:

PERL 5 SOLUTION

For Perl I decided to implement a Rational data-type class in Moo, that when initialized with any numerator and denominator automatically creates an internal reduced form, along with a floating-point value and a stringifying method to create hash keys.

All fractions are created exhaustively and added to a hash, keyed on the reduced form with the floating-point value as the key. We can then sort the final list of hash keys on the value to properly order the results.

use warnings;
use strict;
use utf8;
use feature ":5.26";
use feature qw(signatures);
no warnings 'experimental::signatures';


package Rat;
{
    use Moo;
    use feature qw(signatures);
    no warnings 'experimental::signatures';

    has n => ( is => 'ro');
    has d => ( is => 'ro');

    has num => ( is => 'rw');
    has den => ( is => 'rw');
    has val => ( is => 'rw');
    
    around BUILDARGS => sub {
        my ( $orig, $class, @args ) = @_;
        return {    n => $args[0],
                    d => $args[1]  };        
    };
 
    sub BUILD ($self, $args) { 
        my $gcd = gcd( $self->n, $self->d );           
        $self->num( $self->n / $gcd );
        $self->den( $self->d / $gcd ); 
        $self->val( $self->n / $self->d );
    };
    
    sub gcd ($m, $n) {
        return $n if $m == 0;   ## gcd of (0,n) is n
        while ( $n != 0 ) {
            $n > $m and ($m, $n) = ($n, $m);
            my $r = $m - $n * ( int ($m/$n));
            return $n if $r == 0;
            ($m, $n) = ($n, $r);
        }
    }

    sub string ($self) {
        return $self->num . "/" . $self->den;
    };

}

package main;

my $order = shift @ARGV // 7;
my @rats;

for my $den (1..$order) {
    for my $num ( 0..$den) {
        push @rats, new Rat($num, $den);    
    }
}
my %farey = map { $_->string => $_->val } @rats;

say join ' ', sort { $farey{$a} <=> $farey{$b} } keys %farey;

Raku Solution

Raku of course has its own Rat rational number type, no we don’t need to make one. We do have to wrangle it, however, and that can get a little weird to get right.

The first lnes define an operator to construct list like (0,3), (1,3), (2,3), (3,3), using the cross-product metaoperator. Then we map a list of denominators starting at 1 to the order requested with this operator to make all of our fraction pairs. This is a pretty heavily nested structure when we’re done, so I flatten everything and start over, grabbing the flat list two elements at a time.

Then we take these short lists and use them to form Rat numbers, which are then sorted and filtered for unique values, and mapped back to their numerator and denominator pairs. We could have used .perl here, to write them out as fractions, but Raku for some reason insists on writing one-half as 0.5, so I had to explicitly construct proper fraction strings.

unit sub MAIN ( $order = 20 ) ;

sub tri-cross { [X] (0..$^a.Num) , $^a.Num } ;

my @f = ((1..$order).map: &tri-cross)
                    .flat
                    .rotor(2)  ;
my @rats;
my @frac;

@rats.push: ($_[0]/$_[1]).Rat for @f;
@frac.push: |(@rats.sort.unique).map: *.nude ;        

@frac .= map({ $_[0] ~ '/' ~ $_[1] });
@frac.say;