PWC #171
PWC #171
Challenge 1 Odd Abundant Numbers
Abundant numbers are whole numbers (positive integers) where the sum of all the whole-number divisors is greater than the number itself (where the summation includes both prime and non-prime divisors and the number 1, but not the number itself) . They contrast with perfect numbers, where this sum exactly equals the number, and deficient numbers, where this sum is less than the number.
We are asked to find the first 20 odd abundant numbers.
I use the Math::Factor::XS package in Perl 5. This has the "factors" function which returns an array of all the factors of a number including non-prime factors (but excluding 1 and the number itself). Perl 5 does not have a ready-made sum function to sum over an array, but it is trivial to write one, along with another convenience function to print an array. We then loop over the odd numbers using a C-style for loop (for my $n=1;;$n+=2), calculating the sum of factors (remembering to add 1), and collecting the cases where this sum is higher than $n. We break when we have collected 20 such numbers, and then print them out.
This is slightly easier to do in Raku, since there is no need for home-made "sum" or "print array" functions. Here I use the Raku Prime::Factor library function divisors($n). It returns a list of all the divisors of a particular whole number $n, but unlike the Perl 5 library's "factors", it includes both 1 and the number itself. To find an abundant number therefore, we compare the sum to the number multiplied by two. The program gives the correct answers, but is slow.
Challenge 2 Compose two functions
Challenge 2 asks us to demonstrate the use of "first-class functions". Specifically, we are asked to show a function "compose" that takes two functions as its arguments, say f and g, and returns the composition of the two, say f(g(..)), which is another function.
In Raku, there is nothing to do, as there is a built-in operator "o" to compose functions. One can code a simple example to demonstrate its use.
In Perl 5 (recent versions), it is only slightly more difficult. One just directly passes references to the functions to the compose function, say $rf and $rg and then directly returns a reference to an anonymous sub as in "return sub {&$rf(&$rg(..)};".
I duly included this in my Perl script, (though I also passed the arguments @x to the inner function, which may not be quite what the task specified.). Incidentally, in all my programs for this challenge, I have done g o f, rather than f o g. In this blog entry though, I will continue to refer to f as the outer and g as the inner function which matches the task specification.
The ability to pass functions (well, subroutines) as arguments has actually been around since early days, via typeglobs. I thought it might be interesting to show this. Also, consider a slightly more complicated version of the challenge, where the inner function is only one of several parameters to the outer function. Thus we have for example,
f:=f(x,y,z,g,a); g:=g(...)
Using only features from Perl 4, we can write a subroutine "compose" that takes two typeglobs as arguments *f, *g, and returns their composition. One could return a typeglob to a subroutine defined within compose, but it is easier to return a string, which can be eval'ed later.
An interesting feature of typeglobs is that when you pass a typeglob to a subroutine, you are passing the entire symbol table entry for that typeglob. That is, when you pass *f, you do not just pass &f, you also pass @f, %f, $f, etc. We can exploit this to pass more information to our "compose" sub via a convenient naming convention. Here is how I implement it:
Let @f be the array of arguments to &f (when passed, the argument g is missing. We splice it in as part of the compose routine).
Let @g be the array of arguments to &g.
Let $f be the position in @f where we will splice in g.
Just passing the typeglobs *f and *g gives the compose subroutine access to all these variables.
Of course, this is not an implementation of first class functions, just a hack that gives a somewhat similar effect. It's not very desirable in terms of modern best practices because the variables have to be "local global" package variables. This approach should of course be avoided if one is writing a module for cpan for example, but might still be a useful pattern in small stand-alone single-user scripts.
I demonstrated my various flavors of compose using a supporting calculation from challenge 1, which is to calculate the sum of factors for 30 (the sum is 41, where 1 and 30 are not included). The composition is sum(factors(30)).
Julia
I also wrote scripts in Julia to benchmark. Julia does not have a factors function (that I could find), so I had to write my own sum_factors function for challenge 1. Otherwise things are similar to the Perl 5 and Raku solutions for challenge 1. Julia is slightly slower than Perl 5 for this due to its startup overhead.
For challenge 2, Julia being a relatively new language, has first-class functions built right in, and the compose function is trivial to write. (In fact, Julia has a built-in compose operator, like Raku, as I found out later.)
Julia solution for challenge 1
Julia solution for challenge 2
Someone else's solution (Wow!)
Like with Challenge #170, Philippe Bricourt alias brxfork has submitted an incredible Perl 5 one-liner here (this is for Challenge 1: abundant numbers).
This one not just prints out the answer, but gives a detailed explanation of the calculation for each abundant number found!
Let me try to unravel it. With Perl, of course, reading code is at least as challenging as writing it. :-)
Here is the one-liner:
perl -E '$_="N"; $" = "+" ; while ($sol < 20) {$_.="NN";my @sum;/^(N+?)\1+$(?{push @sum,length$1})(?!)/;eval "@sum" > length() and ++$sol and say length()," < ", eval "@sum" , " = ", "@sum" }'
First, the topic variable $_ is set to a string consisting of a single "N". The procedure will be to keep growing this string by adding two more "N"s each pass, so that the length of the growing string keeps track of odd numbers (1,3,...). Recall that $_ is the default variable on which regex matches operate.
The special variable $" represents the default separator used when a list @.. is enclosed in a string as in "@..". Usually this is a space so that if @p=(1,2,3,4,6), then "@p" in double quotes would become "1 2 3 4 6". The program changes this separator to "+" via the code $"="+". Now "@p" in my example would be represented as "1+2+3+4+6". You can perhaps see where this is tending. Divisors of each odd number would be accumulated in an array @sum. Then eval "@sum" will literally sum those divisors.
Next, the magic regex /^(N+?)\1+$(?{push @sum,length$1})(?!)/
It tests if the string "NNN..." can be parsed into some smaller string of N's say "N" or "NN" or "NNN" repeated throughout the whole string from beginning (^) to end ($). If this is the case, then the length of the smaller string is a divisor of the length of the larger string. We have found a divisor of the current odd number. We push this (length of the captured smaller string of N's) into the @sum array. Finally, the negative lookahead (?!) has the effect of sending the process back to find another match (another divisor) until all divisors are found. (I am somewhat fuzzy about why this works, but it does).
Next we eval "@sum" to get the sum of the divisors, and compare this to the length of $_ to check if the latter is an abundant odd number. If it is, we print the details, as in:
945 < 975 = 1+3+5+7+9+15+21+27+35+45+63+105+135+189+315
Then we loop to the next odd number and keep at it till we have 20 abundant numbers. Just a single loop is needed.
Comments