Home primes
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.
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) |
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
Factor
<lang factor>USING: formatting kernel make math math.parser math.primes math.primes.factors math.ranges present prettyprint sequences sequences.extras ;
- squish ( seq -- n ) [ present ] map-concat dec> ;
- next ( m -- n ) factors squish ; inline
- (chain) ( n -- ) [ dup prime? ] [ dup , next ] until , ;
- chain ( n -- seq ) [ (chain) ] { } make ;
- prime. ( n -- ) dup "HP%d = %d\n" printf ;
- setup ( seq -- n s r ) unclip-last swap dup length 1 [a,b] ;
- multi. ( n -- ) chain setup [ "HP%d(%d) = " printf ] 2each . ;
- chain. ( n -- ) dup prime? [ prime. ] [ multi. ] if ;
2 20 [a,b] [ chain. ] each</lang>
- Output:
HP2 = 2 HP3 = 3 HP4(2) = HP22(1) = 211 HP5 = 5 HP6(1) = 23 HP7 = 7 HP8(13) = HP222(12) = HP2337(11) = HP31941(10) = HP33371313(9) = HP311123771(8) = HP7149317941(7) = HP22931219729(6) = HP112084656339(5) = HP3347911118189(4) = HP11613496501723(3) = HP97130517917327(2) = HP531832651281459(1) = 3331113965338635107 HP9(2) = HP33(1) = 311 HP10(4) = HP25(3) = HP55(2) = HP511(1) = 773 HP11 = 11 HP12(1) = 223 HP13 = 13 HP14(5) = HP27(4) = HP333(3) = HP3337(2) = HP4771(1) = 13367 HP15(4) = HP35(3) = HP57(2) = HP319(1) = 1129 HP16(4) = HP2222(3) = HP211101(2) = HP3116397(1) = 31636373 HP17 = 17 HP18(1) = 233 HP19 = 19 HP20(15) = HP225(14) = HP3355(13) = HP51161(12) = HP114651(11) = HP3312739(10) = HP17194867(9) = HP194122073(8) = HP709273797(7) = HP39713717791(6) = HP113610337981(5) = HP733914786213(4) = HP3333723311815403(3) = HP131723655857429041(2) = HP772688237874641409(1) = 3318308475676071413
J
<lang j>step =: -.&' '&.":@q: hseq =: [,$:@step`(0&$)@.(1&p:) fmtHP =: (' is prime',~":@])`('HP',":@],'(',":@[,')'&[)@.(*@[) fmtlist =: [:;@}.[:,(<' = ')&,"0@(|.@i.@# fmtHP each [) printHP =: 0 0&$@stdout@(fmtlist@hseq,(10{a.)&[) printHP"0 [ 2}.i.21 exit 0</lang>
- Output:
2 is prime 3 is prime HP4(2) = HP22(1) = 211 is prime 5 is prime HP6(1) = 23 is prime 7 is prime HP8(13) = HP222(12) = HP2337(11) = HP31941(10) = HP33371313(9) = HP311123771(8) = HP7149317941(7) = HP22931219729(6) = HP112084656339(5) = HP3347911118189(4) = HP11613496501723(3) = HP97130517917327(2) = HP531832651281459(1) = 3331113965338635107 is prime HP9(2) = HP33(1) = 311 is prime HP10(4) = HP25(3) = HP55(2) = HP511(1) = 773 is prime 11 is prime HP12(1) = 223 is prime 13 is prime HP14(5) = HP27(4) = HP333(3) = HP3337(2) = HP4771(1) = 13367 is prime HP15(4) = HP35(3) = HP57(2) = HP319(1) = 1129 is prime HP16(4) = HP2222(3) = HP211101(2) = HP3116397(1) = 31636373 is prime 17 is prime HP18(1) = 233 is prime 19 is prime HP20(15) = HP225(14) = HP3355(13) = HP51161(12) = HP114651(11) = HP3312739(10) = HP17194867(9) = HP194122073(8) = HP709273797(7) = HP39713717791(6) = HP113610337981(5) = HP733914786213(4) = HP3333723311815403(3) = HP131723655857429041(2) = HP772688237874641409(1) = 3318308475676071413 is prime
Julia
<lang julia>using Primes
function homeprimechain(n::BigInt)
isprime(n) && return [n] concat = prod(string(i)^j for (i, j) in factor(n).pe) return pushfirst!(homeprimechain(parse(BigInt, concat)), n)
end homeprimechain(n::Integer) = homeprimechain(BigInt(n))
function printHPiter(n, numperline = 4)
chain = homeprimechain(n) len = length(chain) for (i, ent) in enumerate(chain) print(i < len ? "HP$ent" * "($(len - i)) = " * (i % numperline == 0 ? "\n" : "") : "$ent is prime.\n\n") end
end
for i in [2:20; 65]
print("Home Prime chain for $i: ") printHPiter(i)
end
</lang>
- Output:
Home Prime chain for 2: 2 is prime. Home Prime chain for 3: 3 is prime. Home Prime chain for 4: HP4(2) = HP22(1) = 211 is prime. Home Prime chain for 5: 5 is prime. Home Prime chain for 6: HP6(1) = 23 is prime. Home Prime chain for 7: 7 is prime. Home Prime chain for 8: HP8(13) = HP222(12) = HP2337(11) = HP31941(10) = HP33371313(9) = HP311123771(8) = HP7149317941(7) = HP22931219729(6) = HP112084656339(5) = HP3347911118189(4) = HP11613496501723(3) = HP97130517917327(2) = HP531832651281459(1) = 3331113965338635107 is prime. Home Prime chain for 9: HP9(2) = HP33(1) = 311 is prime. Home Prime chain for 10: HP10(4) = HP25(3) = HP55(2) = HP511(1) = 773 is prime. Home Prime chain for 11: 11 is prime. Home Prime chain for 12: HP12(1) = 223 is prime. Home Prime chain for 13: 13 is prime. Home Prime chain for 14: HP14(5) = HP27(4) = HP333(3) = HP3337(2) = HP4771(1) = 13367 is prime. Home Prime chain for 15: HP15(4) = HP35(3) = HP57(2) = HP319(1) = 1129 is prime. Home Prime chain for 16: HP16(4) = HP2222(3) = HP211101(2) = HP3116397(1) = 31636373 is prime. Home Prime chain for 17: 17 is prime. Home Prime chain for 18: HP18(1) = 233 is prime. Home Prime chain for 19: 19 is prime. Home Prime chain for 20: HP20(15) = HP225(14) = HP3355(13) = HP51161(12) = HP114651(11) = HP3312739(10) = HP17194867(9) = HP194122073(8) = HP709273797(7) = HP39713717791(6) = HP113610337981(5) = HP733914786213(4) = HP3333723311815403(3) = HP131723655857429041(2) = HP772688237874641409(1) = 3318308475676071413 is prime. Home Prime chain for 65: HP65(19) = HP513(18) = HP33319(17) = HP1113233(16) = HP11101203(15) = HP332353629(14) = HP33152324247(13) = HP3337473732109(12) = HP111801316843763(11) = HP151740406071813(10) = HP31313548335458223(9) = HP3397179373752371411(8) = HP157116011350675311441(7) = HP331333391143947279384649(6) = HP11232040692636417517893491(5) = HP711175663983039633268945697(4) = HP292951656531350398312122544283(3) = HP2283450603791282934064985326977(2) = HP333297925330304453879367290955541(1) = 1381321118321175157763339900357651 is prime.
Nim
This algorithm is really efficient. We get the result for HP2 to HP20 in about 6 ms and adding HP65 in 1.3 s. I think that the threshold to switch to Pollard-Rho is very important. <lang Nim>import algorithm, sequtils, strformat, strutils import bignum
let
Two = newInt(2) Three = newInt(3) Five = newInt(5)
proc primeFactorsWheel(n: Int): seq[Int] =
const Inc = [4, 2, 4, 2, 4, 6, 2, 6] var n = n while (n mod 2).isZero: result.add Two n = n div 2 while (n mod 3).isZero: result.add Three n = n div 3 while (n mod 5).isZero: result.add Five n = n div 5 var k = 7 var i = 0 while k * k <= n: if (n mod k).isZero: result.add newInt(k) n = n div k else: inc k, Inc[i] i = (i + 1) and 7 if n > 1: result.add n
func pollardRho(n : Int): Int =
func g(x, y: Int): Int = (x * x + 1) mod y
var x, y = newInt(2) var z, d = newInt(1) var count = 0 while true: x = g(x, n) y = g(g(y, n), n) d = abs(x - y) mod n z *= d inc count if count == 100: d = gcd(z, n) if d != 1: break z = newInt(1) count = 0 if d == n: return newInt(0) result = d
proc primeFactors(n: Int): seq[Int] =
var n = n while n > 1: if n > 100_000_000: let d = pollardRho(n) if not d.isZero: result.add primeFactorsWheel(d) n = n div d if n.probablyPrime(25) != 0: result.add n break else: result.add primeFactorsWheel(n) break else: result.add primeFactorsWheel(n) break result.sort()
let list = toSeq(2..20) & 65
for i in list:
if i in [2, 3, 5, 7, 11, 13, 17, 19]: echo &"HP{i} = {i}" continue var n = 1 var j = newInt(i) var h = @[j] while true: j = newInt(primeFactors(j).join()) h.add j if j.probablyPrime(25) != 0: for k in countdown(n, 1): stdout.write &"HP{h[n-k]}({k}) = " echo h[n] break else: inc n</lang>
- Output:
HP2 = 2 HP3 = 3 HP4(2) = HP22(1) = 211 HP5 = 5 HP6(1) = 23 HP7 = 7 HP8(13) = HP222(12) = HP2337(11) = HP31941(10) = HP33371313(9) = HP311123771(8) = HP7149317941(7) = HP22931219729(6) = HP112084656339(5) = HP3347911118189(4) = HP11613496501723(3) = HP97130517917327(2) = HP531832651281459(1) = 3331113965338635107 HP9(2) = HP33(1) = 311 HP10(4) = HP25(3) = HP55(2) = HP511(1) = 773 HP11 = 11 HP12(1) = 223 HP13 = 13 HP14(5) = HP27(4) = HP333(3) = HP3337(2) = HP4771(1) = 13367 HP15(4) = HP35(3) = HP57(2) = HP319(1) = 1129 HP16(4) = HP2222(3) = HP211101(2) = HP3116397(1) = 31636373 HP17 = 17 HP18(1) = 233 HP19 = 19 HP20(15) = HP225(14) = HP3355(13) = HP51161(12) = HP114651(11) = HP3312739(10) = HP17194867(9) = HP194122073(8) = HP709273797(7) = HP39713717791(6) = HP113610337981(5) = HP733914786213(4) = HP3333723311815403(3) = HP131723655857429041(2) = HP772688237874641409(1) = 3318308475676071413 HP65(19) = HP513(18) = HP33319(17) = HP1113233(16) = HP11101203(15) = HP332353629(14) = HP33152324247(13) = HP3337473732109(12) = HP111801316843763(11) = HP151740406071813(10) = HP31313548335458223(9) = HP3397179373752371411(8) = HP157116011350675311441(7) = HP331333391143947279384649(6) = HP11232040692636417517893491(5) = HP711175663983039633268945697(4) = HP292951656531350398312122544283(3) = HP2283450603791282934064985326977(2) = HP333297925330304453879367290955541(1) = 1381321118321175157763339900357651
Perl
<lang perl>use strict; use warnings; use ntheory 'factor';
for my $m (2..20, 65) {
my (@steps, @factors) = $m; push @steps, join '_', @factors while (@factors = factor $steps[-1] =~ s/_//gr) > 1; my $step = $#steps; if ($step >= 1) { print 'HP' . $_ . "($step) = " and --$step or last for @steps } else { print "HP$m = " } print "$steps[-1]\n";
}</lang>
- Output:
HP2 = 2 HP3 = 3 HP4(2) = HP2_2(1) = 2_11 HP5 = 5 HP6(1) = 2_3 HP7 = 7 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 HP9(2) = HP3_3(1) = 3_11 HP10(4) = HP2_5(3) = HP5_5(2) = HP5_11(1) = 7_73 HP11 = 11 HP12(1) = 2_2_3 HP13 = 13 HP14(5) = HP2_7(4) = HP3_3_3(3) = HP3_3_37(2) = HP47_71(1) = 13_367 HP15(4) = HP3_5(3) = HP5_7(2) = HP3_19(1) = 11_29 HP16(4) = HP2_2_2_2(3) = HP2_11_101(2) = HP3_11_6397(1) = 3_163_6373 HP17 = 17 HP18(1) = 2_3_3 HP19 = 19 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 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
Phix
Added a new mpz_pollard_rho routine, based on the wp:Pollard's_rho_algorithm C code.
with javascript_semantics requires("1.0.0") include mpfr.e procedure test(integer n) string s = sprintf("%d",n), lastp = "" sequence res = {s} atom t0 = time() while true do s = substitute(s,"_","") sequence rr = mpz_pollard_rho(s,true) if length(rr)=1 then exit end if s = join(rr,"_") res = append(res,s) end while atom t = time()-t0 integer niter = length(res)-1 string iter = iff(niter>1?sprintf("(%d)",niter):""), e = iff(t>0.1?" ["&elapsed(t)&"]":"") s = sprintf("HP%d%s = ",{n,iter}) if niter=0 then printf(1,"%s%d %s\n",{s,n,e}) else for i=2 to niter do niter -= 1 printf(1,"%sHP%s(%d)\n",{s,res[i],niter}) if i=2 then s = repeat(' ',length(s)) s[-2] = '=' end if end for printf(1,"%s%s %s\n",{s,res[$],e}) end if end procedure papply(tagset(20,2)&65,test)
- Output:
Using underscores to show the individual factors that were concatenated together
HP2 = 2 HP3 = 3 HP4(2) = HP2_2(1) = 2_11 HP5 = 5 HP6 = 2_3 HP7 = 7 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 HP9(2) = HP3_3(1) = 3_11 HP10(4) = HP2_5(3) = HP5_5(2) = HP5_11(1) = 7_73 HP11 = 11 HP12 = 2_2_3 HP13 = 13 HP14(5) = HP2_7(4) = HP3_3_3(3) = HP3_3_37(2) = HP47_71(1) = 13_367 HP15(4) = HP3_5(3) = HP5_7(2) = HP3_19(1) = 11_29 HP16(4) = HP2_2_2_2(3) = HP2_11_101(2) = HP3_11_6397(1) = 3_163_6373 HP17 = 17 HP18 = 2_3_3 HP19 = 19 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 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 [13.9s]
Raku
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.
<lang perl6>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;
}</lang>
- 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)
Wren
This uses a combination of the Pollard Rho algorithm and wheel based factorization to try and factorize the large numbers involved here in a reasonable time.
Reaches HP20 in about 0.52 seconds but HP65 took just under 40 minutes! <lang ecmascript>import "/math" for Int import "/big" for BigInt import "/sort" for Sort
// simple wheel based prime factors routine for BigInt var primeFactorsWheel = Fn.new { |n|
var inc = [4, 2, 4, 2, 4, 6, 2, 6] var factors = [] while (n%2 == 0) { factors.add(BigInt.two) n = n / 2 } while (n%3 == 0) { factors.add(BigInt.three) n = n / 3 } while (n%5 == 0) { factors.add(BigInt.five) n = n / 5 } var k = BigInt.new(7) var i = 0 while (k * k <= n) { if (n%k == 0) { factors.add(k) n = n / k } else { k = k + inc[i] i = (i + 1) % 8 } } if (n > 1) factors.add(n) return factors
}
var pollardRho = Fn.new { |n|
var g = Fn.new { |x, y| (x*x + BigInt.one) % n } var x = BigInt.two var y = BigInt.two var z = BigInt.one var d = BigInt.one var count = 0 while (true) { x = g.call(x, n) y = g.call(g.call(y, n), n) d = (x - y).abs % n z = z * d count = count + 1 if (count == 100) { d = BigInt.gcd(z, n) if (d != BigInt.one) break z = BigInt.one count = 0 } } if (d == n) return BigInt.zero return d
}
var primeFactors = Fn.new { |n|
var factors = [] while (n > 1) { if (n > BigInt.maxSmall/100) { var d = pollardRho.call(n) if (d != 0) { factors.addAll(primeFactorsWheel.call(d)) n = n / d if (n.isProbablePrime(2)) { factors.add(n) break } } else { factors.addAll(primeFactorsWheel.call(n)) break } } else { factors.addAll(primeFactorsWheel.call(n)) break } } Sort.insertion(factors) return factors
}
var list = (2..20).toList list.add(65) for (i in list) {
if (Int.isPrime(i)) { System.print("HP%(i) = %(i)") continue } var n = 1 var j = BigInt.new(i) var h = [j] while (true) { var k = primeFactors.call(j).reduce("") { |acc, f| acc + f.toString } j = BigInt.new(k) h.add(j) if (j.isProbablePrime(2)) { for (l in n...0) System.write("HP%(h[n-l])(%(l)) = ") System.print(h[n]) break } else { n = n + 1 } }
}</lang>
- Output:
HP2 = 2 HP3 = 3 HP4(2) = HP22(1) = 211 HP5 = 5 HP6(1) = 23 HP7 = 7 HP8(13) = HP222(12) = HP2337(11) = HP31941(10) = HP33371313(9) = HP311123771(8) = HP7149317941(7) = HP22931219729(6) = HP112084656339(5) = HP3347911118189(4) = HP11613496501723(3) = HP97130517917327(2) = HP531832651281459(1) = 3331113965338635107 HP9(2) = HP33(1) = 311 HP10(4) = HP25(3) = HP55(2) = HP511(1) = 773 HP11 = 11 HP12(1) = 223 HP13 = 13 HP14(5) = HP27(4) = HP333(3) = HP3337(2) = HP4771(1) = 13367 HP15(4) = HP35(3) = HP57(2) = HP319(1) = 1129 HP16(4) = HP2222(3) = HP211101(2) = HP3116397(1) = 31636373 HP17 = 17 HP18(1) = 233 HP19 = 19 HP20(15) = HP225(14) = HP3355(13) = HP51161(12) = HP114651(11) = HP3312739(10) = HP17194867(9) = HP194122073(8) = HP709273797(7) = HP39713717791(6) = HP113610337981(5) = HP733914786213(4) = HP3333723311815403(3) = HP131723655857429041(2) = HP772688237874641409(1) = 3318308475676071413 HP65(19) = HP513(18) = HP33319(17) = HP1113233(16) = HP11101203(15) = HP332353629(14) = HP33152324247(13) = HP3337473732109(12) = HP111801316843763(11) = HP151740406071813(10) = HP31313548335458223(9) = HP3397179373752371411(8) = HP157116011350675311441(7) = HP331333391143947279384649(6) = HP11232040692636417517893491(5) = HP711175663983039633268945697(4) = HP292951656531350398312122544283(3) = HP2283450603791282934064985326977(2) = HP333297925330304453879367290955541(1) = 1381321118321175157763339900357651