Perl Weekly Challenge: Week 171

Challenge 1:

Abundant Number

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

Fairly straightforward.

We start by defining a list to hold our results and the number to start searching from.

my @abundants;
my $n = 1;

Then until we have 20 odd abundant numbers...

until @abundants.elems == 20 {

...we find all the divisors for the current value of $n. A small optimizzation we can make is to stop searching for divisors at $n / 2. Any divisors found will be stored in another list.

    my @divisors;
    for 1 .. $n / 2 -> $i {
        if $n %% $i {
            @divisors.push($i);
        }
    }

Once we have all the divisors, we total them and if the sum is greater than $n we have an abundant number and we can store it.

    if ([+] @divisors) > $n {
        @abundants.push($n);
    }

And then no matter what the outcome was we move on to the next candidate number. As we are only interested in odd abundant numbers, we can do another little optimization and increment $n by 2 thereby skipping even numbers.

    $n += 2;
}

Finally, the results are printed out nicely.

@abundants.join(q{, }).say;

(Full code on Github.)

This is the Perl version. It is pretty much a 1-1 translation from Raku except I had to use my own sum() function instead of [+].

my @abundants;
my $n = 1;

until (scalar @abundants == 20) {
    my @divisors;
    for my $i (1 .. $n / 2) {
        if ($n % $i == 0) {
            push @divisors, $i;
        }
    }

    if (sum(\@divisors) > $n) {
        push @abundants, $n;
    }

    $n += 2;
}

say join q{, }, @abundants;

(Full code on Github.)

The first 20 odd abundant numbers are:

945, 1575, 2205, 2835, 3465, 4095, 4725, 5355, 5775, 5985, 6435, 6615, 6825, 7245, 7425, 7875, 8085, 8415, 8505, 8925

Challenge 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, ...

I didn't really study functional languages such as LISP when I did my Computer Science degree. The primary language of instruction were C++ and Java neither of which had much in the way of functional features (though they do now.) It was not until later when I read Mark-Jason Dominus's "Higher Order Perl" that things really clicked for me. Now I use functional techniques a lot though I need to learn more I must admit. Btw, that book is available to read for free and download at the link I gave. You really should read it even if you're not programming in Perl.

An important concept in functional programming is that functions should be able to be used as data i.e stored in a variable or passed as an argument to another function etc. Languages which allow this sort of thing are said to have first-class functions. First-class functions can be used as basic building bricks to make new more complex functions. This is called composability.

Let's say we have two Perl functions:

square() takes one argument and returns it squared.

sub square {
    my ($x) = @_;

    return $x * $x;
}

sum() takes multiple arguments, adds them altogether and returns the result.

sub sum {
    my $total = 0;

    for my $elem (@_) {
        $total += $elem;
    }

    return $total;
}

Now what if we wanted to do both? We could just call both functions like this:

say square(sum(1, 2, 3));

but that's not very generic. What if requirements changed and we now want to multiply and square instead. We would have to write a multiply() function certainly but we would also have to review our codebase and change all the lines like the one above to:

say square(multiply(1,2,3));

Which could be all over the place in a huge project.

Instead we can write a function like this:

sub compose {

It starts by taking two references to functions as its' arguments.

    my ($f, $g) = @_;

Then it creates a new anonymous subroutine that calls the function stored in $g and then feeds the results into the function stored in $f.

    return sub { $f->($g->(@_)); };
}

we call it like this:

say compose(\&square, \&sum)->(1,2,3);

\& signifies a code reference. $f and $g could be square() and sum() or square() and multiply() or even sum() and multiply() etc. Or we can store the new subroutine in a variable like this:

my $h = compose(\&square, \&sum);
say $h->(1,2,3);

If we use $h everywhere, we can change sum() to multiply() once in the definition and not have to change any other line of code.

(Full Perl code on Github.)

This is the Raku version. It works the same way as Perl but has gotten rid of the unsightly ->s.

sub compose(&f, &g) {

    return sub (*@args) { &f(&g(@args)); };
}

sub square(Int $x) {
    return $x * $x;
}

sub sum(*@args) {
    return [+] @args;
}

say compose(&square, &sum)(1,2,3);

(Full Raku code on Github.)