aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--challenge-146/athanasius/perl/ch-1.pl127
-rw-r--r--challenge-146/athanasius/perl/ch-2.pl232
-rw-r--r--challenge-146/athanasius/raku/ch-1.raku128
-rw-r--r--challenge-146/athanasius/raku/ch-2.raku208
4 files changed, 695 insertions, 0 deletions
diff --git a/challenge-146/athanasius/perl/ch-1.pl b/challenge-146/athanasius/perl/ch-1.pl
new file mode 100644
index 0000000000..5961ea5b77
--- /dev/null
+++ b/challenge-146/athanasius/perl/ch-1.pl
@@ -0,0 +1,127 @@
+#!perl
+
+###############################################################################
+=comment
+
+Perl Weekly Challenge 146
+=========================
+
+TASK #1
+-------
+*10001st Prime Number*
+
+Submitted by: Mohammad S Anwar
+
+Write a script to generate the 10001st prime number.
+
+=cut
+###############################################################################
+
+#--------------------------------------#
+# Copyright © 2022 PerlMonk Athanasius #
+#--------------------------------------#
+
+#==============================================================================
+=comment
+
+Algorithm
+---------
+Primes are identified using a standard Sieve of Eratosthenes [1]. The only
+difficulty is determining the minimal size of the sieve needed to guarantee a
+sufficient number of primes. For this purpose, the prime-counting function
+pi(n) is used to estimate the number of primes less than or equal to n. From
+[2], the lower bound for pi(n) is given by:
+
+ n/ln(n) < pi(n)
+
+A value of n = 116,700 gives n/ln(n) = 10,002.261, which is just slightly
+greater than the target of 10,001.
+
+Solution
+--------
+This script identifies the 10,001st prime number as 104,743. This is confirmed
+by [3], which contains the following entries:
+
+ ...
+ 10000 104729
+ 10001 104743
+ 10002 104759
+ ...
+
+References
+----------
+[1] Wikipedia, "Sieve of Eratosthenes".
+ https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
+[2] Weisstein, Eric W. "Prime Counting Function." From MathWorld--A Wolfram Web
+ Resource. https://mathworld.wolfram.com/PrimeCountingFunction.html
+[3] N. J. A. Sloane, "Table of n, prime(n) for n = 1..100000".
+ https://oeis.org/A000040/a000040.txt
+
+=cut
+#==============================================================================
+
+use strict;
+use warnings;
+use Const::Fast;
+
+const my $TARGET => 10_001;
+const my $SIEVE_SZ => 116_700; # See discussion above
+const my $USAGE => "Usage:\n perl $0\n";
+
+#------------------------------------------------------------------------------
+BEGIN
+#------------------------------------------------------------------------------
+{
+ $| = 1;
+ print "\nChallenge 146, Task #1: 10001st Prime Number (Perl)\n\n";
+}
+
+#==============================================================================
+MAIN:
+#==============================================================================
+{
+ my $args = scalar @ARGV;
+ $args == 0
+ or die "ERROR: Expected 0 command line arguments, found $args\n$USAGE";
+
+ my $count = 0;
+ my @sieve = (0) x $SIEVE_SZ;
+ my $latest_prime;
+
+ for my $i (2 .. $#sieve)
+ {
+ if ($sieve[ $i ] == 0)
+ {
+ $latest_prime = $i;
+
+ last if ++$count >= $TARGET;
+
+ for (my $j = $i * $i; $j <= $#sieve; $j += $i)
+ {
+ $sieve[ $j ] = 1;
+ }
+ }
+ }
+
+ $count == $TARGET
+ or die "ERROR: Found $count primes, target is $TARGET\n";
+
+ printf "The %sst prime number is %s\n",
+ commify( $count ), commify( $latest_prime );
+}
+
+#------------------------------------------------------------------------------
+# Adapted from: https://perldoc.perl.org/perlfaq5#
+# How-can-I-output-my-numbers-with-commas-added%3F
+#
+sub commify
+#------------------------------------------------------------------------------
+{
+ my ($n) = @_;
+
+ 1 while $n =~ s/ ^ ([-+]? \d+) (\d{3}) /$1,$2/x;
+
+ return $n;
+}
+
+###############################################################################
diff --git a/challenge-146/athanasius/perl/ch-2.pl b/challenge-146/athanasius/perl/ch-2.pl
new file mode 100644
index 0000000000..45cc1aa63c
--- /dev/null
+++ b/challenge-146/athanasius/perl/ch-2.pl
@@ -0,0 +1,232 @@
+#!perl
+
+###############################################################################
+=comment
+
+Perl Weekly Challenge 146
+=========================
+
+TASK #2
+-------
+*Curious Fraction Tree*
+
+Submitted by: Mohammad S Anwar
+
+Consider the following Curious Fraction Tree:
+
+ 1/1
+ ---------------------------------------
+ | |
+ | |
+ 1/2 2/1
+ ------------------- -------------------
+ | | | |
+ | | | |
+ 1/3 3/2 2/3 3/1
+ --------- --------- --------- ---------
+ | | | | | | | |
+ | | | | | | | |
+ 1/4 4/3 3/5 5/2 2/5 5/3 3/4 4/1
+
+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'
+
+=cut
+###############################################################################
+
+#--------------------------------------#
+# Copyright © 2022 PerlMonk Athanasius #
+#--------------------------------------#
+
+#==============================================================================
+=comment
+
+Assumption
+----------
+The input numerator and denominator must be positive (non-zero) integers and
+relative primes (i.e., coprimes).
+
+Output
+------
+Standard output displays the parent and grandparent (if any) of the given
+fraction, as per the Examples.
+
+In my view, however, a more interesting output is a display of all the nodes
+which form a path from the root to the given fraction. To see this additional
+output, set the constant $SHOW_PATH to a true value.
+
+Algorithm
+---------
+As explained in [1], the children of each node a/b in the Curious Fraction Tree
+are a/(a+b) (left) and (a+b)/b (right). Left children are always less than one,
+and right children are always greater than one. Therefore, the parent of any
+given fraction n/d may be found as follows:
+
+ IF n = d = 1 THEN n/d is the root node, and has no parent
+ ELSE
+ IF n < d THEN n/d is a left child, and its parent is n/(d - n)
+ ELSE n/d is a right child, and its parent is (n - d)/d
+ ENDIF
+ ENDIF
+
+Of course, the grandparent of any fraction is simply the parent of its parent.
+
+Reference
+---------
+[1] James Tanton, "Fractions are Hard! 5.3 A Curious Fraction Tree".
+ https://gdaymath.com/lessons/fractions/5-3-a-curious-fraction-tree/
+
+=cut
+#==============================================================================
+
+use strict;
+use warnings;
+use Const::Fast;
+use Math::Prime::Util qw( gcd );
+use Regexp::Common qw( number );
+
+const my $SHOW_PATH => 1;
+const my $USAGE =>
+"Usage:
+ perl $0 <num> <den>
+
+ <num> Numerator: positive integer
+ <den> Denominator: positive integer, coprime to the numerator\n";
+
+#------------------------------------------------------------------------------
+BEGIN
+#------------------------------------------------------------------------------
+{
+ $| = 1;
+ print "\nChallenge 146, Task #2: Curious Fraction Tree (Perl)\n\n";
+}
+
+#==============================================================================
+MAIN:
+#==============================================================================
+{
+ my ($num, $den) = parse_command_line();
+
+ print "Input: member = '$num/$den'\n";
+
+ my ($pa, $pb);
+
+ print 'Output: ';
+
+ if (get_parent( $num, $den, \$pa, \$pb ))
+ {
+ my ($ga, $gb);
+
+ if (get_parent( $pa, $pb, \$ga, \$gb))
+ {
+ print "parent = '$pa/$pb' and grandparent = '$ga/$gb'\n";
+ }
+ else
+ {
+ print "parent = '1/1' (root) and there is no grandparent\n";
+ }
+ }
+ else
+ {
+ print "root has no parent (or grandparent)\n";
+ }
+
+ if ($SHOW_PATH)
+ {
+ my $path = get_all_ancestors( $num, $den );
+
+ printf "\nPath from root:\n%s\n", join ' --> ', @$path;
+ }
+}
+
+#------------------------------------------------------------------------------
+sub get_parent
+#------------------------------------------------------------------------------
+{
+ my ($n, $d, $pa, $pb) = @_;
+ my $has_parent = 1;
+
+ if ($n == $d)
+ {
+ $has_parent = 0;
+ }
+ elsif ($n < $d)
+ {
+ $$pa = $n;
+ $$pb = $d - $n;
+ }
+ else # $n > $d
+ {
+ $$pa = $n - $d;
+ $$pb = $d;
+ }
+
+ return $has_parent;
+}
+
+#------------------------------------------------------------------------------
+sub get_all_ancestors
+#------------------------------------------------------------------------------
+{
+ my ($n, $d ) = @_;
+ my @path = "$n/$d";
+ my ($pa, $pb);
+
+ while (get_parent( $n, $d, \$pa, \$pb ))
+ {
+ push @path, "$pa/$pb";
+
+ $n = $pa;
+ $d = $pb;
+ }
+
+ @path = reverse @path;
+
+ return \@path;
+}
+
+#------------------------------------------------------------------------------
+sub parse_command_line
+#------------------------------------------------------------------------------
+{
+ my $args = scalar @ARGV;
+ $args == 2 or error( "Expected 2 command line arguments, found $args" );
+
+ for (@ARGV)
+ {
+ / ^ $RE{num}{int} $ /x
+ or error( qq["$_" is not a valid integer] );
+
+ $_ > 0 or error( "$_ is not positive" );
+ }
+
+ my ($num, $den) = @ARGV;
+
+ gcd( $num, $den ) == 1
+ or error( "The numerator and denominator are not coprimes" );
+
+ return ($num, $den);
+}
+
+#------------------------------------------------------------------------------
+sub error
+#------------------------------------------------------------------------------
+{
+ my ($message) = @_;
+
+ die "ERROR: $message\n$USAGE";
+}
+
+###############################################################################
diff --git a/challenge-146/athanasius/raku/ch-1.raku b/challenge-146/athanasius/raku/ch-1.raku
new file mode 100644
index 0000000000..e890aea09b
--- /dev/null
+++ b/challenge-146/athanasius/raku/ch-1.raku
@@ -0,0 +1,128 @@
+use v6d;
+
+###############################################################################
+=begin comment
+
+Perl Weekly Challenge 146
+=========================
+
+TASK #1
+-------
+*10001st Prime Number*
+
+Submitted by: Mohammad S Anwar
+
+Write a script to generate the 10001st prime number.
+
+=end comment
+###############################################################################
+
+#--------------------------------------#
+# Copyright © 2022 PerlMonk Athanasius #
+#--------------------------------------#
+
+#==============================================================================
+=begin comment
+
+Algorithm
+---------
+Primes are identified using a standard Sieve of Eratosthenes [1]. The only
+difficulty is determining the minimal size of the sieve needed to guarantee a
+sufficient number of primes. For this purpose, the prime-counting function
+pi(n) is used to estimate the number of primes less than or equal to n. From
+[2], the lower bound for pi(n) is given by:
+
+ n/ln(n) < pi(n)
+
+A value of n = 116,700 gives n/ln(n) = 10,002.261, which is just slightly
+greater than the target of 10,001.
+
+Solution
+--------
+This script identifies the 10,001st prime number as 104,743. This is confirmed
+by [3], which contains the following entries:
+
+ ...
+ 10000 104729
+ 10001 104743
+ 10002 104759
+ ...
+
+References
+----------
+[1] Wikipedia, "Sieve of Eratosthenes".
+ https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
+[2] Weisstein, Eric W. "Prime Counting Function." From MathWorld--A Wolfram Web
+ Resource. https://mathworld.wolfram.com/PrimeCountingFunction.html
+[3] N. J. A. Sloane, "Table of n, prime(n) for n = 1..100000".
+ https://oeis.org/A000040/a000040.txt
+
+=end comment
+#==============================================================================
+
+my UInt constant $TARGET = 10_001;
+my UInt constant $SIEVE-SZ = 116_700; # See discussion above
+
+#------------------------------------------------------------------------------
+BEGIN
+#------------------------------------------------------------------------------
+{
+ "\nChallenge 146, Task #1: 10001st Prime Number (Raku)\n".put;
+}
+
+#==============================================================================
+sub MAIN()
+#==============================================================================
+{
+ my $count = 0;
+ my @sieve = 0 xx $SIEVE-SZ;
+ my $latest-prime;
+
+ for 2 .. @sieve.end -> UInt $i
+ {
+ if @sieve[ $i ] == 0
+ {
+ $latest-prime = $i;
+
+ last if ++$count >= $TARGET;
+
+ loop (my UInt $j = $i * $i; $j <= @sieve.end; $j += $i)
+ {
+ @sieve[ $j ] = 1;
+ }
+ }
+ }
+
+ $count == $TARGET
+ or die "ERROR: Found $count primes, target is $TARGET\n";
+
+ "The %sst prime number is %s\n".printf:
+ commify( $count ), commify( $latest-prime );
+}
+
+#------------------------------------------------------------------------------
+# Adapted from: https://perldoc.perl.org/perlfaq5#
+# How-can-I-output-my-numbers-with-commas-added%3F
+#
+sub commify( Int:D $n --> Str:D )
+#------------------------------------------------------------------------------
+{
+ my Str $s = ~$n;
+
+ Nil while $s ~~ s/ ^ (<[-+]>? \d+) (\d ** 3) /$0,$1/;
+
+ return $s;
+}
+
+#------------------------------------------------------------------------------
+sub USAGE()
+#------------------------------------------------------------------------------
+{
+ my Str $usage = $*USAGE;
+
+ $usage ~~ s/ ($*PROGRAM-NAME) /raku $0/;
+
+ $usage.put;
+}
+
+##############################################################################
diff --git a/challenge-146/athanasius/raku/ch-2.raku b/challenge-146/athanasius/raku/ch-2.raku
new file mode 100644
index 0000000000..bbeb8ea4c8
--- /dev/null
+++ b/challenge-146/athanasius/raku/ch-2.raku
@@ -0,0 +1,208 @@
+use v6d;
+
+###############################################################################
+=begin comment
+
+Perl Weekly Challenge 146
+=========================
+
+TASK #2
+-------
+*Curious Fraction Tree*
+
+Submitted by: Mohammad S Anwar
+
+Consider the following Curious Fraction Tree:
+
+ 1/1
+ ---------------------------------------
+ | |
+ | |
+ 1/2 2/1
+ ------------------- -------------------
+ | | | |
+ | | | |
+ 1/3 3/2 2/3 3/1
+ --------- --------- --------- ---------
+ | | | | | | | |
+ | | | | | | | |
+ 1/4 4/3 3/5 5/2 2/5 5/3 3/4 4/1
+
+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'
+
+=end comment
+###############################################################################
+
+#--------------------------------------#
+# Copyright © 2022 PerlMonk Athanasius #
+#--------------------------------------#
+
+#==============================================================================
+=begin comment
+
+Assumption
+----------
+The input numerator and denominator must be positive (non-zero) integers and
+relative primes (i.e., coprimes).
+
+Output
+------
+Standard output displays the parent and grandparent (if any) of the given
+fraction, as per the Examples. In my view, however, a more interesting output
+is a display of all the nodes which form a path from the root to the given
+fraction. To see this additional output, set the constant $SHOW-PATH to True.
+
+Algorithm
+---------
+As explained in [1], the children of each node a/b in the Curious Fraction Tree
+are a/(a+b) (left) and (a+b)/b (right). Left children are always less than one,
+and right children are always greater than one. Therefore, the parent of any
+given fraction n/d may be found as follows:
+
+ IF n = d = 1 THEN n/d is the root node, and has no parent
+ ELSE
+ IF n < d THEN n/d is a left child, and its parent is n/(d - n)
+ ELSE n/d is a right child, and its parent is (n - d)/d
+ ENDIF
+ ENDIF
+
+Of course, the grandparent of any fraction is simply the parent of its parent.
+
+Reference
+---------
+[1] James Tanton, "Fractions are Hard! 5.3 A Curious Fraction Tree".
+ https://gdaymath.com/lessons/fractions/5-3-a-curious-fraction-tree/
+
+=end comment
+#==============================================================================
+
+subset Pos of Int where * > -1;
+
+my Bool constant $SHOW-PATH = True;
+
+#------------------------------------------------------------------------------
+BEGIN
+#------------------------------------------------------------------------------
+{
+ "\nChallenge 146, Task #2: Curious Fraction Tree (Raku)\n".put;
+}
+
+#==============================================================================
+sub MAIN
+(
+ Pos:D $num, #= Numerator: positive integer
+ Pos:D $den where { $num gcd $den == 1 } #= Denominator: positive integer,
+ #= coprime to the numerator
+)
+#==============================================================================
+{
+ "Input: member = '$num/$den'".put;
+
+ my Pos ($pa, $pb) = 1, 1;
+
+ 'Output: '.print;
+
+ if get-parent( $num, $den, $pa, $pb )
+ {
+ my Pos ($ga, $gb) = 1, 1;
+
+ if get-parent( $pa, $pb, $ga, $gb )
+ {
+ "parent = '$pa/$pb' and grandparent = '$ga/$gb'".put;
+ }
+ else
+ {
+ "parent = '1/1' (root) and there is no grandparent".put;
+ }
+ }
+ else
+ {
+ 'root has no parent (or grandparent)'.put;
+ }
+
+ if $SHOW-PATH
+ {
+ my @path = get-all-ancestors( $num, $den );
+
+ "\nPath from root:\n%s\n".printf: @path.join: ' --> ';
+ }
+}
+
+#------------------------------------------------------------------------------
+sub get-parent
+(
+ Pos:D $n,
+ Pos:D $d,
+ Pos:D $pa is rw,
+ Pos:D $pb is rw
+--> Bool:D
+)
+#------------------------------------------------------------------------------
+{
+ my Bool $has-parent = True;
+
+ if $n == $d
+ {
+ $has-parent = False;
+ }
+ elsif $n < $d
+ {
+ $pa = $n;
+ $pb = $d - $n;
+ }
+ else # $n > $d
+ {
+ $pa = $n - $d;
+ $pb = $d;
+ }
+
+ return $has-parent;
+}
+
+#------------------------------------------------------------------------------
+sub get-all-ancestors
+(
+ Pos:D $n is copy,
+ Pos:D $d is copy
+--> Seq:D[Str:D]
+)
+#------------------------------------------------------------------------------
+{
+ my Str @path = "$n/$d";
+ my Pos ($pa, $pb) = 1, 1;
+
+ while get-parent( $n, $d, $pa, $pb )
+ {
+ @path.push: "$pa/$pb";
+
+ $n = $pa;
+ $d = $pb;
+ }
+
+ return @path.reverse;
+}
+
+#------------------------------------------------------------------------------
+sub USAGE()
+#------------------------------------------------------------------------------
+{
+ my Str $usage = $*USAGE;
+
+ $usage ~~ s/ ($*PROGRAM-NAME) /raku $0/;
+ $usage.put;
+}
+
+##############################################################################
generated by cgit (git 2.34.1) at 2026-07-01 23:31:19 +0000