Facts Left on the Table by the Front Door

Wherein we throw our common sense in a bowl so we have a chance of finding it again when we want to leave the party.

THE WEEKLY CHALLENGE – PERL & RAKU #153 Task 1


“An ideal world is left as an exercise to the reader.”

— Paul Graham


Left Factorials

Submitted by: Mohammad S Anwar

Write a script to compute Left Factorials of 1 to 10. Please refer to OEIS A003422 for more information.

Expected Output:
1, 2, 4, 10, 34, 154, 874, 5914, 46234, 409114

ANALYSIS

When first considering this task, I found the meaning of the term “left factorial” unusually elusive for some reason. Maybe because I wasn’t fully awake, and yes it’s true I was distracted, but however I had it figured in my head the answer to my confusion was, surprising no-one, considerably simpler than I made out.

Call it being unable to see the forest from the technical minutia, if you will.

In any case I will make a stab at my own descriptive definition:

Consider the factorials as an ordered sequence of values starting at 0 and incrementing by 1. The Left Factorial is the sum of all values in this sequence for indices less than, but not including, the value in question.

So L(4) = 3! + 2! + 1! + 0!

Another clver bit of nomaclature I saw was to denotate this as:

!5 = 0! + 1! + 2! + 3! + 4!

Note the exclamation is placed to the left for the left factorial. Clever that. This is only one of the more common ways to indicate the Left Factorial. For now I think we’ll just use a generic bold letter with an index subscripted: Ln

I’ve also decided to capitalize Left Factorial, reasoning that it sets the term apart somewhat from the “normal” factorials, which are also going to come up a lot in discussion, which if we’re not careful could be quite confusing.

This is all well and good, except that unfortunately there exists another definition for the identical term as the derangement number of a list, also known as the subfactorial. The derangement number is the number of ways a list of elements can be rearranged such that no element remains in its original position. Which is terribly interesting, but has nothing to do with our problem today. So we’re going to note that, put it aside, and pretend it doesn’t exist, lest the shiny thing distract us. Ohh, look! Shiny shiny derangements!

The zero factorial, 0! is a funny concept, being the product of no values. For an assortment of reasons it has been decided by consent to be equal to 1, the multiplicative identity, instead of, say, 0 or NaN. This is acknowledged to be not exactly obvious, but then again neither is the meaning of the product of no values. Suffice to say it works out and makes sense as a continuing progression of the sequence as a whole, and practicality has won the day. The absolute conceptual meaning of the term, as is often the case when a value drops to zero, remains considerably less clear. Nothingness as a thing under examination has a tendency to do that. It looks complete from a distance, but the closer you get to it the more the substance turns to dust.

METHOD

To compute a list of the first ten, or whatever number, of Left Factorials, we will need to compute normal factorials and maintain a running sum of these to build up the sequence . There’s a recurrence relation we can exploit:

Ln = Ln-1 + (n-1)!

Which is to say the Left Factorial of some number n is the previous Left Factorial constructed plus the factorial of the previous index value. With every new position added we add one more factorial value, that of the previous index in the series. Thus at every index we have a complete sum of all earlier factorials, built up by adding one value at a time.

Another recurrence relation can be drawn on as well to facilitate construction of the factorials themselves:

n! = n × (n-1)!

Or in other words we multiply the previous factorial by the current index to bring it up to date.

5! = 5 × 4 × 3 × 2 × 1

6! = 6 × 5 × 4 × 3 × 2 × 1

or

6! = 6 × 5!

So really what we need to keep track of here are only three values: the current index, the value of last Left Factorial calculated, and the value of the last factorial product used in the calculations, which will be the factorial for the number one less than the previous index. Perhaps it would be clearer to combine the two earlier recurrences into a single equation:

Ln = Ln-1 + (n-2)! × (n-1)

We use the previous Left Factorial to compose the new one, using the previous factorial to bring it up to date. However we use the factorial previous to that to update that factorial, so we need ultimately to go back two steps to keep things in sync.

On the other hand there’s no recomputing of products at all if we do it this way.

PERL 5 SOLUTION

Ultimately coding in the recurrence relation is quite compact, but because we’re always at least one behind the indexing is a little tricky. We keep a counter that trails the actual index being added, so at every iteration we multiply up a running factorial term to the new value, for the previous index. Adding this to the last Left Factorial created and we have a new value for that, which is pushed onto the sequence. Only then is the counter incremented and we go around again — as such the counter is always one behind the current index.

To keep things interesting we won’t limit ourselves to finding 10 values. Instead we’ll provide an input for an arbitrary number of vales from the sequence.

Of note: things blow up quickly along the factorial number line. We can only calculate up to L21 before we run out of integer in a 64-bit build of Perl, so we add the bigint pragma. Because the processing is very efficient, this does not appreciably slow calculation and we can produce absurdly large Left Factorials in short order. Like, ridiculously huge values.

You know, if we want to do that for some reason.

use warnings;
use strict;
use utf8;
use feature ":5.26";
use feature qw(signatures);
no warnings 'experimental::signatures';

my $num   = shift // 21;

my @left  = (0,1);
my $fact  = 1;
my $count = 1;

while ($count < $num) {
    $fact *= $count;
    push @left, $left[-1] + $fact;
    $count++;
}

say for @left;

Raku Solution

In Raku, a pair of reduction metaoperators drives this bus. Unwrapping this package from the right, we have a sequence of indices for our output terms: 0 to the given quantity requested. For each of these values we then compose a range from 0 up to but not including the value (sound familiar?) and for each value in that range we then map the product reduction of the range from 1 to the the inner value. Each list of factorials produced this way is then summed to calculate the Left Factorial.

Yes it may be crazy-efficient to do it as we did with Perl, and of course that is the best way. But reconstructing and repeating that here would be a bit… redundant. And we couldn’t use not one but two reduction metaoperators so this way is way cooler, for some definitions of cooler. And I don’t care what anyone says, but metaoperators are cool.

unit sub MAIN ( $num  = 50 ) ;

say [+] map { [*] 1..$_ }, ^$_ for 0..$num;


The Perl Weekly Challenge, that idyllic glade wherein we stumble upon the holes for these sweet descents, is now known as

The Weekly Challenge – Perl and Raku

It is the creation of the lovely Mohammad Sajid Anwar and a veritable swarm of contributors from all over the world, who gather, as might be expected, weekly online to solve puzzles. Everyone is encouraged to visit, learn and contribute at

https://theweeklychallenge.org

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s