## Perl Weekly Challenge 153: Left Factorials and Factorions

These are some answers to the Week 153 of the Perl Weekly Challenge organized by Mohammad S. Anwar.

*Spoiler Alert:* This weekly challenge deadline is due in a few days from now (on February 27, 2022 at 24:00). This blog post offers some solutions to this challenge, please don’t read on if you intend to complete the challenge on your own.

## Task 1: Left Factorials

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

*Expected Output:*

```
1, 2, 4, 10, 34, 154, 874, 5914, 46234, 409114
```

The task specification unfortunately lacks a precise definition of left factorials. Looking at OEIS A003422, I found we could use the following recursive definition:

```
a(0) = 0
a(1) = 1
a(n) = n*a(n - 1) - (n - 1)*a(n - 2)
```

After I did some of the implementations below, I found another definition making more sense of left factorials (a.k.a. factorial sums). Left factorial of the integer n is the sum of the factorials of the integers from 0 to n - 1. Left factorial is commonly denoted by a prefixed exclamation mark. So we have:

with ! 0 = 0.

### Left Factorials in Raku

The implementation can easily be derived from the recursive definition above, except that I prefer an iterative implementation (well, it could probably be argued it is sort of a *cached* recursive approach, even though there is no recursive subroutine call):

```
my @a = 0, 1, 2;
for 3..10 -> $n {
@a[$n] = $n * @a[$n -1] - ($n - 1) * @a[$n - 2];
}
say @a[1..10];
```

This program displays the following output:

```
$ raku ./left_fact.raku
(1 2 4 10 34 154 874 5914 46234 409114)
```

In Raku, we can also use sigilless variables) to make the code look more like a math formula:

```
my @a = 0, 1;
for 2..10 -> \n {
@a[n] = n * @a[n -1] - (n - 1) * @a[n - 2];
}
say @a[1..10];
```

This new version displays the same output.

As mentioned before, the above implementations were done before I found about the second (summation of factorials) formula. Raku has reduction metaoperators) making it easy to implement factorials and summations. This can lead to this concise Raku one-liner using two triangular reduction operators:

```
$ raku -e 'say (|[\+] 1, (|[\*] 1..*))[0..9]'
(1 2 4 10 34 154 874 5914 46234 409114)
```

In addition, we could also define a prefix `!`

operator, but this has the drawback of redefining the standard negation prefix operator `!`

. This does work, but it’s probably not very wise to do so.

### Left Factorials in Perl

Again, the implementation can easily be derived from the recursive definition provided above:

```
use strict;
use warnings;
use feature "say";
my @a = (0, 1);
for my $n (2..10) {
$a[$n] = $n * $a[$n -1] - ($n - 1) * $a[$n - 2];
}
say "@a[1..10]";
```

This program displays the following output:

```
$ perl ./left_fact.pl
1 2 4 10 34 154 874 5914 46234 409114
```

### Left Factorials in Other Languages

#### In Julia

Using the recursive definition of left factorials:

```
a = [1, 2] # Julia arrays start with index 1
for n in 3:10
push!(a, n * a[n - 1] - (n - 1) * a[n - 2])
end
println(a)
```

Output:

```
$ julia ./left_fact.jl
[1, 2, 4, 10, 34, 154, 874, 5914, 46234, 409114]
```

#### In Ring

Here, we use the summation of factorials definition. For each iteration in the `for`

loop, we multiply `fact`

by the loop variable to obtain the new factorial, and we add the new factorial to the `sum`

variable. For some strange reason, `see left_fact + " "'`

doesn’t output a space after the variable value, where as `see " " + left_fact`

does what we want. To me, it looks like a small bug in the language, but I may be missing something.

```
left_fact = 1
fact = 1
for i = 1 to 10
see " " + left_fact
fact *= i
left_fact += fact
next
see " " + nl
```

Output:

```
$ ring ./left_fact.ring
1 2 4 10 34 154 874 5914 46234 409114
```

#### In Python

Again using the summation of factorials definition.

```
fact = 1
left_fact = 1
for n in range (1, 11):
print(left_fact)
fact = fact * n
left_fact = left_fact + fact
```

Output:

```
$ python3 ./left_fact.py
1
2
4
10
34
154
874
5914
46234
409114
```

Note that I didn’t remember how to how to output data without a new line in Python, and I was too lazy to spend time to find out. This is proverbially left as an exercise to the reader, as this output fits the specification bill.

#### In Awk

Using the summation of factorials definition.

```
BEGIN {
left_fact = 1
fact = 1
for (i = 1; i <= 10; i++) {
printf "%d ", left_fact
fact *= i
left_fact += fact
}
printf "\n"
}
```

Output:

```
$ awk -f left_fact.awk
1 2 4 10 34 154 874 5914 46234 409114
```

#### In C

Using the summation of factorials definition.

```
#include <stdio.h>
int main () {
int sum = 1;
int fact = 1;
for (int i = 1; i <= 10; i++) {
printf("%d ", sum);
fact *= i;
sum += fact;
}
printf ("\n");
return 0;
}
```

Output:

```
$ ./test-left
1 2 4 10 34 154 874 5914 46234 409114
```

#### In Bc

Using the summation of factorials definition.

```
sum = 1
fact = 1
for (n = 1; n <= 10; n ++) {
print sum, " "
fact = fact * n
sum = sum + fact
}
```

Output:

```
$ bc left_fact.bc
bc 1.06.95
Copyright (...)
1 2 4 10 34 154 874 5914 46234 409114
```

#### In Tcl

Using the summation of factorials definition.

```
set left_fact 1
set fact 1
puts -nonewline $left_fact
for {set i 1} {$i <= 10} {incr i} {
puts -nonewline "${left_fact} "
set fact [expr $fact * $i]
set left_fact [expr $left_fact + $fact]
}
puts ""
```

Output:

```
$ tclsh ./left_fact.tcl
11 2 4 10 34 154 874 5914 46234 409114
```

#### In R

Using the summation of factorials definition.

```
left_fact <- 1
fact <- 1
for (i in 1:10) {
cat(left_fact, '')
fact <- fact * i
left_fact <- left_fact + fact
}
cat("\n")
```

Output:

```
$ Rscript left_fact.r
1 2 4 10 34 154 874 5914 46234 409114
```

#### In Pascal

Using the summation of factorials definition.

```
Program leftfact;
var
fact, left_fact: longint;
i: integer;
begin
left_fact := 1;
fact := 1;
for i := 1 to 10 do begin
write(left_fact, ' ');
fact := fact * i;
left_fact := left_fact + fact;
end;
writeln('');
end.
```

Output:

```
$ ./left_fact
1 2 4 10 34 154 874 5914 46234 409114
```

#### In Rust

Using the summation of factorials definition.

```
fn main() {
let mut fact = 1;
let mut left_fact = 1;
for n in 1..11 {
println!("{}", left_fact);
fact = fact * n;
left_fact = left_fact + fact;
}
}
```

Output:

```
$ ./left_fact
1
2
4
10
34
154
874
5914
46234
409114
```

#### In Go

Using the summation of factorials definition.

```
package main
import "fmt"
func main() {
left_fact := 1
fact := 1
for i := 1; i <= 10; i++ {
fmt.Printf("%d ", left_fact)
fact *= i
left_fact += fact
}
fmt.Printf("\n")
}
```

Output:

```
1 2 4 10 34 154 874 5914 46234 409114
```

#### In Scala

Using the summation of factorials definition.

```
object fact_left extends App {
var fact = 1
var left_fact = 1
for (n <- 1 to 10) {
println(left_fact)
fact *= n
left_fact += fact
}
}
```

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

#### In Ruby

Using the summation of factorials definition.

```
fact = 1
left_fact = 1
for n in 1..10
printf "%d ", left_fact
fact *= n
left_fact += fact
end
printf "\n"
```

Output:

```
ruby left_fact.rb
1 2 4 10 34 154 874 5914 46234 409114
```

#### In Lua

Using the summation of factorials definition.

```
fact = 1
left_fact = 1
for n = 1, 10 do
print(left_fact)
fact = fact * n
left_fact = left_fact + fact
end
```

Output:

```
$ lua left_fact.lua
1
2
4
10
34
154
874
5914
46234
409114
```

#### In Kotlin

Using the summation of factorials definition.

```
fun main() {
var fact = 1
var left_fact = 1
for (i in 1..9) {
fact *= i
left_fact += fact
print("$left_fact ")
}
}
```

Output:

```
$ ./left_fact.kexe
2 4 10 34 154 874 5914 46234 409114
```

## Task 2: Factorions

*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
```

We will slightly deviate from the task specification and write a subroutine that checks whether an integer is a factorion, and write a program to find all factorions in a given range.

### Factorions in Raku

Here again, we use twice the reduction metaoperators), one (`[*] 1..$_`

) to compute the factorial of a digit, and one (`[+]`

) to sum up the digit factorials.

```
sub is_factorion (Int $in) {
my $sum = [+] map { [*] 1..$_ }, $in.comb;
return $sum == $in;
}
say $_ if is_factorion $_ for 1..50000;
```

We chose here an upper limit of 50,000 because it is known and proven that there are only 4 factorions in the decimal system, all smaller than 50,000. This solution is concise and elegant and the `is_factorion`

subroutine could easily be boiled down to a single code line:

```
sub is_factorion (Int $in) {
return $in == [+] map { [*] 1..$_ }, $in.comb;
}
```

This program displays the following output:

```
$ time raku ./factorion.raku
1
2
145
40585
real 0m13,079s
user 0m0,015s
sys 0m0,030s
```

Note that I timed the execution because I felt it was a bit slow. The reason for that slowness is that we’re computing the factorial of each digit a very large number of times. It is significantly more efficient to cache the factorials of each digit, for example by storing in an array (`@fact`

) the precomputed factorials of digits 0 to 9.

```
my @fact = map { [*] 1..$_ }, 0..9;
sub is_factorion (Int $in) {
my $sum = [+] map { @fact[$_] }, $in.comb;
return $sum == $in;
}
say $_ if is_factorion $_ for 1..50000;
```

This modified program displays the following output and timings:

```
$ time raku ./factorion.raku
1
2
145
40585
real 0m1,553s
user 0m0,000s
sys 0m0,015s
```

So caching the digit factorials made the program about 8.5 times faster.

### Factorions in Perl

In Perl, we implemented directly the cached version with a `@digit_fact`

array:

```
use strict;
use warnings;
use feature "say";
sub fact {
my $i = shift;
my $prod = 1;
$prod *= $_ for 2..$i;
return $prod;
}
my @digit_fact = map {fact $_} 0..9;
sub is_factorion {
my $in = shift;
my $sum = 0;
$sum += $_ for map { $digit_fact[$_] } split //, $in;
return $sum == $in;
#say $sum;
}
for (1..50000) {
say $_ if is_factorion($_)
}
```

This program displays the following output:

```
$ time perl ./factorion.pl
1
2
145
40585
real 0m0,182s
user 0m0,140s
sys 0m0,015s
```

### Factorions in Other Languages

#### In Julia

```
fact = map(x -> factorial(x), Vector(0:9))
function is_factorion(num)
sum = 0
start_num = num
for n in 1:length(string(num))
sum += fact[num % 10 + 1] # Julia arrays start at 1
num = num ÷ 10
end
return sum == start_num
end
for i in 1:50000
if is_factorion(i)
println(i)
end
end
```

Output:

```
$ julia ./factorion.jl
1
2
145
40585
```

#### In Ring

In Ring, list index starts at 1. That makes index management a bit complicated in this case, because we need to store the factorial of 0. So factorial 0 is stored at index 1, and all the others are shifted by 1. It’s not a problem, but it makes the code look a bit unnatural.

```
fact = [1, 1]
for k = 2 to 9
add (fact, k * fact[k]) # list indices start at 1
next
# see fact + nl
for n = 1 to 50000
if is_factorion(fact, n)
see n + nl
ok
next
func is_factorion fact, input
sum = 0
n = "" + input
for i = 1 to len(n)
digit = n[i]
sum += fact[1 + digit]
next
return input = sum
```

Output:

```
$ ring ./factorion.ring
1
2
145
40585
```

#### In Python

```
fact = [1] * 10
for n in range (1, 10):
fact[n] = n * fact[n - 1]
def is_factorion (input):
sum = 0
n = str(input)
for i in range (0, len(n)):
sum = sum + fact[int(n[i])]
return input == sum
for n in range(1, 50000):
if is_factorion(n):
print(n)
```

Output:

```
$ python3 ./factorion.py
1
2
145
40585
```

#### In C

```
#include <stdio.h>
char is_factorion(int fact[], int num) {
int sum = 0;
int n = num;
while (n > 0) {
sum += fact[n % 10];
n /= 10;
}
return num == sum;
}
int main() {
int fact[10];
fact[0] = 1;
for (int i = 1; i <= 9; i++) {
fact[i] = i * fact[i - 1];
}
for (int n = 1; n < 50000; n++) {
if (is_factorion(fact, n)) {
printf("%d ", n);
}
}
printf("\n");
return 0;
}
```

Output:

```
$ ./factorion 1 2 145 40585
```

#### In Awk

```
function populate_fact() {
fact[0] = 1
for (n = 1; n <= 9; n++) {
fact[n] = n * fact[n - 1]
}
}
function is_factorion(num) {
sum = 0
start_num = num
for (n = 0; n < length(start_num); n++) {
sum += fact[num % 10]
num = int(num / 10)
}
return sum == start_num
}
BEGIN {
populate_fact()
for (i = 1; i <= 50000; i++) {
if (is_factorion(i)) {
print i
}
}
}
```

Output:

```
$ awk -f factorion.awk
1
2
145
40585
```

#### In Bc

```
fact[0] = 1
for (n = 1; n <= 9; n++) {
fact[n] = n * fact[n - 1]
}
for (n = 1; n <= 50000; n++) {
sum = 0
i = n
while (i > 0) {
sum += fact[i % 10]
i /= 10
}
if (sum == n) {
print n, " "
}
}
halt
```

Output:

```
$ bc factorion.bc
bc 1.06.95
Copyright (...)
1 2 145 40585
```

#### In Scala

```
object factorion extends App {
def is_factorion(fact: Array[Int], num: Int): Boolean = {
var sum = 0
var i = num
while (i > 0) {
sum += fact(i % 10)
i /= 10
}
return num == sum
}
val fact = new Array[Int](12)
fact(0) = 1
for (n <- 1 to 9) {
fact(n) = n * fact(n - 1)
}
for (j <- 1 to 50000) {
if (is_factorion(fact, j)) {
println(j)
}
}
}
```

Output:

```
1
2
145
40585
```

#### In Lua

```
function is_factorion(fact, num)
sum = 0
i = num
while i > 0 do
sum = sum + fact[ 1 + i % 10]
i = math.floor(i / 10)
end
return num == sum
end
fact = {1}
for n = 1, 10 do
table.insert(fact, n * fact[n])
end
for j = 1, 50000 do
if is_factorion(fact, j) then
print(j)
end
end
```

Output:

```
$ lua factorion.lua
1
2
145
40585
```

#### In Kotlin

```
fun main() {
var fact = mutableListOf<Int>()
fact.add(1)
for (n in 1..9) {
fact.add(n * fact[n-1])
}
for (num in 1..50000) {
var i = num
var sum = 0
while (i > 0) {
sum += fact[i % 10]
i /= 10
}
if (num == sum) print ("$num ")
}
}
```

Output:

```
$ ./factorion.kexe
1 2 145 40585
```

#### In Ruby

```
def is_factorion(fact, num)
sum = 0
i = num
while i > 0
i, d = i.divmod(10)
sum += fact[d]
end
return num == sum
end
fact = [1]
for n in 1..10
fact.push(n * fact[n - 1])
end
for j in 1..50000
if is_factorion(fact, j)
printf "%d ", j
end
end
printf("\n")
```

Output:

```
$ ruby factorion.rb
1 2 145 40585
```

## Wrapping up

The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on March 6, 2022. And, please, also spread the word about the Perl Weekly Challenge if you can.

## Leave a comment