Perl Weekly Challenge 171: Abundant Numbers and First-Class Functions
These are some answers to the Week 171 of the Perl Weekly Challenge organized by Mohammad S. Anwar.
Spoiler Alert: This weekly challenge deadline is due in a few of days from now (on July 3, 2022 at 23:59). This blog post offers some solutions to this challenge, please don’t read on if you intend to complete the challenge on your own.
Task 1: Abundant Numbers
Write a script to generate first 20 Abundant Odd Numbers.
According to wikipedia,
A number n for which the sum of divisors σ(n) > 2n, or, equivalently, the sum of proper divisors (or aliquot sum) s(n) > n.
For example, 945 is the first Abundant Odd Number.
Sum of divisors:
1 + 3 + 5 + 7 + 9 + 15 + 21 + 27 + 35 + 45 + 63 + 105 + 135 + 189 + 315 = 975
Reading that the first odd abundant number is 975, I was a bit afraid that we would have to dig into very large numbers to find the first 20 ones, but this turned out not to be the case.
Abundant Numbers in Raku
The is-abundant subroutine lists all the proper divisors of the input parameter and checks whether their sum is larger than the input integer. Then, we just loop over each odd integer (using the 1, 3 ... Inf lazy sequence operator) and display it if it in abundant. And we stop when we reach 20 of them.
sub is-abundant (Int $n where * > 0) {
my @divisors = grep {$n %% $_}, 1..$n/2;
return @divisors.sum > $n ?? True !! False;
}
my $count = 0;
for 1, 3 ... Inf -> $n {
if is-abundant $n {
say $n;
last if ++$count >= 20;
}
}
This program displays the following output:
$ raku ./abundant.raku
945
1575
2205
2835
3465
4095
4725
5355
5775
5985
6435
6615
6825
7245
7425
7875
8085
8415
8505
8925
Abundant Numbers in Perl
This is essentially a port to Perl of the above Raku program. The only significant differences is that we implement our own sum subroutine and iterate manually over odd integers.
use strict;
use warnings;
use feature "say";
sub sum {
my $sum = 0;
$sum += $_ for @_;
return $sum;
}
sub is_abundant {
my $n = shift;
my @divisors = grep {$n % $_ == 0} 1..$n/2;
return sum(@divisors) > $n ? 1 : 0;
}
my $n = 1;
my $count = 0;
while ($count < 20) {
if (is_abundant $n) {
say $n;
$count++;
}
$n += 2;
}
This program displays the following output:
$ perl ./abundant.pl
945
1575
2205
2835
3465
4095
4725
5355
5775
5985
6435
6615
6825
7245
7425
7875
8085
8415
8505
8925
Abundant Numbers in 17 Other Programming Languages
Update on July 1, 2022: added this section with other programming languages
I thought it would be an interesting and perhaps even useful exercise to try an implementation in a number of other programming languages. All of the implementations in this section have essentially the same structure, with the same function names (when possible) and variable names, to make language comparisons easier. They also all display the same output (space-separated values on one single line):
945 1575 2205 2835 3465 4095 4725 5355 5775 5985 6435 6615 6825 7245 7425 7875 8085 8415 8505 8925
Therefore, I won’t provide the output for each language, as this would repeat the line above each time.
To help reference, languages are listed in alphabetic order.
In Awk
function is_abundant(n) {
sum = 0
for (i = 2; i <= n/2; i++) {
if (n % i == 0) {
sum += i
if (sum > n) {
return 1
}
}
}
return 0
}
BEGIN {
n = 1
count = 0
while (count < 20) {
if (is_abundant(n)) {
printf("%d ", n)
count++
}
n += 2
}
}
In Bc
define is_abundant (n) {
sum = 0
for (i = 2; i < n/2; i++) {
if (n % i == 0) {
sum += i;
if (sum > n) {
return 1
}
}
}
return 0
}
n = 1
count = 0
while (count < 20) {
if (is_abundant(n)) {
print n, " "
count += 1
}
n += 2
}
quit
In C
#include <stdio.h>
#include <stdlib.h>
int is_abundant(int n) {
int sum = 0;
for (int i = 2; i <= n/2; i++) {
if (n % i == 0) {
sum += i;
if (sum > n) {
return 1;
}
}
}
return 0;
}
int main() {
int n = 1;
int count = 0;
while (count < 20) {
if (is_abundant(n)) {
printf("%d ", n);
count ++;
}
n += 2;
}
}
In D
import std.stdio;
int is_abundant(int n) {
int sum = 0;
for (int i = 2; i <= n/2; i++) {
if (n % i == 0) {
sum += i;
if (sum > n) {
return 1;
}
}
}
return 0;
}
void main() {
int n = 1;
int count = 0;
while (count < 20) {
if (is_abundant(n)) {
printf("%d ", n);
count ++;
}
n += 2;
}
}
In Dart
import "dart:io";
void main() {
var count = 0;
var j = 1;
while (count < 20) {
if (is_abundant(j)) {
stdout.write("$j ");
count++;
}
j += 2;
}
}
bool is_abundant(n) {
var sum = 0;
for (int i = 1; i <= n/2; i++) {
if (n % i == 0) {
sum += i;
if (sum > n) {
return true;
}
}
}
return false;
}
In Go
package main
import "fmt"
func main() {
var count = 0
var j = 1
for count < 20 {
if is_abundant(j) {
fmt.Printf("%d ", j)
count++
}
j += 2
}
}
func is_abundant(n int) bool {
var sum = 0
for i := 1; i < n/2; i++ {
if n%i == 0 {
sum += i
if sum > n {
return true
}
}
}
return false
}
In Javascript
function is_abundant(n) {
let sum = 0;
for (let i = 1; i < (n/2 + 1); i++) {
if (n % i == 0) {
sum += i;
if (sum > n) {
return true;
}
}
}
return false;
}
let count = 0
let j = 1
while (count < 20) {
if (is_abundant(j)) {
process.stdout.write(j + " ")
count++
}
j += 2
}
In Julia
function is_abundant(n)
sum = 0
for i in 1:n/2
if n % i == 0
sum += i
if sum > n
return true
end
end
end
return false
end
j = 1
count = 0
while count < 20
if is_abundant(j)
print(j, " ")
global count += 1
end
global j += 2
end
In Kotlin
fun is_abundant(n: Int): Boolean {
var sum = 0
for (i in 2..(n/2 + 1).toInt()) {
if (n % i == 0) {
sum += i
if (sum > n) {
return true
}
}
}
return false
}
fun main() {
val max = 20
var count = 0
var j = 1
while (count < max) {
if (is_abundant(j)) {
print ("$j ")
count++;
}
j += 2
}
}
In Lua
local function is_abundant(n)
sum = 0
for i = 1, n/2 do
if n % i == 0 then
sum = sum + i
if sum > n then
return true
end
end
end
return false
end
max = 20
count = 0
j = 1
while count < max do
if is_abundant(j) then
io.write(j, " ")
count = count + 1
end
j = j + 2
end
In Nim
In Nim, control flow control is using indentation (like Python).
proc is_abundant(n: int): bool =
var sum = 0
for i in 2..int(n/2):
if n mod i == 0:
sum += i
if sum > n:
return true
return false;
var count = 0
var j = 1
while count < 20:
if is_abundant(j):
stdout.write j, " "
count += 1
j += 2
In Pascal
program abundant;
const
max = 20;
var
count, j: integer;
function is_abundant(n: integer): boolean;
var
sum, i: integer;
begin
sum := 0;
for i := 2 to round(n/2) do
begin
if ( n mod i = 0) then
sum := sum + i;
if (sum > n) then
exit(true);
end;
exit(false);
end;
begin
count := 0;
j := 1;
while ( count < max ) do
begin
if (is_abundant(j)) then
begin
write(j, ' ');
count := count + 1;
end;
j := j + 2;
end;
end.
In Python
def is_abundant(n):
sum = 0
for i in range(2,int(n/2 + 1)):
if n % i == 0:
sum += i
if sum > n:
return True
return False
n = 1
count = 0
while count < 20:
if is_abundant(n):
print(n, end=' ')
count += 1
n += 2
In Ring
count = 0
for j = 1 to 10001 step 2
if is_abundant(j)
see " " + j
count += 1
if count > 10 exit 1 ok
ok
j += 2
next
func is_abundant n
sum = 0
for i = 2 to n/2
if n % i = 0
sum += i
if sum > n
return 1
ok
ok
next
return 0;
In Ruby
def is_abundant(n)
sum = 0
for i in 1.upto(n/2)
if n % i == 0 then
sum += i
if sum > n then
return true
end
end
end
return false
end
j = 1
count = 0
while count < 20
if is_abundant(j) then
print("#{j} ")
count += 1
end
j += 2
end
In Rust
fn is_abundant(n: usize) -> bool {
let mut sum = 0;
for i in 2..n/2 {
if n % i == 0 {
sum += i;
if sum > n {
return true;
}
}
}
return false
}
fn main() {
let mut n = 1;
let mut count = 0;
while count < 20 {
if is_abundant(n) {
print!("{} ", n);
count += 1;
}
n += 2;
}
}
In Scala
object abundant extends App {
def is_abundant(n: Int): Boolean = {
var sum = 0
for (i <- 1 to n/2) {
if (n % i == 0) {
sum += i
if (sum > n) {
return true
}
}
}
return false;
}
var count = 0
var j = 1
while (count < 20) {
if (is_abundant(j)) {
print(s"$j ")
count += 1
}
j += 2
}
}
Task 2: First-class Function
Create sub compose($f, $g) which takes in two parameters $f and $g as subroutine refs and returns subroutine ref i.e. compose($f, $g)->($x) = $f->($g->($x))
e.g.
$f = (one or more parameters function)
$g = (one or more parameters function)
$h = compose($f, $g)
$f->($g->($x,$y, ..)) == $h->($x, $y, ..) for any $x, $y, ...
There are some problems with this task specification. First, it doesn’t say what we should do, but more or less how it should (probably) be done in Perl. I usually do my first implementation of a challenge task in Raku, and it would make little sense to implement the provided pseudo-code in Raku.
The second problem is that, when composing functions, you can’t have just any random number of parameters. The arity (number of parameters) of the second function must usually match the number of values returned by the first one. I’ll deal primarily with examples of functions taking one parameter, but will also show an example with variadic functions.
First-Class Function in Raku
Raku has the infix:<∘> (ring) or infix:<o> function composition operator, which combines two functions, so that the left function is called with the return value of the right function.
We could use this operator directly, but since we are asked to write a compose subroutine, we’ll carry out the extra step of creating such a subroutine.
sub f($n) { $n / 2 + 1}
sub g($n) { $n * 2 }
sub compose (&h1, &h2) {
&h1 ∘ &h2; # h1 will be called with the return value of h2
# could also be written: &h1 o &h2;
}
my &composed = compose(&f, &g);
say composed 2;
This script displays the following output:
$ raku ./first-class.raku
3
Our compose subroutine will also work with variadic input functions (taking a variable number of arguments). For example, here, we use a triple subroutine multiplying by 3 the items of a list of integers and a concat subroutine concatenating the resulting integers into a string (with a _ separator):
sub concat { join "_", @_}
sub triple { map {$_ * 3}, @_ }
sub compose (&h1, &h2) {
&h1 ∘ &h2; # h1 will be called with the return value of h2
}
my &composed = compose(&concat, &triple);
say composed <2 4 6 8>;
This generates the following output:
$ ./raku first-class_2.raku
6_12_18_24
First-Class Function in Perl
Here, the compose subroutine is a function factory that takes two subroutine references as input parameters and returns an anonymous subroutine reference combining the two input subroutines.
use strict;
use warnings;
use feature "say";
sub f { shift() / 2 + 1}
sub g { shift() * 2 }
sub compose {
my ($f, $g) = @_;
sub {
$f -> ($g -> (@_))
};
}
my $composed = compose( \&f, \&g);
say $composed->(2);
This script displays the following output:
$ perl ./first-class.pl
3
Our compose subroutine will also work with variadic input functions (taking a variable number of arguments). For example, here, we use a triple subroutine multiplying by 3 the items of a list of integers and a concat subroutine concatenating the resulting integers into a string (with a _ separator):
use strict;
use warnings;
use feature "say";
sub concat { join "_", @_}
sub triple { map $_ * 3, @_ }
sub compose {
my ($f, $g) = @_;
sub {
$f -> ($g -> (@_))
};
}
my $composed = compose(\&concat, \&triple);
say $composed->(qw/2 4 6 8/);
This script displays the following output:
$ perl first-class_2.pl
6_12_18_24
First-Class Function in Other Programming Languages
Update on July 2, 2022: added this section with other programming languages
Using first-class functions is usually a relatively advanced topic. I can do it quite easily in Perl and Raku, but I’m only kind of a novice in several of the programming languages presented below in this section. So, in some cases, I had to look it up in the Internet and some of the solutions are copied in part from others. Thus, I do not claim full authorship on these code snippets, but, so what? After all, writing a computer program is very often about taking an existing solution and modifying it to meet new requirements.
In all cases, we will compose a function returning twice the input parameter and a function that, for an input parameter p, returns p/2 + 1. And we display the result for input integers between 1 and 6. In some cases, we also display the result of actually chaining calls of the two functions. The result might be something like that:
2.0 2.0
3.0 3.0
4.0 4.0
5.0 5.0
6.0 6.0
7.0 7.0
We will not repeat the output for each programming language.
In D
In D, a delegate is a kind of pointer to a function.
import std.stdio;
T delegate(S) compose(T, U, S)(in T delegate(U) f,
in U delegate(S) g) {
return s => f(g(s));
}
void main() {
auto h = compose((int x) => x / 2 + 1, (int x) => x * 2);
for (int i = 1; i <= 6; i++) {
writeln(i);
}
}
In Julia
Like Raku, Julia has the ∘ function compose operator, making the solution pretty straight forward.
function f(p)
return p / 2 + 1
end
function g(p)
return p * 2
end
function compose(h1, h2)
return h1 ∘ h2;
end
h = compose(f, g)
for i in 1:5
println(h(i), " ", f(g(i)))
end
In Kotlin
fun f(x: Int): Int = x/2 + 1
fun g(x: Int): Int = x * 2
fun compose(f: (Int) -> Int, g: (Int) -> Int): (Int) -> Int = { f(g(it)) }
fun main() {
for (i in 2..6) {
println(compose(::f, ::g)(i))
}
}
In Nim
import sugar
proc compose[A,B,C](h1: A -> B, h2: B -> C): A -> C = (x: A) => h1(h2(x))
proc f(x: int): int = int(x / 2) + 1
proc g(x: int): int = x * 2
var h = compose(f, g)
for i in 1..6:
echo (h(i), f(g(i)))
In Python
def compose(f1, f2):
return lambda x: f1(f2(x))
def f(p):
return p / 2 + 1
def g(p):
return p * 2
h = compose(f, g)
for i in range(1, 6):
print (f(g(i)), " ", h(i))
In Ruby
def compose(h1, h2)
lambda {|x| h1.call(h2.call(x))}
end
f = lambda { |x| return x / 2 + 1 }
g = lambda { |x| return x * 2 }
h = compose(f, g)
for i in 1.upto(6)
print ("#{h[i]} #{f.call(g.call(i))}\n")
end
In Scala
object first_class extends App {
def compose[A](h1: A => A, h2: A => A) = { x: A => h1(h2(x)) }
def f(x: Int) = x / 2 + 1
def g(x: Int) = x * 2
val h = compose(f, g)
for (i <- 1 to 6) {
println(s"${h(i)} ${f(g(i))}")
}
}
Wrapping up
The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on July 10, 2022. And, please, also spread the word about the Perl Weekly Challenge if you can.
I am the author of the "Think Perl 6" book (O'Reilly, 2017) and I blog about the Perl 5 and Raku programming languages.
Leave a comment