user
|  |
| --- |
| This page uses content from **Wikipedia**. The original article was at Home prime. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance) |

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.

The traditional notation has the prefix "HP" and a postfix count of the number of iterations until the home prime is found (if the count is greater than 0), for instance HP4(2) === HP22(1) === 211 is the same as saying the home prime of 4 needs 2 iterations and is the same as the home prime of 22 which needs 1 iteration, and (both) resolve to 211, a prime.

Prime numbers are their own home prime;

So:

```
   HP2 = 2
   
   HP7 = 7

```

If the integer obtained by concatenating increasing prime factors is not prime, iterate until you reach a prime number; the home prime.

```
   HP4(2) = HP22(1) = 211
   HP4(2) = 2 × 2 => 22; HP22(1) = 2 × 11 => 211; 211 is prime  
   
   HP10(4) = HP25(3) = HP55(2) = HP511(1) = 773
   HP10(4) = 2 × 5 => 25; HP25(3) = 5 × 5 => 55; HP55(2) = 5 × 11 => 511; HP511(1) = 7 × 73 => 773; 773 is prime  

```

Task

* Find and show here, on this page, the home prime iteration chains for the integers 2 through 20 inclusive.

Stretch goal

* Find and show the iteration chain for 65.

Impossible goal

* Show the the home prime for HP49.

See also

* OEIS:A037274 - Home primes for n >= 2 * OEIS:A056938 - Concatenation chain for HP49
assistant
Not the fastest, but not too bad either. Make an abortive attempt at HP49.

Assuming there are n steps; HP49(n - 25) is slow, HP49(n - 31) is *really* slow, and I gave up on HP49(n - 34) after 45 minutes.

Using Prime::Factor from the Raku ecosystem.

```
use Prime::Factor;

my $start = now;

(flat 2..20, 65).map: -> $m {
    my ($now, @steps, @factors) = now, $m;

    @steps.push: @factors.join('_') while (@factors = prime-factors @steps[*-1].Int) > 1;

    say (my $step = +@steps) > 1 ?? (@steps[0..*-2].map( { "HP$_\({--$step})" } ).join: ' = ') !! ("HP$m"),
      " = ", @steps[*-1], "  ({(now - $now).fmt("%0.3f")} seconds)";
}

say "Total elapsed time: {(now - $start).fmt("%0.3f")} seconds\n";

say 'HP49:';
my ($now, @steps, @factors) = now, 49;
my $step = 0;
while (@factors = prime-factors @steps[*-1].Int) > 1 {
    @steps.push: @factors.join('_');
    say "HP{@steps[$step].Int}\(n - {$step++}) = ", @steps[*-1], "  ({(now - $now).fmt("%0.3f")} seconds)";
    $now = now;
    last if $step > 30;
}

```

Output:

```
HP2 = 2  (0.000 seconds)
HP3 = 3  (0.000 seconds)
HP4(2) = HP2_2(1) = 2_11  (0.001 seconds)
HP5 = 5  (0.000 seconds)
HP6(1) = 2_3  (0.000 seconds)
HP7 = 7  (0.000 seconds)
HP8(13) = HP2_2_2(12) = HP2_3_37(11) = HP3_19_41(10) = HP3_3_3_7_13_13(9) = HP3_11123771(8) = HP7_149_317_941(7) = HP229_31219729(6) = HP11_2084656339(5) = HP3_347_911_118189(4) = HP11_613_496501723(3) = HP97_130517_917327(2) = HP53_1832651281459(1) = 3_3_3_11_139_653_3863_5107  (0.014 seconds)
HP9(2) = HP3_3(1) = 3_11  (0.000 seconds)
HP10(4) = HP2_5(3) = HP5_5(2) = HP5_11(1) = 7_73  (0.001 seconds)
HP11 = 11  (0.000 seconds)
HP12(1) = 2_2_3  (0.000 seconds)
HP13 = 13  (0.000 seconds)
HP14(5) = HP2_7(4) = HP3_3_3(3) = HP3_3_37(2) = HP47_71(1) = 13_367  (0.001 seconds)
HP15(4) = HP3_5(3) = HP5_7(2) = HP3_19(1) = 11_29  (0.001 seconds)
HP16(4) = HP2_2_2_2(3) = HP2_11_101(2) = HP3_11_6397(1) = 3_163_6373  (0.001 seconds)
HP17 = 17  (0.000 seconds)
HP18(1) = 2_3_3  (0.000 seconds)
HP19 = 19  (0.000 seconds)
HP20(15) = HP2_2_5(14) = HP3_3_5_5(13) = HP5_11_61(12) = HP11_4651(11) = HP3_3_12739(10) = HP17_194867(9) = HP19_41_22073(8) = HP709_273797(7) = HP3_97_137_17791(6) = HP11_3610337981(5) = HP7_3391_4786213(4) = HP3_3_3_3_7_23_31_1815403(3) = HP13_17_23_655857429041(2) = HP7_7_2688237874641409(1) = 3_31_8308475676071413  (0.020 seconds)
HP65(19) = HP5_13(18) = HP3_3_3_19(17) = HP11_13_233(16) = HP11_101203(15) = HP3_3_23_53629(14) = HP3_3_1523_24247(13) = HP3_3_3_7_47_3732109(12) = HP11_18013_16843763(11) = HP151_740406071813(10) = HP3_13_13_54833_5458223(9) = HP3_3_97_179_373_7523_71411(8) = HP1571_1601_1350675311441(7) = HP3_3_13_33391_143947_279384649(6) = HP11_23_204069263_6417517893491(5) = HP7_11_1756639_83039633268945697(4) = HP29_29_5165653_13503983_12122544283(3) = HP228345060379_1282934064985326977(2) = HP3_3_3_2979253_3030445387_9367290955541(1) = 1381_3211183211_75157763339900357651  (6.686 seconds)
Total elapsed time: 6.737 seconds

HP49:
HP49(n - 0) = 7_7  (0.000 seconds)
HP77(n - 1) = 7_11  (0.000 seconds)
HP711(n - 2) = 3_3_79  (0.000 seconds)
HP3379(n - 3) = 31_109  (0.000 seconds)
HP31109(n - 4) = 13_2393  (0.000 seconds)
HP132393(n - 5) = 3_44131  (0.000 seconds)
HP344131(n - 6) = 17_31_653  (0.000 seconds)
HP1731653(n - 7) = 7_11_43_523  (0.000 seconds)
HP71143523(n - 8) = 11_11_577_1019  (0.000 seconds)
HP11115771019(n - 9) = 311_35742029  (0.000 seconds)
HP31135742029(n - 10) = 7_17_261644891  (0.000 seconds)
HP717261644891(n - 11) = 11_19_3431873899  (0.002 seconds)
HP11193431873899(n - 12) = 11_613_4799_345907  (0.001 seconds)
HP116134799345907(n - 13) = 3_204751_189066719  (0.001 seconds)
HP3204751189066719(n - 14) = 3_1068250396355573  (0.003 seconds)
HP31068250396355573(n - 15) = 621611_49980213343  (0.005 seconds)
HP62161149980213343(n - 16) = 3_3_6906794442245927  (0.006 seconds)
HP336906794442245927(n - 17) = 73_4615161567701999  (0.009 seconds)
HP734615161567701999(n - 18) = 3_13_18836286194043641  (0.009 seconds)
HP31318836286194043641(n - 19) = 3_3_3_43_14369_161461_11627309  (0.004 seconds)
HP333431436916146111627309(n - 20) = 3_32057_1618455677_2142207827  (0.153 seconds)
HP33205716184556772142207827(n - 21) = 3_1367_2221_5573_475297_1376323127  (0.006 seconds)
HP31367222155734752971376323127(n - 22) = 7_3391_51263_25777821480557336017  (0.003 seconds)
HP733915126325777821480557336017(n - 23) = 47_67_347_431_120361987_12947236602187  (0.043 seconds)
HP476734743112036198712947236602187(n - 24) = 3_7_7_17_12809_57470909_57713323_4490256751  (0.124 seconds)
HP377171280957470909577133234490256751(n - 25) = 3096049809383_121823389214993262890297  (27.913 seconds)
HP3096049809383121823389214993262890297(n - 26) = 7_379_62363251_18712936424989555929478399  (0.132 seconds)
HP73796236325118712936424989555929478399(n - 27) = 13_1181_145261411_33089538087518197265265053  (0.034 seconds)
HP13118114526141133089538087518197265265053(n - 28) = 3_19_521_441731977174163487542111577539726749  (0.002 seconds)
HP319521441731977174163487542111577539726749(n - 29) = 59_5415617656474189392601483764603009147911  (0.002 seconds)
HP595415617656474189392601483764603009147911(n - 30) = 13_8423_1466957_3706744784027901056001426046777  (0.015 seconds)
```