Merge pull request #6383 from rjt-pl/master

rjt's 171 solutions and blogs

8 files changed, 206 insertions, 4 deletions

diff --git a/challenge-171/ryan-thompson/README.md b/challenge-171/ryan-thompson/README.md
index 226fd05aea..66151b9345 100644
--- a/challenge-171/ryan-thompson/README.md
+++ b/challenge-171/ryan-thompson/README.md
@@ -1,15 +1,19 @@
 # Ryan Thompson
 
-## Week 170 Solutions
+## Week 171 Solutions
 
-### Task 1 › Primordial Numbers
+### Task 1 › Odd Abundant Numbers
 
  * [Perl](perl/ch-1.pl)
+ * [Perl](perl/ch-1a.pl) — Alternative implementations (see blog)
+ * [Raku](raku/ch-1.raku)
 
-### Task 2 › Kronecker Product
+### Task 2 › First Class Functions
 
  * [Perl](perl/ch-2.pl)
+ * [Raku](raku/ch-2.raku)
 
 ## Blogs
 
- * [Primordial Numbers and Kronecker Products](https://ry.ca/2022/06/primordial-kronecker/)
+ * [Odd Abundant Numbers](https://ry.ca/2022/06/odd-abundant-numbers/)
+ * [First Class Functions](https://ry.ca/2022/06/first-class-functions/)
diff --git a/challenge-171/ryan-thompson/blog.txt b/challenge-171/ryan-thompson/blog.txt
new file mode 100644
index 0000000000..977910ca83
--- /dev/null
+++ b/challenge-171/ryan-thompson/blog.txt
@@ -0,0 +1 @@
+https://ry.ca/2022/06/odd-abundant-numbers/
diff --git a/challenge-171/ryan-thompson/blog1.txt b/challenge-171/ryan-thompson/blog1.txt
new file mode 100644
index 0000000000..9a2bf8ca32
--- /dev/null
+++ b/challenge-171/ryan-thompson/blog1.txt
@@ -0,0 +1 @@
+https://ry.ca/2022/06/first-class-functions/
diff --git a/challenge-171/ryan-thompson/perl/ch-1.pl b/challenge-171/ryan-thompson/perl/ch-1.pl
new file mode 100755
index 0000000000..ec5591b62d
--- /dev/null
+++ b/challenge-171/ryan-thompson/perl/ch-1.pl
@@ -0,0 +1,22 @@
+#!/usr/bin/env perl
+#
+# ch-1.pl - Abundant numbers
+#
+# 2022 Ryan Thompson <rjt@cpan.org>
+
+use 5.010;
+use warnings;
+use strict;
+no warnings 'uninitialized';
+
+my $lim = $ARGV[0] // 10000;
+
+# This returns 23 abundant numbers. Please do see
+# my blog post and ch-1a.pl for a lot more information.
+# https://ry.ca/2022/06/odd-abundant-numbers/
+
+my @div_sum; # Sum of divisors for each number
+for my $n (1..$lim) {
+    $div_sum[$n*$_] += $n for 1..$lim/$n+1;
+    say $n if $n % 2 and 2*$n <= $div_sum[$n];
+}
diff --git a/challenge-171/ryan-thompson/perl/ch-1a.pl b/challenge-171/ryan-thompson/perl/ch-1a.pl
new file mode 100755
index 0000000000..3454d6ea83
--- /dev/null
+++ b/challenge-171/ryan-thompson/perl/ch-1a.pl
@@ -0,0 +1,123 @@
+#!/usr/bin/env perl
+#
+# ch-1a.pl - Alternative abundant number methods
+#
+# This file contains some of the code from my blog post, some benchmarks,
+# and other useful tidbits not part of my main solution.
+#
+# Blog: https://ry.ca/2022/06/odd-abundant-numbers/
+#
+# 2022 Ryan Thompson <rjt@cpan.org>
+
+use 5.010;
+use warnings;
+use strict;
+no warnings 'uninitialized';
+
+use List::Util qw< sum >;
+use Math::Prime::Util qw< divisor_sum >;
+use Benchmark qw< cmpthese >;
+use Test::More;
+
+sub odd_abundant_iterator(&);
+sub n_odd_abundant(&$);
+
+is_deeply([ n_abundant_sqrt() ], [ n_abundant_naive() ]);
+is_deeply([ n_abundant_sqrt() ], [ n_abundant_mpu() ]);
+
+done_testing;
+
+my $N = $ARGV[0] // 20; # First $N numbers
+
+say scalar n_abundant_sieve(100000);
+
+# Best algorithm. Uses a sieve-like method to reduce runtime
+# down to n log n
+sub n_abundant_sieve {
+    my $lim = shift;
+    my @r;
+
+    my @div_sum; # Sum of divisors for each number
+    for my $n (1..$lim) {
+        $div_sum[$n*$_] += $n for 1..$lim/$n+1;
+        push @r, $n if $n % 2 and 2*$n <= $div_sum[$n];
+    }
+
+    @r;
+}
+
+# If you just want to know if a particular number is abundant, use this
+sub is_abundant {
+    my $n = shift;
+    my $sum = divisor_sum($n);
+
+    2*$n < $sum;
+}
+
+cmpthese(-5, {
+#   naive   => sub { n_abundant_naive($N) },
+#   sqrt    => sub { n_abundant_sqrt($N) },
+    mpu     => sub { n_abundant_mpu($N) },
+    sieve   => sub { n_abundant_sieve(10000) },
+});
+
+# Check divisors up to sqrt($n)
+sub n_abundant_sqrt {
+    n_odd_abundant {
+        my $n    = shift;
+        my $sqrt = sqrt($n);
+
+        my $sum  = sum map { $_,  $n / $_ } 
+                      grep { $n % $_ == 0 } 1..$sqrt;
+
+        $sum -= $sqrt if $sqrt == int $sqrt;
+        
+        2*$n < $sum;
+    } $_[0];
+}
+
+# Use Math::Prime::Util's divisor_sum for quick divisors
+sub n_abundant_mpu {
+    n_odd_abundant {
+        my $n = shift;
+        my $sum = divisor_sum($n);
+
+        2*$n < $sum;
+    } $_[0];
+}
+
+# Brute force every divisor up to n/2
+sub n_abundant_naive {
+    n_odd_abundant {
+        my $n = shift;
+        $n < sum grep { $n % $_ == 0 } 1..$n/2;
+    } $_[0];
+}
+
+# Returns the first $N odd abundant numbers using the method of choice
+sub n_odd_abundant(&$) {
+    my ($is_abundant, $N) = @_;
+
+    my @r;
+    for (my $n = 3; $N; $n += 2) {
+        if ($is_abundant->($n)) {
+            push @r, $n;
+            $N--
+        }
+    }
+
+    @r;
+}
+
+# Checks for abundant numbers using the method of choice up to the $N-th
+# abundant number.
+sub odd_abundant_iterator(&) {
+    my $is_abundant = shift;
+    my $n = 1;
+    
+    sub {
+        do { $n += 2 } until $is_abundant->($n);
+
+        $n;
+    }
+}
diff --git a/challenge-171/ryan-thompson/perl/ch-2.pl b/challenge-171/ryan-thompson/perl/ch-2.pl
new file mode 100755
index 0000000000..b02a4cc797
--- /dev/null
+++ b/challenge-171/ryan-thompson/perl/ch-2.pl
@@ -0,0 +1,24 @@
+#!/usr/bin/env perl
+#
+# ch-2.pl - First class functions
+#
+# 2022 Ryan Thompson <rjt@cpan.org>
+
+use 5.010;
+use warnings;
+use strict;
+no warnings 'uninitialized';
+
+use List::Util qw< sum0 >;
+
+my $squares = sub { map { $_ * $_ } @_ };
+my $h = comp( \&sum0, $squares );
+
+say "The sum of squares for 1..10 = " . $h->(1..10);
+
+# Demonstrate function composition
+sub comp {
+    my ($f, $g) = @_;
+
+    sub { $f->($g->(@_)) }
+}
diff --git a/challenge-171/ryan-thompson/raku/ch-1.raku b/challenge-171/ryan-thompson/raku/ch-1.raku
new file mode 100644
index 0000000000..e597b65cc3
--- /dev/null
+++ b/challenge-171/ryan-thompson/raku/ch-1.raku
@@ -0,0 +1,15 @@
+#!/usr/bin/env raku
+
+# ch-1.raku - Odd abundant numbers
+#
+# 2021 Ryan Thompson <rjt@cpan.org>
+
+sub MAIN(Int $lim = 10000) {
+    my @div_sum; # Sum of divisors for each number
+
+    for 1...$lim -> $n {
+        @div_sum[$n*$_] += $n for 1..$lim/$n+1;
+        $n.say if $n % 2 and 2*$n <= @div_sum[$n];
+    }
+
+}
diff --git a/challenge-171/ryan-thompson/raku/ch-2.raku b/challenge-171/ryan-thompson/raku/ch-2.raku
new file mode 100644
index 0000000000..21af34c160
--- /dev/null
+++ b/challenge-171/ryan-thompson/raku/ch-2.raku
@@ -0,0 +1,12 @@
+#!/usr/bin/env raku
+
+# ch-2.raku - Function composition
+#
+# 2022 Ryan Thompson <rjt@cpan.org>
+
+my &sum    = sub {    [+] @_ };
+my &square = sub { @_ »*« @_ };
+
+my &h = &sum ∘ &square;
+
+say &h(1..10);