## PWC 171 › Odd Abundant Numbers

This post is part of a series on Mohammad Anwar’s excellent Weekly Challenge, where hackers submit solutions in Perl, Raku, or any other language, to two different challenges every week. (It’s a lot of fun, if you’re into that sort of thing.)

This week’s tasks include a simple number theory calculation, and a language feature. Here’s a look at task 1.

## Odd Abundant Numbers

Abundant numbers are numbers where the sum of the proper divisors is greater than the number. The first odd abundant number is 945. 945’s proper divisors are 1, 3, 5, 7, 9, 15, 21, 27, 35, 45, 63, 105, 135, 189, and 315. (Recall that we exclude 945 itself as a proper divisor.)

The sum of those divisors is 975, so therefore 945 is an abundant number.

Equivalently, a number is abundant if the sum of all divisors is greater than twice the number. We’ll see both variations in the solutions below.

I’m going to take you through a few different approaches. Since I don’t like repeating myself, let’s get some foreshadowing for task #2 going, by using a first class function:

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;
}


The above code takes in a code ref ($is_abundant) and a limit ($N). We loop over all odd numbers, pushing any that pass the $is_abundant check to our result. Although the above version suited my purposes better, it’s also possible to do this with an iterator, to avoid having to store the intermediate result: sub odd_abundant_iterator(&) { my$is_abundant = shift;
my $n = 1; sub { do {$n += 2 } until $is_abundant->($n);

$n; } }  Now that we have a framework for gathering abundant numbers, let’s try it a few different ways. ### Brute force The first way you might think to try is simply to brute force your way through every divisor of every number. This is O(n) for each number, and takes over a second to find the first 20 numbers: sub n_abundant_naive { n_odd_abundant { my$n = shift;
$n < sum grep {$n % $_ == 0 } 1..$n/2;
} $_[0]; }  ### Using sqrt Stopping at $$\sqrt{n}$$ perhaps unsurprisingly brings the asymptotic time down to O($$\sqrt{n}$$). Since divisors come in pairs, we can simply calculate the other divisor and avoid looping through most of the numbers: 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];
}


It might not seem like a huge change, but the above code runs about 27 times faster than the naïve version, when asked to find the first 20 odd abundant numbers.

### Using Math::Prime::Utildivisor_sum

Just for fun, our old friend, Math::Prime::Util has a function that seems perfect for our needs: divisor_sum. It does what it says on the tin: it calculates the sum of the divisors of whatever number we give it.

sub n_abundant_mpu {
n_odd_abundant {
my $n = shift; my$sum = divisor_sum($n); 2*$n < $sum; }$_[0];
}


This one is another 12 times faster than the sqrt solution, and 356 times faster than the naïve method. Great, right? Well, not so fast. Under the hood, the divisor_sum function is still finding all divisors for every number, so we’re still at $$O(n \sqrt{n})$$ time. It’s only faster because of the very tightly optimized C code under the hood.

### Sieve

We can still do quite a bit better by realizing that since we’re looking for a whole bunch of abundant numbers, we’re repeating the same calculations over and over again, for every multiple of a number we’ve seen already. So as long as we’re willing to tweak the requirement slightly to find all abundant numbers below a given limit (although we’ll see how we can still accommodate the old calling syntax if we really want to), we can do much better:

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;
}


When called as n_odd_abundant_sieve(10000), this returns the first 23 odd abundant numbers, about twice as fast as the sqrt version returns 20. That’s because this algorithm runs in $$O(n \log{n})$$ time, which is strictly less than $$O(n \sqrt{n})$$ time for all $$n > 0$$. It grows significantly slower.

#### Sneaking up on the limit

In number theory circles, finding all numbers below a limit is usually just fine, but if we wanted to be a stickler for the parameters of the challenge and return only the first 20, we could simply call n_odd_abundant_sieve multiple times, doubling the limit every time, until we have at least 20 results. I wouldn’t bother, though.

You might be wondering, “how does this perform compared to the MPU version?”

For small values (the first 23 numbers in the sequence), the MPU version is faster by about 200%. However, when given more realistic limits, our better algorithm pulls ahead. It breaks even at about 100 numbers on my machine. By the time we ask for 150 numbers, the sieve is already 60% faster.

Benchmarks are an incredibly useful—and essential—tool when you need to write high performance code. Knowing that one algorithm is faster than another doesn’t always translate to real code. When dealing with implementation details, those hidden constants can really make a difference. What’s also really important, however, is knowing your requirements. If we’re only ever going to need to find less than 100 abundant primes, the MPU version might be a worthy choice. However, if we want to push it beyond that, then the better algorithm wins.

Of course, translating the sieve algorithm to tight C code would blow both of them out of the water at any value of n, since the sieve version grows strictly slower than the MPU version.

## Raku

Here’s a quick port to Raku. If you’re only concerned with outputting the results, there’s no point in storing them first:

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];
}

}


## PWC 171 › First Class Functions

This post is part of a series on Mohammad Anwar’s excellent Weekly Challenge, where hackers submit solutions in Perl, Raku, or any other language, to two different challenges every week. (It’s a lot of fun, if you’re into that sort of thing.)

Task #2 this week is no doubt about first class functions, but gets more specific, asking us to have a go at function composition:

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))

Before we get too far ahead of ourselves, let’s briefly review what these terms mean.

## First Class Functions

A language that supports first class functions simply allows you to pass functions around like any other variable. Passing anonymous functions (also known as lambda functions) around is usually included in this definition as well. Perl makes this easy:

my $add2 = sub {$_[0] + 2 }; # Returns a sub that adds 2 to its argument
$sub->(5); # Returns 7  That example may not be the most compelling, but for some motivation, look no farther than Perl’s map or grep builtins. When you call something like map {$_ * $_ } 1..10 to get the first ten square numbers, that block {$_ * $_ } is an anonymous subroutine. First class functions are incredibly useful, and deserve more discussion than I can cram into this blog post, so perhaps I’ll do them justice with a longer dedicated post in the future. ## Function Composition Function composition is a distinct concept in mathematics. In computer science, it depends on first class functions, but is otherwise not related. Function composition, often denoted with the ∘ operator, takes two functions f and g and produces a new function: $$h = g \circ f \text{ such that } h(x) = g(f(x))$$ The reason it’s usually written as g ∘ f is that in plain English, g follows f, because we are feeding the output of f into g. Of course, f and g are just symbols, so they can be swapped to match the task description with no issues: $$h = f \circ g \text{ such that } h(x) = f(g(x))$$ ## Perl Now that we’ve gotten all of the pesky definitions out of the way, the code is … well, there’s hardly any code at all, really. Here’s a function that generates the composition h = fg: sub comp { my ($f, $g) = @_; sub {$f->($g->(@_)) } }  Here’s an example usage that calculates the sum of squares of a list of numbers: 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); # 385  I chose to use List::Util‘s sum0 function so I could demonstrate how to pass in a reference to a named function. The $squares function shows how to use a variable. I could have also done this as an anonymous function:

@fac == 1 ? $_[0] : home_prime(join '', @fac); }  I like this solution for its expressiveness, but it’s about 20% slower than the following iterative version: Continue reading “PWC 168 › Home Prime” ## PWC 163 › A tail of two sums This post is part of a series on Mohammad Anwar’s excellent Weekly Challenge, where hackers submit solutions in Perl, Raku, or any other language, to two different challenges every week. (It’s a lot of fun, if you’re into that sort of thing.) This week’s challenges are very quick, so I’m putting them in one blog post. The title is a bit of a play on words, given the tail recursion in part 2. Full solutions are available at GitHub. ## Task 1 › Bitwise Sum For the first task, we’re asked to first bitwise AND (&) each unique pair of numbers, and then compute the sum of those operations. So, given an input of (a, b, c), we would compute: a & b + a & c + b & c To formalize this a bit, in preparation for writing the code, consider a pair (ni, nj) where i and j are the indices in the input array. Unique pairs could be interpreted to mean ji. However, the provided example clearly implies that self pairs are to be avoided, so we’ll include pairs where j > i. So for an array of length k (n1 … nk), this looks like: $${ \displaystyle \sum \limits_{i=1}^{k} } \sum_{j=i+1}^{k} n_i\ \&\ n_j$$ Continue reading “PWC 163 › A tail of two sums” ## PWC 110 › Phone Number Validation This post is part of a series on Mohammad Anwar’s excellent Weekly Challenge, where hackers submit solutions in Perl, Raku, or any other language, to two different challenges every week. (It’s a lot of fun, if you’re into that sort of thing.) Personal note: I’ve had to take a break from participating in the PWC, but I’m back for this week, at least. Hopefully I’ll be able to contribute more again. The first task this week is a sort of simple phone number validation, based on provided templates. Numbers must match the following, where n is any decimal digit: +nn nnnnnnnnnn (nn) nnnnnnnnnn nnnn nnnnnnnnnn  Based on the provided sample output, it seems clear that leading and trailing whitespace are ignored. Internal whitespace is also compressed, as the first provided template has two spaces after +nn, yet the phone number +44 1148820341 is supposed to match. Let’s try two different methods of matching, with Perl and Raku. Continue reading “PWC 110 › Phone Number Validation” ## PWC 110 › Transpose CSV File This post is part of a series on Mohammad Anwar’s excellent Weekly Challenge, where hackers submit solutions in Perl, Raku, or any other language, to two different challenges every week. (It’s a lot of fun, if you’re into that sort of thing.) The second task this week is simple: given a (simplified) comma-separated-value (CSV) file, transpose its rows and columns. For example: $$\begin{bmatrix} A & B & C & D \\ 1 & 2 & 3 & 4 \\ w & x & y & z \end{bmatrix}^T \Rightarrow \begin{bmatrix} A & 1 & w \\ B & 2 & x \\ C & 3 & y \\ D & 4 & z \end{bmatrix}$$ The challenge task does not actually refer to the input as CSV, so I’m using that term loosely, with simplified parsing to match the input specification. If more compliant parsing is needed, one could use the usual Text::CSV module in Perl, or ports in Raku. There are a couple of ways to transpose files, which I’ll explore in Raku and Perl. Continue reading “PWC 110 › Transpose CSV File” ## PWC 056 › Path Sum This post is part of a series on Mohammad Anwar’s excellent Weekly Challenge, where hackers submit solutions in Perl, Raku, or any other language, to two different challenges every week. (It’s a lot of fun, if you’re into that sort of thing.) Task #2 this week is a simple tree traversal: You are given a binary tree and a sum, write a script to find if the tree has a path such that adding up all the values along the path equals the given sum. Only complete paths (from root to leaf node) may be considered for a sum. For both my Perl and Raku versions, I’m going super-lean with the implementation, using only array references. The “node,” which recursively defines an entire (sub)tree, looks like this: • Element 0: Node’s value • Elements 1..N: References to child nodes Thus, the (Raku) syntax my @tree = [10, [18, [5], [2]], [8, [16, [18]], [9]]] describes a tree that looks like this:  10 / \ 18 8 / \ / \ 5 2 16 9 / 18  If we look for a path sum of 30, there is precisely one path with that sum: 10 18 2. It’s worth noting that, although the task is limited to binary trees, my implementation will handle m-ary trees. Forcing it to handle only binary trees would actually be slightly more difficult, and a lot less useful. Continue reading “PWC 056 › Path Sum” ## PWC 056 › Diff-K This post is part of a series on Mohammad Anwar’s excellent Weekly Challenge, where hackers submit solutions in Perl, Raku, or any other language, to two different challenges every week. (It’s a lot of fun, if you’re into that sort of thing.) Task #1 this week is to implement the Diff-K algorithm, as explained by Mohammad: You are given an array @N of positive integers (sorted) and another non negative integer k. Write a script to find if there exists 2 indices i and j such that A[i] – A[j] = k and i != j. This one is pretty easy. We can boil down the solution into two operations for each element ($_) of @N:

• First, filter @N for elements where $k+$_ exists in @N.
• For the remaining elements, return an array containing the indexes of $k+$_ and \$_.

To make this easier and more efficient, we’ll create an %idx_of hash to store the index of each element in @N. This can be created in linear time, and gives us O(1) lookups for both operations, above.

I really like how easy it is to create a reverse hash like this in Raku:

my %idx_of = @N.antipairs;

Continue reading “PWC 056 › Diff-K”

## PWC 054 › Collatz Conjecture

This post is part of a series on Mohammad Anwar’s excellent Weekly Challenge, where hackers submit solutions in Perl, Raku, or any other language, to two different challenges every week. (It’s a lot of fun, if you’re into that sort of thing.)

Task #2 this week was one of my devising:

It is thought that the following sequence will always reach 1:

$$Collatz(n) = \begin{cases} n \div 2 & n \text{ is even} \\ 3n + 1 & n \text{ is odd} \end{cases}$$

For example, if we start at 23, we get the following sequence:

23 → 70 → 35 → 106 → 53 → 160 → 80 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

Write a function that finds the Collatz sequence for any positive integer. Notice how the sequence itself may go far above the original starting number.

## Extra Credit

Have your script calculate the sequence length for all starting numbers up to 1000000 (1e6), and output the starting number and sequence length for the longest 20 sequences.

I’ve always liked the Collatz conjecture. It is simple enough for schoolchildren to play with, yet the math to prove the conjecture is still beyond our greatest mathematicians.

Here is how I solved this task.

Continue reading “PWC 054 › Collatz Conjecture”