and Raku

This is my response to the Perl Weekly Challenge #159.

You are given a positive number,

Write a script to compute

Example 1:

`$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.

I do not know *why* the challenge
does not provide a Wikipedia link for the `Farey Sequence`

, as it does so for
the `Moebius Number`

in the second part, but here it is:
Wikipedia page.

#! /usr/bin/env raku
unit sub MAIN (Int $n where $n > 0, :v(:$verbose)); # [1]
my @fs = (0/1, 1/1); # [2]
for 1 .. $n -1 -> $numerator # [3]
{
for $numerator +1 .. $n -> $denominator # [4]
{
@fs.push: $numerator/$denominator; # [5]
}
}
if $verbose
{
say ":Unsorted: { @fs.join(", ") }";
say ":Unsorted x/y: { @fs.map( *.nude.join("/") ).join(", ") }";
say ":Sorted x/y: { @fs.sort.map( *.nude.join("/") ).join(", ") }";
}
@fs.sort.unique.map( *.nude.join("/") ).join(", ").say; # [6]

[1] Ensure a positive integer. The challenge rewuires a number, but it is fairly obvious that we should allow integers only.

[2] Pre-populate the result array with the first and last values - as rational numbers.

[3] Iterate over all the possible numbers to left of the `/`

(in the result).

[4] Ditto for the right hand part of the `/`

.

[5] Add the result of thre division to the result array.

[6] This one does a lot of heavy lifting. The `sort`

gives
us the values in sorted order (numerically). `unique`

gets rid of duplicates,
as e.g. both `1/2`

and `2/4`

will give `1/2`

(as will be
shown by the verbose output later on). The `map`

uses the `nude`

method to get the **nu**merator and the **de**nominator of the rational number.

See
docs.raku.org/routine/nude
for more information about `nude`

.

Running it:

$ ./farey-sequence 5
0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1
$ ./farey-sequence 7
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
$ ./farey-sequence 4
0/1, 1/4, 1/3, 1/2, 2/3, 3/4, 1/1

Looking good.

With verbose mode, to see what is going on:

$ ./farey-sequence -v 5
:Unsorted: 0, 1, 0.5, 0.333333, 0.25, 0.2, 0.666667, \
0.5, 0.4, 0.75, 0.6, 0.8
:Unsorted x/y: 0/1, 1/1, 1/2, 1/3, 1/4, 1/5, 2/3, 1/2, 2/5, 3/4, 3/5, 4/5
:Sorted x/y: 0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1
0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1
$ ./farey-sequence -v 7
:Unsorted: 0, 1, 0.5, 0.333333, 0.25, 0.2, 0.166667, 0.142857, 0.666667, \
0.5, 0.4, 0.333333, 0.285714, 0.75, 0.6, 0.5, 0.428571, 0.8, 0.666667, \
0.571429, 0.833333, 0.714286, 0.857143
:Unsorted x/y: 0/1, 1/1, 1/2, 1/3, 1/4, 1/5, 1/6, 1/7, 2/3, 1/2, 2/5, 1/3, \
2/7, 3/4, 3/5, 1/2, 3/7, 4/5, 2/3, 4/7, 5/6, 5/7, 6/7
:Sorted x/y: 0/1, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 1/3, 2/5, 3/7, 1/2, 1/2, \
1/2, 4/7, 3/5, 2/3, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 1/1
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
$ ./farey-sequence -v 4
:Unsorted: 0, 1, 0.5, 0.333333, 0.25, 0.666667, 0.5, 0.75
:Unsorted x/y: 0/1, 1/1, 1/2, 1/3, 1/4, 2/3, 1/2, 3/4
:Sorted x/y: 0/1, 1/4, 1/3, 1/2, 1/2, 2/3, 3/4, 1/1
0/1, 1/4, 1/3, 1/2, 2/3, 3/4, 1/1

You are given a positive number

`$n`

.
Write a script to generate the `Moebius Number`

for the given number.
Please refer to wikipedia page
for more informations.

Input: $n = 5
Output: -1

Example 2:
Input: $n = 10
Output: 1

Example 2:
Input: $n = 20
Output: 0

We need the factors, and happily we can borrow a function doing just that from my Centenary Sequences with Raku - Part 5 Divisors and Factors article.

Careful re-reading of the Wikipedia page (whilst writing the program and testing it) uncovered that the number «1» should also be included in the list of factors (even if not explicitly stated), so I have amended the procedure so that we can ask for it to be included.

File: moebius-number#! /usr/bin/env raku
unit sub MAIN (Int $n where $n > 0, :v(:$verbose)); # [1]
my @prime-factors = factors($n, :include-one); # [2]
say ": Factor count: { @prime-factors.elems } (Factors: \
{ @prime-factors.join(", ")})" if $verbose;
if @prime-factors.repeated.elems # [3]
{
say 0; # [3a]
}
else # [4]
{
say @prime-factors.elems %% 2 ?? -1 !! 1; # [4a]
}
sub factors ($number is copy, :$include-one) # [5]
{
return (1) if $number == 1;
if $number.is-prime
{
return :$include-one ?? (1, $number) !! ($number);
}
my @factors = $include-one ?? 1 !! ();
for (2 .. $number div 2).grep( *.is-prime ) -> $candidate
{
while $number %% $candidate
{
@factors.push: $candidate;
$number /= $candidate;
}
}
return @factors;
}

[1] Non-integers cannot have prime factors (as the latter are integers), so it is obvious that we can only allow integers.

[2] Get the prime factors, including 1.

[3] If we have duplicates of any of the factors we print «0» [3a].
Duplicates are detected with `repeated`

that kills of the first instance of
any unique value. Then we simply check for any elements in the result.

See
docs.raku.org/routine/repeated
for more information about `repeated`

.

[4] If not, print «-1» if the number of factors is even, and «1» if it is odd [4a].

[5] This one gives us the factors, with 1 included if we ask for it.

`else`

block (with the embedded ternary if) can be written more verbose
(and possibly more readable) as:
elsif @prime-factors.elems %% 2
{
say -1;
}
else
{
say 1;
}

Running it:

$ ./moebius-number 5
-1
$ ./moebius-number 10
1
$ ./moebius-number 20
0

Looking good.

With verbose mode:

$ ./moebius-number -v 5
: Factor count: 2 (Factors: 1, 5)
-1
$ ./moebius-number -v 10
: Factor count: 3 (Factors: 1, 2, 5)
1
$ ./moebius-number -v 20
: Factor count: 4 (Factors: 1, 2, 2, 5)
0

And that's it.