RogerBW's Blog

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.