Farey’s in a twist
Weekly challenge 159 — 4 April 2022
Week 159: 4 Apr 2022
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.
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.
#!/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); }
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
Any content of this website which has been created by Peter Campbell Smith is in the public domain