Fractionally Prime with Raku and Perl
[164] Published 7. January 2022.This is my response to the Perl Weekly Challenge #146.
Challenge #146.1: 10001st Prime Number
10001st prime number.
#! /usr/bin/env raku
unit sub MAIN (Int :$number where $number > 0 = 10001); # [1]
my $primes := (1..Inf).grep( *.is-prime ); # [2]
say $primes[$number -1]; # [3]
[1] You can optionally specify another index than 1001.
See
docs.raku.org/routine/is-prime
for more information about is-prime.
[3] Print the requested prime (with an index one less than the number, as the index is zero based).
Running it:
$ ./10001st
104743
You can get any prime you want (by index):
$ ./10001st -number=1
2
$ ./10001st -number=2
3
$ ./10001st -number=3
5
$ ./10001st -number=43
191
A Perl Version
This is straight forward(ish) translation of the Raku version, but with a loop instead of the sequence: File: 10001st-perl
#! /usr/bin/env perl
use strict;
use warnings;
use feature 'say';
use Math::Prime::Util 'is_prime'; # [1]
my $number = int($ARGV[0] || 10001);
my $count = 0;
my $candidate = 0;
while (++$candidate)
{
next unless is_prime($candidate);
$count++;
last if $count == $number;
}
say $candidate;
[1] Perl does not have a built in function for prime recognition, but the «Math::Prime::Util» module supplies one for us.
Running it gives the same result as the Raku version:
$ ./10001st-perl
104743
$ ./10001st-perl 43
191
Challenge #146.2: Curious Fraction Tree
Curious Fraction Tree:
You are given a fraction, member of the tree created similar to the above sample.
Write a script to find out the parent and grandparent of the given member.
Example 1:
Input: $member = '3/5';
Output: parent = '3/2' and grandparent = '1/2'
Input: $member = '4/3';
Output: parent = '1/3' and grandparent = '1/2'
A Graph Digression
I used Graphviz to generate the graph above. The dependency file, which I wrote myself (manually) looks like this:File: cft.dot
digraph foogrph {
"1/3" -> "1/4";
"1/3" -> "4/3";
"3/2" -> "3/5";
"3/2" -> "5/2";
"1/2" -> "1/3";
"1/2" -> "3/2";
"2/3" -> "2/5";
"2/3" -> "5/3";
"3/1" -> "3/4";
"3/1" -> "5/1";
"2/1" -> "2/3";
"2/1" -> "3/1";
"1/1" -> "1/2";
"1/1" -> "2/1";
}
Then I used the «dot» command to get the svg file:
dot -Tsvg cft.dot > cft.svg
See e.g. my Pokemon Chiao, Raku article for more information about Graphviz.
We can hard code the data structure, just as I did with the graph above (except that the relationship is «child -> parent», and not «parent -> child» as in the graph):
File: cft-hash
#! /usr/bin/env raku
subset NuDe of Str where * ~~ /^\d+\/\d+$/; # [1]
unit sub MAIN (NuDe $fraction); # [1]
my %parent = ( '1/4' => '1/3',
'4/3' => '1/3',
'3/5' => '3/2',
'5/2' => '3/2',
'1/3' => '1/2',
'3/2' => '1/2',
'2/5' => '2/3',
'5/3' => '2/3',
'3/4' => '3/1',
'4/1' => '3/1',
'2/3' => '2/1',
'3/1' => '2/1',
'1/2' => '1/1',
'2/1' => '1/1'
);
my $parent = %parent{$fraction} // die "No such member: $fraction"; # [2]
my $grandparent = %parent{$parent} // die "No such member: $parent"; # [2]
say "parent = \'$parent\' and grandparent = \'$grandparent\'"; # [3]
[1] A custom type for the fraction (as a string). Nu = Numerator, De = Denominator.
[2] Get the parent and grandparent, if they are in the hash.
[3] Print the result.
Running it:
$ ./cft-hash '3/5'
parent = '3/2' and grandparent = '1/2'
$ ./cft-hash '4/3'
parent = '1/3' and grandparent = '1/2'
Not very exciting, but it works.
Note that the program will fail if we give it a fraction that we have not put in, as e.g.
1/5:
$ ./cft-hash '1/5'
No such member: 1/5
in sub MAIN at ./cft-hash line 21
Let us find the pattern, i.e. how to get from a fraction to the parent, and use that to compute the parent and grandparent values on the spot.
File: cft
#! /usr/bin/env raku
subset NuDe of Str where * ~~ /^\d+\/\d+$/;
unit sub MAIN (NuDe $fraction);
my $parent = parent($fraction);
my $grandparent = parent($parent);
say "parent = \'$parent\' and grandparent = \'$grandparent\'";
sub parent (NuDe $fraction) # [1]
{
my (Int $numerator, Int $denominator) = $fraction.split("/")>>.Int; # [2]
return "0/0" if $numerator == $denominator == 1; # [3]
$numerator < $denominator # [4]
?? return $numerator ~ "/" ~ $denominator - $numerator # [4a]
!! return $numerator - $denominator ~ "/" ~ $denominator; # [4b]
}
[1] This procedure gives us the value of the parent.
[2] Split the fraction (a string) into the integers. The >>.Int
coercer is there as we want integers values and not strings, as is the default when
we split strings. We want this coersion as the variables require integer values,
by design.
[3] If we are at the top of the tree, return "0/0". Another possibility is to die, i.e. giving up.
[4] The formulae for the parent differ for left and right child nodes. We decide which one we have by comparing the numerator and denominator. The formulae [4a and 4b] are reversed engineered from the tree.
Running it:
$ ./cft '3/5'
parent = '3/2' and grandparent = '1/2'
$ ./cft '4/3'
parent = '1/3' and grandparent = '1/2'
$ ./cft '11/8'
parent = '3/8' and grandparent = '3/5'
We got the right result.
A Second Graph Digression
The manually generated graph («dot» file, really) is ok, but what if we want a graph with 4 levels?Here is a program that generates the «dot» file, with as many levels as you want:
File: mkcft
#! /usr/bin/env raku
subset NuDe of Str where * ~~ /^\d+\/\d+$/;
unit sub MAIN (Int $levels where $levels > 0 = 3);
say 'digraph foogrph {';
recurse('1/1');
say '}';
sub recurse (NuDe $current, $level = 1)
{
my $left = left-child($current);
my $right = right-child($current);
say " \"{ $current }\" -> \"{ left-child($current) }\"";
say " \"{ $current }\" -> \"{ right-child($current) }\"";
return if $level == $levels;
recurse($left, $level +1);
recurse($right, $level +1);
}
sub left-child (NuDe $fraction)
{
my (Int $numerator, Int $denominator) = $fraction.split("/")>>.Int;
return "$numerator/{ $numerator + $denominator }";
}
sub right-child (NuDe $fraction)
{
my (Int $numerator, Int $denominator) = $fraction.split("/")>>.Int;
return "{ $numerator + $denominator }/$denominator";
}
The original 3 level graph looks the same. Here is the 4 level one:
$ ./mkcft 4 > 4.dot
$ dot -Tsvg 4.dot > 4.svg
The 5 level one:
$ ./mkcft 5 > 5.dot
$ dot -Tsvg 5.dot > 5.svg
The order (left to right) is as expected, as we specified (printed) them in the correct order (left before right), for each row (or level). Screw up the order, and things will behave differently. (Crossing dependencies will cause Graphwiz to rearrange the graph so that as few dependency lines as possible intersect, but that is not an issue here.)
Perl
This is a straight forward translation of the Raku version. File: cft-perl
#! /usr/bin/env perl
use strict;
use warnings;
use feature 'say';
use feature 'signatures';
no warnings qw(experimental::signatures);
my $fraction = $ARGV[0] // "";
die "Not a fraction: $fraction" unless $fraction =~ /^\d+\/\d+$/;
my $parent = parent($fraction);
my $grandparent = parent($parent);
say "parent = \'$parent\' and grandparent = \'$grandparent\'";
sub parent ($fraction)
{
my ($numerator, $denominator) = split("/", $fraction);
return "0/0" if $numerator == 1 && $denominator == 1;
$numerator < $denominator
? return $numerator . "/" . ( $denominator - $numerator )
: return ($numerator - $denominator ) . "/" . $denominator;
}
Running it gives the same result as the Raku version:
$ ./cft-perl '3/5'
parent = '3/2' and grandparent = '1/2'
$ ./cft-perl '4/3'
parent = '1/3' and grandparent = '1/2'
$ ./cft-perl '11/8'
parent = '3/8' and grandparent = '3/5'
And that's it.