by Arne Sommer

# 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

Write a script to generate the `10001st` prime number.
File: 10001st ```#! /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.

[2] A sequence of primes.

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

Consider the following `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' ``` Example 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 ```

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.