Peter
Peter Campbell Smith

Fun with primes

Weekly challenge 168 — 6 June 2022

Week 168: 6 Jun 2022

Task 2

Task — Home prime

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

In number theory, 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. Further information can be found on Wikipedia and OEIS.

Examples


Example 1:
As given in the Wikipedia page:
HP(10) = 773, as 10 factors as 2×5 yielding 
HP10(1) = 25, 25 factors as 5×5 yielding 
HP10(2) = HP25(1) = 55, 55 = 5×11 implies 
HP10(3) = HP25(2) = HP55(1) = 511, and 511 = 7×73 gives 
HP10(4) = HP25(3) = HP55(2) = HP511(1) = 773, 
a prime number.

Analysis

The home prime $HP(n) of an integer $n is obtained by concatenating its prime factors (in ascending order) to form a new number and then repeating this process until the result is prime. Perl is good at switching between the binary and character representation of a number as the context demands, so if we are allowed factor() and is_prime() from Math::Util this task is fairly trivial using recursion.

This works in microseconds up to the 48th home prime, but the 49th is apparently yet to be solved.

Script


#!/usr/bin/perl

# Peter Campbell Smith - 2022-06-06
# PWC 168 task 2

use v5.28;
use strict;
use warnings;
use utf8;
use Math::Prime::Util qw[factor is_prime];

my ($test, $hp);

# loop over 2 to 48 (49 is known to be difficult!)
for $test (2 .. 48) {
    $hp = home($test);
    say qq[hp($test) = $hp];
}

sub home {
    
    my (@prime_factors, $concat);
    
    # get prime factors
    @prime_factors = factor(shift);
    
    # concatenate them
    $concat .= $_ for @prime_factors;
    
    # either we have an answer or need to go round again
    return $concat if is_prime($concat);
    home($concat);
}

Output


hp(2) = 2
hp(3) = 3
hp(4) = 211
hp(5) = 5
hp(6) = 23
hp(7) = 7
hp(8) = 3331113965338635107
hp(9) = 311
hp(10) = 773
hp(11) = 11
hp(12) = 223
hp(13) = 13
hp(14) = 13367
hp(15) = 1129
hp(16) = 31636373
hp(17) = 17
hp(18) = 233
hp(19) = 19
hp(20) = 3318308475676071413
hp(21) = 37
hp(22) = 211
hp(23) = 23
hp(24) = 331319
hp(25) = 773
hp(26) = 3251
hp(27) = 13367
hp(28) = 227
hp(29) = 29
hp(30) = 547
hp(31) = 31
hp(32) = 241271
hp(33) = 311
hp(34) = 31397
hp(35) = 1129
hp(36) = 71129
hp(37) = 37
hp(38) = 373
hp(39) = 313
hp(40) = 3314192745739
hp(41) = 41
hp(42) = 379
hp(43) = 43
hp(44) = 22815088913
hp(45) = 3411949
hp(46) = 223
hp(47) = 47
hp(48) = 6161791591356884791277

 

Any content of this website which has been created by Peter Campbell Smith is in the public domain