RabbitFarm

The examples used here are from The Weekly Challenge problem statement and demonstrate the working solution.

Part 1

Write a script to determine the first ten members of the Left Factorials sequence.

Solution

use strict;
use warnings;

use POSIX;
use constant UPPER_BOUND => INT_MAX/1000;

sub left_factorials_sieve{
    my($n) = @_;
    my @sieve = (0 .. UPPER_BOUND);
    my $x = 2;
    {
        my @sieve_indices = grep { $_ <= $x || $_ % $x == 0 } 0 .. @sieve - 1; 
        @sieve = map{ $sieve[$_] } @sieve_indices;
        $x++;
        redo if $x <= $n;
    }
    return @sieve[1 .. @sieve - 1];
}

MAIN:{
    print join(", ", left_factorials_sieve(10)) . "\n";
}

Sample Run

$ perl perl/ch-1.pl
1, 2, 4, 10, 34, 154, 874, 5914, 46234, 409114 

Notes

The problem statement for this refers to a On-Line Encyclopedia of Integer Sequences entry. That OEIS entry mentions some interesting facts about the sequence, including the sieve technique used here. Officially the sequence seems to start with 0 but since the example shows it starting with 1 here the initial 0 element is removed.

There is nothing special about the choice of UPPER_BOUND it is just an arbitrarily large number which fits the purpose. I chose the number via trial and error, but it seems there is a straightforward provable upper bound U required to get a sequence of required sequence length N. If this were a math text then I as the author would be compelled to leave a frustrating note that finding the upper bound is left as an exercise for the reader. Ha!

Part 2

Write a script to figure out if the given integer is a factorion.

Solution

use strict;
use warnings;

use boolean;

sub factorial{
    my($n) = @_;
    return 1 if $n == 1;
    $n * factorial($n - 1);
}

sub is_factorion{
    my($n) = @_;
    return boolean($n == unpack("%32I*", pack("I*", map {factorial($_)} split(//, $n))));
}

MAIN:{
    print is_factorion(145) . "\n";
    print is_factorion(123) . "\n";
}

Sample Run

$ perl perl/ch-2.pl
1
0

Notes

In this solution I tried to optimize for the least amount of code. Not quite a golfed solution, but compact, to be sure. The digits are obtained via split, passed to our totally boring recursive factorial() function, the sum of the resulting factorials taken using pack, and then that sum compared to $n. For convenience in stringifying the output boolean() is used.

References

Challenge 153

Left Factorial Sequence

Left Factorial

Factorion