Task — Farey sequence

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

Examples

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

The Farey sequence of order $n comprises a value-ordered list of all the fractions with integer denominators in the range 1 .. $n and integer numerators in the range 0 .. $denominator, and with the numerator and denominator having a greatest common divisor (gcd) of 1.

So that's what my solution does, with nested loops for numerator and denominator, discarding those with a gcd > 1 and storing them in a hash with the key equal numerator/$denominator + 1 and the value equal to the string "$numerator/$denominator".

As the keys will all be 0.xxx or 1.000 they sort in the right order despite being regarded as strings.

Try it 

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2022-04-04
use utf8;     # Week 159 - task 1 - Farey Sequence
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';

farey_sequence(5);
farey_sequence(15);
farey_sequence(1);

sub farey_sequence {
    
    my ($n, $num, $den, $numx, $denx, $gcd, %farey, $j, $result);
    
    # generate terms of sequence
    $n = shift;
    for $den (1 .. $n) {
        for $num (0 .. $den) {
            
            # discard if the have a common factor
            next if gcd($num, $den) != 1;
            $farey{$num / $den} = qq[$num/$den];
        }
    }
    
    # sort by value, list by $num/$den
    for $j (sort keys %farey) {
        $result .= qq[$farey{$j}, ];
    }
    
    say qq[\nInput:  \$n = $n];
    say qq[Output: ] . substr($result, 0, -2);
}

sub gcd {
    
    # calculates greatest common divisor of $a and $b
    my ($a, $b) = @_;
    return 0 == $b ? $a : gcd($b, $a % $b);
}

Output

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

Input:  $n = 15
Output: 0/1, 1/15, 1/14, 1/13, 1/12, 1/11, 1/10, 1/9, 1/8, 2/15, 1/7, 2/13, 1/6, 2/11, 1/5, 3/14, 2/9, 3/13, 1/4, 4/15, 3/11, 2/7, 3/10, 4/13, 1/3, 5/14, 4/11, 3/8, 5/13, 2/5, 5/12, 3/7, 4/9, 5/11, 6/13, 7/15, 1/2, 8/15, 7/13, 6/11, 5/9, 4/7, 7/12, 3/5, 8/13, 5/8, 7/11, 9/14, 2/3, 9/13, 7/10, 5/7, 8/11, 11/15, 3/4, 10/13, 7/9, 11/14, 4/5, 9/11, 5/6, 11/13, 6/7, 13/15, 7/8, 8/9, 9/10, 10/11, 11/12, 12/13, 13/14, 14/15, 1/1

Input:  $n = 1
Output: 0/1, 1/1