Perl Weekly Challenge: Week 155
Challenge 1:
Fortunate Numbers
Write a script to produce first
8 Fortunate Numbers(unique and sorted).
According to Wikipedia
A Fortunate number, named after Reo Fortune, is the smallest integer m > 1 such that, for a given positive integer n, pn# + m is a prime number, where the primorial pn# is the product of the first n prime numbers.
Expected Output
3, 5, 7, 13, 17, 19, 23, 37
This is my Raku solution:
First we set up an array to hold the results.
my @fortunates;
Then we loop until we have the full set of 8 results we want.
my $i = 0;
while @fortunates.elems < 8 {
The primorials mentioned in the spec are generated by a lazy list of integers from
2 onwards. From this list, we grep an amount of prime numbers using .is-prime()
equal to n (though for some reason I named the variable $i instead of $n.) These
primes are multiplied together using the [*] operator.
my $pn = [*] (2 ... ∞).grep({ .is-prime; })[0 .. $i++];
Now from $pn + 2 we begin counting upwards. 2 because the next number after a prime
cannot be prime except for the case of 2 and 3.
for $pn + 2 .. ∞ -> $m {
If this number, $m is prime and the difference between it and $pn hasn't already
been included in our results...
if ($m.is-prime && $m - $pn ∉ @fortunates) {
...we add the difference to the results and break the loop so we can find the next fortunate number.
@fortunates.push($m - $pn);
last;
}
}
}
Finally, all that needs to be done is to print out the results.
@fortunates.sort.join(q{, }).say;
The Perl version works the same way for the most part except I had to re-use my trusty
isPrime() and nextPrime() functions from previous challenges.
my @fortunates;
my $i = 0;
while (scalar @fortunates < 8) {
my $pn = nextPrime(1);
And I made up for a lack of [*] by multiplying in a loop.
for my $j (1 .. $i++) {
$pn *= nextPrime();
}
my $m = $pn + 1;
while($m++) {
if (isPrime($m) && !grep { $_ == $m - $pn } @fortunates) {
push @fortunates, $m - $pn;
last;
}
}
}
say join q{, }, sort {$a <=> $b} @fortunates;
Challenge 2:
Pisano Period
Write a script to find the period of the
3rd Pisano Period.In number theory, the nth Pisano period, written as π(n), is the period with which the sequence of Fibonacci numbers taken modulo n repeats.
The Fibonacci numbers are the numbers in the integer sequence:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, ...
For any integer n, the sequence of Fibonacci numbers F(i) taken modulo n is periodic. The Pisano period, denoted π(n), is the value of the period of this sequence. For example, the sequence of Fibonacci numbers modulo 3 begins:
0, 1, 1, 2, 0, 2, 2, 1,
0, 1, 1, 2, 0, 2, 2, 1,
0, 1, 1, 2, 0, 2, 2, 1, ...
This sequence has period 8, so π(3) = 8.
One of the things I love about Raku is the complete unicode support which lets you
do things like name a subroutine π.
This lets us be really expressive. The solution looks like this:
say π(3);
How cool is that!?
The actual π() is shown below. It takes a number $n (In hindsight I should have explicitly
made it an Int) which is the Pisano period we are calculating. (Last week Padua and this week
Pisa; where in Italy will the weekly challenge take us next?)
sub π($n) {
We need fibonacci numbers. The line below creates them efficiently as a lazy sequence.
my @fibs = 0, 1, -> $a, $b { $a + $b} ... ∞;
Now we grow a list of moduli (moduluses?) of fibonacci numbers two at a time so we can evenly divide it into two halves.
my $i = 2;
loop {
my @moduli = @fibs[0 ..^ $i].map({ $_ mod $n; });
The two halves are compared using a combination of Z== and .all(). I keep forgetting that
Raku has an eqv operator does the same thing in a more readable fashion. Oh well, this works too.
if (@moduli[0 ..^ $i / 2] Z== @moduli[$i / 2 .. *]).all {
If the two halves are the same, we have a recurring sequence. The length of a half, which is the Pisano period, is returned.
return $i / 2;
}
$i += 2;
}
}
In the Perl version, I generated Fibonacci numbers using a recursive function like this:
sub fibonacci {
my ($n) = @_;
if ($n <= 1) {
return $n;
}
return fibonacci($n - 1) + fibonacci($n - 2);
}
and it worked well enough for $n = 3 which is all the spec asks for. However just
to see if my code was working correctly, I calculated all the first 10 Pisano periods.
I found that the code got really slow for $n > 4. I pulled the plug on $n == 10
when it looked like it would never finis. This is because a recursive function
has to keep calculating intermediate results over and over again. An easy solution
for this problem is to use Memoize; and add this line of code:
memoize('fibonacci');
The Memoize module caches intermediate results giving fibonacci() a tremendous
speedup, though by $n = 10, it was starting to bog down a little. Atleast it finished though.
I noticed Raku could calculate even the 10th Pisano period with ease. I wonder what it is doing behind the scenes to be so fast?
Perl is more limited in characters that can be used as identifiers unless you use utf8; which
I always forget to do so I gave the function the boring name pisano() instead.
sub pisano {
my ($n) = @_;
my $i = 2;
while (1) {
my @moduli = map { fibonacci($_) % $n; } 0 .. $i -1;
In Perl also, I try to detect a recurring sequence by comparing two halves of an array.
This time however, the comparison is done using the smartmatch operator ~~. Although
it has been around for a long time, ~~ is still considered experimental so you have to
add no warnings 'experimental'; to avoid an annoying warning message.
if (@moduli[0 .. $i / 2 - 1] ~~ @moduli[$i / 2 .. $#moduli]) {
return $i / 2;
}
$i += 2;
}
}
say pisano(3);