Just the Fact with Raku

This is my response to the Perl Weekly Challenge #153.

Challenge #153.1: Left Factorials

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

What exactly is the meaning of compute? Let us start with a very silly version:

#! /usr/bin/env raku

say "1, 2, 4, 10, 34, 154, 874, 5914, 46234, 409114";

Running it gives what you would expect:

$ ./left-factorials-silly 
1, 2, 4, 10, 34, 154, 874, 5914, 46234, 409114

The OEIS article reveals that the formula for the nth value is (0! .. n!).sum. The first value in the sequence is zero, but the challenge skips that one and starts with 1 (which according to OEIS is the second value). Let us do what the challenge asks for, inititally at least.

#! /usr/bin/env raku

my $lf := gather
{
  my $index = 0;                                      # [1]

  loop                                                # [2]
  {
    take (0 .. $index++).map({ [*] (1 .. $_) }).sum;  # [3]
  }
}

say $lf[^10]].join(", ");

[1] Used to keep track of the current index, as the formulae requires it.

[2] An eternal loop, giving one value for each iteration.

{3] The inside of the «map» (({ [*] (1 .. $_) }) is the faculty function, implemented with the Reduction Metaoperator [] that (in this case, as the operator is *) multiplies all the values together. The values are the numbers from 1 up to $_. The first part ((0 .. $index++).map(...)) gives us all the indices, and maps them to the corresponding faculty value. (I.e. 3 gives 3!). The final .sum adds them together, giving the current value in the sequence.

See docs.raku.org/language/operators#Reduction_metaoperators for more information about the Reduction Metaoperator [].

Running it:

$ ./left-factorials-loop
1, 2, 4, 10, 34, 154, 874, 5914, 46234, 409114

Note that this will recalculate all the factorial values a lot of times. We can - and indeed should - cache them:

#! /usr/bin/env raku

my $lf := gather
{
  my $index = 0;
  my $prev  = 0;                                # [1]

  loop
  {
    take $prev += ( [*] (1 .. $index++) ).sum;  # [2]
  }
}

say $lf[^10].join(", ");

[1] The previous value in the sequence, used by the next one. This is the cached value.

[2] Get the faculty of the new index, and add that to the previous value.

The result is as expected:

$ ./left-factorials-loop-cached
1, 2, 4, 10, 34, 154, 874, 5914, 46234, 409114

Let us amend this, so that we can get the first (or zero) value of 0, as OEIS would like us to:

#! /usr/bin/env raku

unit sub MAIN (:z(:$zero-based));

my $lf := gather
{
  my $index = 0;
  my $prev  = 0;

  take 0 if $zero-based;  # [1]

  loop
  {
    take $prev += ( [*] (1 .. $index++) ).sum;
  }
}

say $lf[^10].join(", ");

[1] Instead of rewriting the loop, we can just insert the initial zero like this.

Running it gives the expected result:

$ ./left-factorials-loop-cached-one 
1, 2, 4, 10, 34, 154, 874, 5914, 46234, 409114

$ ./left-factorials-loop-cached-one -z
0, 1, 2, 4, 10, 34, 154, 874, 5914, 46234

We can actually do this with a proper Raku sequence, which is very compact:

#! /usr/bin/env raku

unit sub MAIN (:c(:$count) = 10);

my $lf := ( 0, 1, ( * + ([*] 1 .. ++$) ) ... Inf );
# ######## [1] [2] [3] ################# [4] #####

say $lf[^$count].join(", ");

[1] The first value is 0.

[2] The second value is 1.

[3] Then a rule for all the values following the first two. Start with the previous value in the sequence (the first *), and add it to the expression after the plus sign. That expression is the faculty function applied to $, which is an anonymous state variable (that pops into existence when we use it, and keeps the value between calls).

See docs.raku.org/syntax/$ for more information about the anonymous state variable $.

[4] Go on indefinitely.

The result is as expected:

$ ./left-factorials-seq-zero
0, 1, 2, 4, 10, 34, 154, 874, 5914, 46234

The non-zero version is a little bit trickier:

#! /usr/bin/env raku

unit sub MAIN (:c(:$count) = 10);

my $lf := ( $ = 1, ( * + ([*] 1 .. ++$) ) ... Inf ); # [1]

say $lf[^$count].join(", ");

[1] This time we skip the initial zero in the sequence, but we have to initialise the state variable to 1 (which is also the first value, as it is returned from the assignment), so that it starts with the correct index value.

All is well:

$ ./left-factorials-seq-zero
0, 1, 2, 4, 10, 34, 154, 874, 5914, 46234

$ ./left-factorials-seq-zero -c=12
0, 1, 2, 4, 10, 34, 154, 874, 5914, 46234, 409114, 4037914

Challenge #153.2: Factorions

Input: $n = 145
Output: 1

    Since 1! + 4! + 5! => 1 + 24 + 120 = 145

Input: $n = 123
Output: 0

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

Let us go for a compact version:

#! /usr/bin/env raku

unit sub MAIN (Int $n where $n > 0);               # [1]

say + ($n.comb.map({ [*] (1 .. $_) }).sum == $n);  # [2]

[1] Ensure a natural number, i.e. a positive integer.

[2] We use comb to get a list of digits, then map to apply the faculty function (as shown in the first part of the challenge) on them. Then we add them together (with sum) and compare the result with the initial number. The result of this comparison is a Boolean value, so we coerce it to an integer (True => 1, False => 0) with the Numeric Coercion Prefix Operator + (that has a very impressive (as in long) name, especially compared with the single character of the operator itself).

See docs.raku.org/routine/+ for more information about the Numeric Coercion Prefix Operator +.

Running it:

$ ./factorions 145
1

$ ./factorions 123
0

Ok.

Let us have a go at the Factorion Sequence:

#! /usr/bin/env raku

unit sub MAIN (:c(:$count) = 10);

my $fs := ( my $i = 1,
            { (++$i).comb.map({ [*] (1 .. $_) }).sum == $i ?? $i !! next } [1]
            ... Inf
          );

say $fs[^$count].join(", ");

[1] Note the next inside the rule (as map is a loop in disguise), instead of the more intuitive grep on the outside. This is necessary, as grep will coerce whatever it is used on to a list. Expanding an eternal sequence is not a good idea.

Also note the ternary operator ?? and !! instead of a full blown if and else.

See docs.raku.org/routine/grep for more information about grep.

See docs.raku.org/language/operators#index-entry-operator_ternary for more information about the ternary operator ?? / !!.

Running it:

$ ./factorion-seq
^C    

It hangs.

Looking it up (at mathworld.wolfram.com/Factorion.html) tells us that there are only 4 values, so the program happily goes on to infinity searching for the default 10 values. (Well, it tries to. Infinity is not reachable.)

This is the four values:

$ ./factorion-seq -c=4
1, 2, 145, 40585

And that's it.