I’ve been doing the Weekly
Challenges. The
latest
involved more furkling about with prime numbers. (Note that this is
open until 12 June 2022.)
Task 1: Perrin Prime
The Perrin sequence is defined to start with [3, 0, 2]; after that,
term N is the sum of terms N-2 and N-3. (So it continues 3, 2, 5, 5,
7, ….)
A Perrin prime is a number in the Perrin sequence which is also a
prime number.
Calculate the first 13 Perrin Primes.
Perrin pseudo-primes have some interesting properties, but take a
while to find – and Perl's Math::Prime::Util
already has optimised
code for finding them. Which is why I proposed this one instead.
There are various fiddly ways of generating arbitrary terms in the
sequence, but since I want the whole sequence anyway I don't bother.
The output numbers won't be in order and may have duplicates, so I
store the results in a set. Ruby:
def perrinprime(n)
out = Set.new
seq = [3, 0, 2]
while true do
Roll the sequence.
seq.push(seq[0] + seq[1])
seq.shift
Prime-test and store.
if seq[-1].prime? then
out.add(seq[-1])
if out.length >= n then
break
end
end
end
return out.to_a.sort
end
(For other languages I have a primality tester from earlier
challenges.)
Task 2:
You are given an integer greater than 1.
Write a script to find the home prime of the given number.
The home prime HP(n) of an integer n greater than 1 is the prime
number obtained by repeatedly factoring the increasing concatenation
of prime factors including repetitions.
In other words, to calculate HP(10) we run through:
primefactors(10) = (2, 5) → 25
primefactors(25) = (5, 5) → 55
primefactors(55) = (5, 11) → 511
primefactors(511) = (7, 73) → 773
primefactors(773) = (773)
(If I wanted a whole sequence of these, I'd build up a map as I did in
task 164.2 "Happy Numbers" – all of these numbers (10, 25, 55, 511,
773) would have the same home prime of 773.)
I already have prime factorisation code from earlier challenges, so
I'll re-use that. Raku:
sub homeprime($n0) {
my $n = $n0;
while (True) {
Get the prime factors.
my $t = primefactor($n);
If there was only one prime factor and its exponent is 1, the result
is prime; exit.
if ($t.elems == 1 && $t.values.max() == 1) {
last;
}
Otherwise, build up a string concatenation of the prime factors.
my $ns = '';
for ($t.keys.sort({ $^a <=> $^b })) -> $d {
for (1..$t{$d}) {
$ns ~= $d;
}
}
And convert it back into a number. (Other languages get this done
explicitly; in Raku, Perl and Lua they just sort of slurp across as
needed.)
$n = 0 + $ns;
}
return $n;
}
Full code on
github.
Comments on this post are now closed. If you have particular grounds for adding a late comment, comment on a more recent post quoting the URL of this one.