Factory People in a Factory World

Wherein we toe the line, and the line tows us…

THE WEEKLY CHALLENGE – PERL & RAKU #153 Task 2


I’d always thought the world was a wish-granting factory.

Caesar Augustus

Apparently, the world is not a wish granting factory.

Caesar Augustus


Factorions

Submitted by: Mohammad S Anwar

You are given an integer, $n.

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

A factorion is a natural number that equals the sum of the factorials of its digits.

Example 1:
Input: $n = 145
Output: 1

    Since 1! + 4! + 5! => 1 + 24 + 120 = 145
Example 2:
Input: $n = 123
Output: 0

    Since 1! + 2! + 3! => 1 + 2 + 6 <> 123

METHOD

This is another example of a multi-part puzzle that at first may seem to be more complicated than it turns out in the end.

Which is to say the compounding factorials component may on the face of it seem daunting, but on further reflection we are only asking for the factorial for any single digit. So there’s ten of these, and those are all the values we will ever need from that function.

In fact, if we make a 1:1 mapping of the digits to their corresponding factorials, we can divide a number down into its digits and straight-away substitute in the associated values before summing. Or even while summing. We have options.

At that point we only need to check for equality between the value and its factorial digit-sum.

Because we only need the ten factorial values, it would make sense to hard-code them into an array or hash lookup, indexed against the digit values 0-9. But we’re not going to do that — we walk our own path in this crazy, mixed up world. Instead we’re going to make a short factorial function and calculate the sequence from 0 through 9. Because YOLO that’s why.

Party on, Garth, party on.

Observations

It turns out there are a grand total of 4 factorions: 1, 2, 145 and 40585. And how do we know this? Because we looked, that’s why.

So how about above 40585? How do we know when to stop looking?

There can be no factorials above 7 digits because the smallest 8-digit number — 10,000,000 — is larger than the digit-sum of the largest 8-digit number, 99,999,999.

9! + 9! + 9! + 9! + 9! + 9! + 9! + 9! = 2,903,040

From this we can conclude that no 8-digit number can possibly be large enough to sum to its own value, and by this same reasoning no larger number can either, so that’s the end of that. Consequently after having manually sifted through values up to 10,000,000, we can definitively state that these are the only instances.

This is indeed the case, as per the listing in the OEIS:

A014080Factorions: equal to the sum of the factorials of their digits in base 10 

I mean, we proved it, but it’s nice to have confirmation too I suppose.

PERL 5 SOLUTION

Because it doesn’t take long at all, we’re going to go ahead and find all of the factorions, scanning the range from 1 to 10,000,000. Trying values one at a time is just a recipe for sadness anyway, so we’re going to avoid that at all costs and make one tiny piece of the world that much better. 1

A mapping is used to swap in the factorial for each digit we find and the list is summed. As what we’re looking for is an up/down judgement on a candidate’s status, we don’t really care what exactly is returned, and Perl’s truth and falsity values for the equality will do just fine.


1 Clifford A. Pickover coined the term “factorion” in 1995, in a chapter of his book The Keys to Infinity appropriately titled “The Loneliness of the Factorions”. There’s only four of them. Let’s keep them together.


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



our @fact = (1);
push @fact, $fact[-1] * $_ for 1..9;

sub is_factorion($n = 145, $ds = 0) {
    $ds += $_ for map { $fact[$_] } split //, $n;

    return $ds == $n 
}


for (1..10000000) {
    say if is_factorion($_);
}

Raku Solution

In Perl the process we originally thought would be complicated turned out to only require a few lines of code. In Raku, chaining methods on a candidate value makes the data flow even easier to follow. The first process, .comb , divided the input number into an array of characters. Then the elements of this array are mapped to their factorial values and finally the data, now an array, is summed.

And the factorials? For that we can map the single digits to their value using the product reduction metaoperator. A list is created from 1 to the target and the multiplication operator is applied to every item in the list, with the final product reported. I really enjoy using Raku’s considerably more robust list-processing capabilities.

unit sub MAIN ( $n = 145 ) ;


my @f = map { [*] 1..$_ }, 0..9;    

sub is_factorion($n, $ds = 0) {
    $n == $n.comb
            .map({@f[$_]})
            .sum 
}

.say for (^10000000).grep: {is_factorion $_}


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