# RabbitFarm

### 2022-06-12

#### Take the Long Way Home

*The examples used here are from the weekly challenge problem statement and demonstrate
the working solution.*

## Part 1

*Calculate the first 13 Perrin Primes.*

### Solution

```
use strict;
use warnings;
use boolean;
use Math::Primality qw/is_prime/;
sub n_perrin_prime_r{
my($n, $perrins, $perrin_primes) = @_;
return $perrin_primes if keys %{$perrin_primes} == $n;
my $perrin = $perrins->[@{$perrins} - 3] + $perrins->[@{$perrins} - 2];
push @{$perrins}, $perrin;
$perrin_primes->{$perrin} = -1 if is_prime($perrin);
n_perrin_prime_r($n, $perrins, $perrin_primes);
}
sub perrin_primes{
return n_perrin_prime_r(13, [3, 0, 2], {});
}
MAIN:{
print join(", ", sort {$a <=> $b} keys %{perrin_primes()}) . "\n";
}
```

### Sample Run

```
$ perl perl/ch-1.pl
2, 3, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, 1442968193, 792606555396977
```

### Notes

The solution here incorporated a lot of elements from previous weekly challenges. That is
to say it is quite familiar, we recursively generate the sequence which is stored as hash
keys and, once completed, sort and print the results. The hash keys are a convenient,
although perhaps slightly bulky, way of handling the repeated `5`

term at the beginning.
The terms strictly increase thereafter.

## Part 2

*You are given an integer greater than 1. Write a script to find the home prime of the
given number.*

### Solution

```
use strict;
use warnings;
use bigint;
use Math::Primality qw/is_prime/;
sub prime_factor{
my $x = shift(@_);
my @factors;
for (my $y = 2; $y <= $x; $y++){
next if $x % $y;
$x /= $y;
push @factors, $y;
redo;
}
return @factors;
}
sub home_prime{
my($n) = @_;
return $n if is_prime($n);
my $s = $n;
{
$s = join("", prime_factor($s));
redo if !is_prime($s);
}
return $s;
}
MAIN:{
print home_prime(10) . "\n";
print home_prime(16) . "\n";
}
```

### Sample Run

```
$ perl perl/ch-2.pl
773
31636373
```

### Notes

*So you think eight is low*

*Calculating HP(8) should be an easy go*

*Take the long way home*

*Take the long way home*

The second part of this week's challenge was a lot of fun as it presented some unexpected
behavior. Here we are asked to compute the *Home Prime* of any given number. The process
for doing so is, given `N`

to take the prime factors for `N`

and concatenate them
together. If the result is prime then we are done, that is the *Home Prime* of `N`

,
typically written `HP(N)`

. This is an easy process to repeat, and in many cases the
computation is a very quick one. However, in some cases, the size of the interim numbers
on the path to HP(N) grow extremely large and the computation bogs down, whence *take the
long way home*! As an example, the computation of HP(8) is still running after 24 hours
on my M1 Mac Mini.

## References

posted at: 23:34 by: Adam Russell | path: /perl | permanent link to this entry

The Weekly Challenge 168 (Prolog Solutions)

*The examples used here are from the weekly challenge problem statement and demonstrate
the working solution.*

## Part 1

*Calculate the first 13 Perrin Primes.*

### Solution

```
perrin_primes(A, B, C) --> {D is B + A, fd_not_prime(D)},
perrin_primes(B, C, D).
perrin_primes(A, B, C) --> {D is B + A, fd_prime(D), D \== C},
[D], perrin_primes(B, C, D).
perrin_primes(A, B, C) --> {D is B + A, fd_prime(D), D == C},
[], perrin_primes(B, C, D).
perrin_primes(_, _, _) --> [], !.
n_perrin_primes(N, PerrinPrimes):-
length(PerrinPrimes, N),
phrase(perrin_primes(3, 0, 2), PerrinPrimes).
```

### Sample Run

```
$ gprolog --consult-file prolog/ch-1.p
| ?- n_perrin_primes(13, PerrinPrimes).
PerrinPrimes = [3,2,5,7,17,29,277,367,853,14197,43721,1442968193,792606555396977] ?
```

### Notes

This is a pretty cut and dry use of a DCG to generate this interesting mathematical
sequence. A couple of things that stand out are (1) the condition that `D \== C`

which is
to remove the duplicate `5`

which occurs naturally at the beginning of the sequence.
Afterwards all of the terms strictly increase. Also, (2) although the first two terms are
indeed `3, 2`

it is a convention to sort these and present them as `2, 3`

although I did
not happen to do so here.

## Part 2

*You are given an integer greater than 1. Write a script to find the home prime of the
given number.*

### Solution

```
prime_factors(N, L):-
N > 0,
prime_factors(N, L, 2).
prime_factors(1, [], _):-
!.
prime_factors(N, [F|L], F):-
R is N // F,
N =:= R * F,
!,
prime_factors(R, L, F).
prime_factors(N, L, F):-
next_factor(N, F, NF),
prime_factors(N, L, NF).
next_factor(_, 2, 3):-
!.
next_factor(N, F, NF):-
F * F < N,
!,
NF is F + 2.
next_factor(N, _, N).
factor_concat(Factors, Atom):-
factor_concat(Factors, '', Atom).
factor_concat([], Atom, Atom).
factor_concat([H|T], AtomAccum, Atom):-
number_atom(H, A),
atom_concat(AtomAccum, A, UpdatedAtomAccum),
factor_concat(T, UpdatedAtomAccum, Atom).
home_prime(N, HomePrime):-
prime_factors(N, Factors),
factor_concat(Factors, A),
number_atom(Number, A),
fd_not_prime(Number),
home_prime(Number, HomePrime).
home_prime(N, HomePrime):-
prime_factors(N, Factors),
factor_concat(Factors, A),
number_atom(Number, A),
fd_prime(Number),
HomePrime = Number.
```

### Sample Run

```
$ gprolog --consult-file prolog/ch-2.p
| ?- home_prime(16, HomePrime).
HomePrime = 31636373 ?
(4 ms) yes
| ?- home_prime(54, HomePrime).
HomePrime = 2333 ?
(1 ms) yes
| ?- home_prime(108, HomePrime).
HomePrime = 23971 ?
yes
```

### Notes

Here we are asked to compute the *Home Prime* of any given number. The process
for doing so is, given `N`

to take the prime factors for `N`

and concatenate them
together. If the result is prime then we are done, that is the *Home Prime* of `N`

,
typically written `HP(N)`

. This is an easy process to repeat, and in many cases the
computation is a very quick one. However, in some cases, the size of the interim numbers
on the path to HP(N) grow extremely large and the computation bogs down. I have used the
prime factorization code here in several other weekly challenges and it is quite
performant but even this runs rather slowly as we are faced with extremely large numbers.

## References

posted at: 19:21 by: Adam Russell | path: /prolog | permanent link to this entry