Home primes

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)