Tag: 153

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:

A014080

Factorions: 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. ¹

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.

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 $_}