Rosetta Code

Home primes: Difference between revisions

Page Discussion

Home primes (view source)

Revision as of 12:12, 8 March 2024

37,873 bytes added ,  2 months ago
added RPL
m (→‎{{header|Raku}}: oops, fencepost error)
(added RPL)
 
(25 intermediate revisions by 15 users not shown)
Line 1:
{{draft task|Prime Numbers}}
{{Wikipedia|Home prime}}
 
Line 47:
=={{header|Factor}}==
{{works with|Factor|0.99 2021-02-05}}
<langsyntaxhighlight lang="factor">USING: formatting kernel make math math.parser math.primes
math.primes.factors math.ranges present prettyprint sequences
sequences.extras ;
Line 67:
: chain. ( n -- ) dup prime? [ prime. ] [ multi. ] if ;
 
2 20 [a,b] [ chain. ] each</langsyntaxhighlight>
{{out}}
<pre>
Line 89:
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
</pre>
 
=={{header|Go}}==
{{trans|Wren}}
{{libheader|Go-rcu}}
<syntaxhighlight lang="go">package main
 
import (
"fmt"
"math/big"
"rcu"
"sort"
)
 
var zero = new(big.Int)
var one = big.NewInt(1)
var two = big.NewInt(2)
var three = big.NewInt(3)
var four = big.NewInt(4)
var five = big.NewInt(5)
var six = big.NewInt(6)
 
// simple wheel based prime factors routine for BigInt
func primeFactorsWheel(m *big.Int) []*big.Int {
n := new(big.Int).Set(m)
t := new(big.Int)
inc := []*big.Int{four, two, four, two, four, six, two, six}
var factors []*big.Int
for t.Rem(n, two).Cmp(zero) == 0 {
factors = append(factors, two)
n.Quo(n, two)
}
for t.Rem(n, three).Cmp(zero) == 0 {
factors = append(factors, three)
n.Quo(n, three)
}
for t.Rem(n, five).Cmp(zero) == 0 {
factors = append(factors, five)
n.Quo(n, five)
}
k := big.NewInt(7)
i := 0
for t.Mul(k, k).Cmp(n) <= 0 {
if t.Rem(n, k).Cmp(zero) == 0 {
factors = append(factors, new(big.Int).Set(k))
n.Quo(n, k)
} else {
k.Add(k, inc[i])
i = (i + 1) % 8
}
}
if n.Cmp(one) > 0 {
factors = append(factors, n)
}
return factors
}
 
func pollardRho(n *big.Int) *big.Int {
g := func(x, n *big.Int) *big.Int {
x2 := new(big.Int)
x2.Mul(x, x)
x2.Add(x2, one)
return x2.Mod(x2, n)
}
x, y, d := new(big.Int).Set(two), new(big.Int).Set(two), new(big.Int).Set(one)
t, z := new(big.Int), new(big.Int).Set(one)
count := 0
for {
x = g(x, n)
y = g(g(y, n), n)
t.Sub(x, y)
t.Abs(t)
t.Mod(t, n)
z.Mul(z, t)
count++
if count == 100 {
d.GCD(nil, nil, z, n)
if d.Cmp(one) != 0 {
break
}
z.Set(one)
count = 0
}
}
if d.Cmp(n) == 0 {
return new(big.Int)
}
return d
}
 
func primeFactors(m *big.Int) []*big.Int {
n := new(big.Int).Set(m)
var factors []*big.Int
lim := big.NewInt(1e9)
for n.Cmp(one) > 0 {
if n.Cmp(lim) > 0 {
d := pollardRho(n)
if d.Cmp(zero) != 0 {
factors = append(factors, primeFactorsWheel(d)...)
n.Quo(n, d)
if n.ProbablyPrime(10) {
factors = append(factors, n)
break
}
} else {
factors = append(factors, primeFactorsWheel(n)...)
break
}
} else {
factors = append(factors, primeFactorsWheel(n)...)
break
}
}
sort.Slice(factors, func(i, j int) bool { return factors[i].Cmp(factors[j]) < 0 })
return factors
}
 
func main() {
list := make([]int, 20)
for i := 2; i <= 20; i++ {
list[i-2] = i
}
list[19] = 65
for _, i := range list {
if rcu.IsPrime(i) {
fmt.Printf("HP%d = %d\n", i, i)
continue
}
n := 1
j := big.NewInt(int64(i))
h := []*big.Int{j}
for {
pf := primeFactors(j)
k := ""
for _, f := range pf {
k += fmt.Sprintf("%d", f)
}
j, _ = new(big.Int).SetString(k, 10)
h = append(h, j)
if j.ProbablyPrime(10) {
for l := n; l > 0; l-- {
fmt.Printf("HP%d(%d) = ", h[n-l], l)
}
fmt.Println(h[n])
break
} else {
n++
}
}
}
}</syntaxhighlight>
 
{{out}}
<pre>
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
</pre>
 
=={{header|J}}==
<syntaxhighlight 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</syntaxhighlight>
{{out}}
<pre>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</pre>
 
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.Collections;
import java.util.List;
import java.util.concurrent.ThreadLocalRandom;
import java.util.stream.Collectors;
import java.util.stream.Stream;
 
public final class HomePrimes {
 
public static void main(String[] aArgs) {
listPrimes(PRIME_LIMIT);
List<Integer> values = List.of( 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 65 );
for ( int value : values ) {
BigInteger number = BigInteger.valueOf(value);
List<BigInteger> previousNumbers = Stream.of( number ).collect(Collectors.toList());
boolean searching = true;
while ( searching ) {
number = concatenate(primeFactors(number));
previousNumbers.add(number);
if ( number.isProbablePrime(CERTAINTY_LEVEL) ) {
final int lastIndex = previousNumbers.size() - 1;
for ( int k = lastIndex; k >= 1; k-- ) {
System.out.print("HP" + previousNumbers.get(lastIndex - k) + "(" + k + ") = ");
}
System.out.println(previousNumbers.get(lastIndex));
searching = false;
}
}
}
}
private static List<BigInteger> primeFactors(BigInteger aNumber) {
List<BigInteger> result = new ArrayList<BigInteger>();
if ( aNumber.compareTo(BigInteger.valueOf(PRIME_LIMIT * PRIME_LIMIT)) <= 0 ) {
return smallPrimeFactors(aNumber);
}
if ( aNumber.isProbablePrime(CERTAINTY_LEVEL) ) {
result.add(aNumber);
return result;
}
BigInteger divisor = pollardRho(aNumber);
result.addAll(primeFactors(divisor));
aNumber = aNumber.divide(divisor);
result.addAll(primeFactors(aNumber));
Collections.sort(result);
return result;
}
private static List<BigInteger> smallPrimeFactors(BigInteger aNumber) {
int number = aNumber.intValueExact();
List<BigInteger> result = new ArrayList<BigInteger>();
for ( int i = 0; i < primes.size() && number > 1; i++ ) {
while ( number % primes.get(i) == 0 ) {
result.add(BigInteger.valueOf(primes.get(i)));
number /= primes.get(i);
}
}
if ( number > 1 ) {
result.add(BigInteger.valueOf(number));
}
return result;
}
 
private static BigInteger pollardRho(BigInteger aNumber) {
if ( ! aNumber.testBit(0) ) {
return BigInteger.TWO;
}
final BigInteger constant = new BigInteger(aNumber.bitLength(), RANDOM);
BigInteger x = new BigInteger(aNumber.bitLength(), RANDOM);
BigInteger y = x;
BigInteger divisor = null;
do {
x = x.multiply(x).add(constant).mod(aNumber);
y = y.multiply(y).add(constant).mod(aNumber);
y = y.multiply(y).add(constant).mod(aNumber);
divisor = x.subtract(y).gcd(aNumber);
} while ( divisor.compareTo(BigInteger.ONE) == 0 );
return divisor;
}
private static BigInteger concatenate(List<BigInteger> aList) {
String number = aList.stream().map(String::valueOf).collect(Collectors.joining());
return new BigInteger(number);
}
public static void listPrimes(int aNumber) {
BitSet sieve = new BitSet(aNumber + 1);
sieve.set(2, aNumber + 1);
for ( int i = 2; i <= Math.sqrt(aNumber); i = sieve.nextSetBit(i + 1) ) {
for ( int j = i * i; j <= aNumber; j = j + i ) {
sieve.clear(j);
}
}
primes = new ArrayList<Integer>(sieve.cardinality());
for ( int i = 2; i >= 0; i = sieve.nextSetBit(i + 1) ) {
primes.add(i);
}
}
private static List<Integer> primes;
private static final int CERTAINTY_LEVEL = 20;
private static final int PRIME_LIMIT = 10_000;
private static final ThreadLocalRandom RANDOM = ThreadLocalRandom.current();
}
</syntaxhighlight>
{{ out }}
<pre>
HP2(1) = 2
HP3(1) = 3
HP4(2) = HP22(1) = 211
HP5(1) = 5
HP6(1) = 23
HP7(1) = 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(1) = 11
HP12(1) = 223
HP13(1) = 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(1) = 17
HP18(1) = 233
HP19(1) = 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
</pre>
 
=={{header|Julia}}==
<langsyntaxhighlight lang="julia">using Primes
 
function homeprimechain(n::BigInt)
Line 113 ⟶ 468:
printHPiter(i)
end
</langsyntaxhighlight>{{out}}
<pre>
Home Prime chain for 2: 2 is prime.
Line 169 ⟶ 524:
HP292951656531350398312122544283(3) = HP2283450603791282934064985326977(2) = HP333297925330304453879367290955541(1) = 1381321118321175157763339900357651 is prime.
</pre>
 
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">ClearAll[HP, HPChain]
HP[n_] := FromDigits[Catenate[IntegerDigits /@ Sort[Catenate[ConstantArray @@@ FactorInteger[n]]]]]
HPChain[n_] := NestWhileList[HP, n, PrimeQ/*Not]
Row[Prepend["Home prime chain for " <> ToString[#] <> ": "]@Riffle[HPChain[#], ", "]] & /@ Range[2, 20] // Column
Row[Prepend["Home prime chain for 65: "]@Riffle[HPChain[65], ", "]]</syntaxhighlight>
{{out}}
<pre>Home prime chain for 2: 2
Home prime chain for 3: 3
Home prime chain for 4: 4, 22, 211
Home prime chain for 5: 5
Home prime chain for 6: 6, 23
Home prime chain for 7: 7
Home prime chain for 8: 8, 222, 2337, 31941, 33371313, 311123771, 7149317941, 22931219729, 112084656339, 3347911118189, 11613496501723, 97130517917327, 531832651281459, 3331113965338635107
Home prime chain for 9: 9, 33, 311
Home prime chain for 10: 10, 25, 55, 511, 773
Home prime chain for 11: 11
Home prime chain for 12: 12, 223
Home prime chain for 13: 13
Home prime chain for 14: 14, 27, 333, 3337, 4771, 13367
Home prime chain for 15: 15, 35, 57, 319, 1129
Home prime chain for 16: 16, 2222, 211101, 3116397, 31636373
Home prime chain for 17: 17
Home prime chain for 18: 18, 233
Home prime chain for 19: 19
Home prime chain for 20: 20, 225, 3355, 51161, 114651, 3312739, 17194867, 194122073, 709273797, 39713717791, 113610337981, 733914786213, 3333723311815403, 131723655857429041, 772688237874641409, 3318308475676071413
 
Home prime chain for 65: 65, 513, 33319, 1113233, 11101203, 332353629, 33152324247, 3337473732109, 111801316843763, 151740406071813, 31313548335458223, 3397179373752371411, 157116011350675311441, 331333391143947279384649, 11232040692636417517893491, 711175663983039633268945697, 292951656531350398312122544283, 2283450603791282934064985326977, 333297925330304453879367290955541, 1381321118321175157763339900357651</pre>
 
=={{header|Nim}}==
{{trans|Wren}}
{{libheader|bignum}}
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.
<syntaxhighlight 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</syntaxhighlight>
 
{{out}}
<pre>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</pre>
 
=={{header|PARI/GP}}==
{{trans|Julia}}
<syntaxhighlight lang="PARI/GP">
homeprimechain(n) = {
my(chain = [], concat_result, factors, factor_str);
while (!isprime(n),
chain = concat(chain, n); /* Append n to the chain */
factors = factor(n);
/* Correctly build the concatenated string of factors */
factor_str = Str(concat(Vec(vector(#factors~, i,
concat(Vec(concat(vector(factors[i, 2], j, Str(factors[i, 1])))))))));
concat_result = factor_str;
\\print("concat_result=" concat_result);
n = eval(concat_result); /* Convert string back to number */
);
concat(chain, n); /* Append the final prime to the chain */
}
 
printHPiter(n, numperline = 4) = {
my(chain = homeprimechain(n), len = #chain, i);
for (i = 1, len,
if (i < len,
print1("HP" , chain[i] , " (" , len - i , ") = " , if(i % numperline == 0, "\n", "")),
print(chain[i], " is prime.\n\n");
);
);
}
 
{
/* Iterate over a set of numbers */
forstep(i = 2, 20, 1, print("Home Prime chain for ", i, ": "); printHPiter(i););
printHPiter(65);
}
</syntaxhighlight>
{{out}}
<pre>
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.
 
 
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.
 
 
 
</pre>
 
 
=={{header|Perl}}==
{{libheader|ntheory}}
<syntaxhighlight 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";
}</syntaxhighlight>
 
{{out}}
<pre>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</pre>
 
=={{header|Phix}}==
Added a new mpz_pollard_rho routine, based on the [[wp:Pollard%27s_rho_algorithm]] C code.
No stretch goal here this time, just the basic task. Note that mpz_prime_factors() needs a maxprime of 12207 or more to cover the 130517 needed for HP8, and in fact the 20000 used below was found by doubling a failing 10000, which...
<!--<langsyntaxhighlight Phixlang="phix">(notonlinephixonline)-->
<span style="color: #008080;">includewith</span> <span style="color: #7060A8008080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">ejavascript_semantics</span>
<span style="color: #7060A8;">requires</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"1.0.0"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%d"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">lastp</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">s</span><span style="color: #0000FF;">}</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">substitute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"_"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">""</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">rr</span> <span style="color: #0000FF;">=</span> <span style="color: #0000007060A8;">mpz_prime_factorsmpz_pollard_rho</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000004600;">20000true</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rr</span><span style="color: #0000FF;">[$])=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">lastps</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rr</span><span style="color: #0000FF;">[$][,</span><span style="color: #000000008000;">1"_"</span><span style="color: #0000FF;">])</span>
<span style="color: #000000;">res</span> <span style="color: #7060A80000FF;">mpz=</span> <span style="color: #0000007060A8;">pappend</span> <span style="color: #0000FF;">=(</span> <span style="color: #7060A8000000;">mpz_initres</span><span style="color: #0000FF;">(,</span><span style="color: #000000;">lastps</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">mpz_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">or</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rr</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">exit</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">rr</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..$-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">lastp</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"_"</span><span style="color: #0000FF;">&</span><span style="color: #000000;">lastp</span>
<span style="color: #008080;">elsif</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rr</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">1</span>
<span style="color: #008080;">and</span> <span style="color: #000000;">rr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">exit</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rr</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">atom</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">prime</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pow</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">si</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"_%d"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">prime</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">pow</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">s</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">si</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lastp</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">s</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">lastp</span>
<span style="color: #000000;">lastp</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">..$])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">niter</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">1</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">iter</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">niter</span><span style="color: #0000FF;">></span><span style="color: #000000;">1</span><span style="color: #0000FF;">?</span><span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"(%d)"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">niter</span><span style="color: #0000FF;">):</span><span style="color: #008000;">""</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">e</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">></span><span style="color: #000000;">0.1</span><span style="color: #0000FF;">?</span><span style="color: #008000;">" ["</span><span style="color: #0000FF;">&</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">)&</span><span style="color: #008000;">"]"</span><span style="color: #0000FF;">:</span><span style="color: #008000;">""</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"HP%d%s = "</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">iter</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">niter</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s%d %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">e</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">else</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">niter</span> <span style="color: #008080;">do</span>
Line 222 ⟶ 878:
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s%s %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">res</span><span style="color: #0000FF;">[$],</span><span style="color: #000000;">e</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #7060A8;">papply</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">20</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)&</span><span style="color: #000000;">65</span><span style="color: #0000FF;">,</span><span style="color: #000000;">test</span><span style="color: #0000FF;">)</span>
<!--</langsyntaxhighlight>-->
{{out}}
Using underscores to show the individual factors that were concatenated together
Line 290 ⟶ 946:
= 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]
</pre>
=={{header|Python}}==
Abhorrently Slow, but it works.
<syntaxhighlight lang="python">
# home_primes.py by Xing216
def primeFactors(n: int) -> list[int]:
primeFactorsL = []
while n % 2 == 0:
primeFactorsL.append(2)
n = n // 2
for i in range(3,int(n**0.5)+1,2):
while n % i== 0:
primeFactorsL.append(i)
n = n // i
if n > 2:
primeFactorsL.append(n)
return primeFactorsL
def list_to_int(l: list[int]) -> int:
return int(''.join(str(i) for i in l))
def home_prime_chain(i:int) -> list[int]:
pf_int = i
chain = []
while True:
pf = primeFactors(pf_int)
pf_int = list_to_int(pf)
if len(pf) == 1:
return chain
else:
chain.append(pf_int)
for i in range(2,21):
chain_list = home_prime_chain(i)
chain_len = len(chain_list)
chain_idx_list = list(range(chain_len))[::-1]
j = chain_len
if chain_list != []:
print(f"HP{i}({chain_len}) =", end=" ")
for k,l in list(zip(chain_list, chain_idx_list)):
if l == 0:
print(f"{k}")
else:
print(f"HP{k}({l}) =", end=" ")
else:
print(f"HP{i}(1) = {i}")
</syntaxhighlight>
{{out}}
<pre style="height: 10em">
HP2(1) = 2
HP3(1) = 3
HP4(2) = HP22(1) = 211
HP5(1) = 5
HP6(1) = 23
HP7(1) = 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(1) = 11
HP12(1) = 223
HP13(1) = 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(1) = 17
HP18(1) = 233
HP19(1) = 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
</pre>
 
=={{header|Raku}}==
 
Line 300 ⟶ 1,039:
Using [https://modules.raku.org/search/?q=Prime+Factor Prime::Factor] from the [https://modules.raku.org/ Raku ecosystem].
 
<syntaxhighlight lang="raku" perl6line>use Prime::Factor;
 
my $start = now;
Line 323 ⟶ 1,062:
$now = now;
last if $step > 30;
}</langsyntaxhighlight>
{{out}}
<pre>HP2 = 2 (0.000 seconds)
Line 380 ⟶ 1,119:
HP595415617656474189392601483764603009147911(n - 30) = 13_8423_1466957_3706744784027901056001426046777 (0.015 seconds)</pre>
 
=={{header|WrenREXX}}==
<syntaxhighlight lang="rexx">/*REXX program finds and displays the home prime of a range of positive integers. */
{{libheader|Wren-math}}
numeric digits 20 /*ensure handling of larger integers. */
{{libheader|Wren-big}}
parse arg LO HI . /*obtain optional arguments from the CL*/
{{libheader|Wren-sort}}
if LO=='' | LO=="," then LO= 2 /*Not specified? Then use the default.*/
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.
if HI=='' | HI=="," then HI= 20 /* " " " " " " */
@hpc= 'home prime chain for ' /*a literal used in two SAY statements.*/
w= length(HI) /*HI width, used for output alignment. */
do j=max(2, LO) to HI /*find home primes for an integer range*/
pf= factr(j); f= words(pf) /*get prime factors; number of factors.*/
if f==1 then do; say @hpc j": " j ' is prime.'; iterate; end /*J is prime*/
xxx.1= j /*save J in the first array element. */
do n=2 until #==1 /*keep processing until we find a prime*/
xxx.n= space(pf, 0) /*obtain factors of a concatenated p.f.*/
pf= factr(xxx.n); #= words(pf) /*assign factors to PF; # of factors. */
end /*n*/
ee= n /*save EE as the final (last) prime. */
n= n - 1; z= n /*adjust N (for DO loop); assign N to Z*/
$= /*nullify the string of home primes. */
do m=1 for n /*build a list ($) of " " */
$= $ 'HP'xxx.m"("z') ─► ' /*concatenate to string of " " */
z= z - 1 /*decrease the index counter by unity. */
end /*m*/ /* [↑] the index counter is decreasing*/
 
say @hpc right(j, w)":" $ xxx.ee ' is prime.' /*show string of home primes.*/
Reaches HP20 in about 0.52 seconds but HP65 took just under 40 minutes!
end /*n*/
<lang ecmascript>import "/math" for Int
exit 0 /*stick a fork in it, we're all done. */
import "/big" for BigInt
/*──────────────────────────────────────────────────────────────────────────────────────*/
import "/sort" for Sort
factr: procedure; parse arg x 1 d,$ /*set X, D to argument 1; $ to null.*/
if x==1 then return '' /*handle the special case of X = 1. */
do while x//2==0; $= $ 2; x= x% 2; end /*append all the 2 factors of new X.*/
do while x//3==0; $= $ 3; x= x% 3; end /* " " " 3 " " " " */
do while x//5==0; $= $ 5; x= x% 5; end /* " " " 5 " " " " */
do while x//7==0; $= $ 7; x= x% 7; end /* " " " 7 " " " " */
q= 1; r= 0 /*R: will be iSqrt(x). ___*/
do while q<=x; q=q*4; end /*these two lines compute integer √ X */
do while q>1; q=q%4; _= d-r-q; r= r%2; if _>=0 then do; d= _; r= r+q; end; end
 
do k=11 by 6 to r /*insure that J isn't divisible by 3.*/
// simple wheel based prime factors routine for BigInt
parse var k '' -1 _ /*obtain the last decimal digit of K. */
var primeFactorsWheel = Fn.new { |n|
if _\==5 then do while x//k==0; $=$ k; x=x%k; end /*maybe reduce by K.*/
var inc = [4, 2, 4, 2, 4, 6, 2, 6]
if _ ==3 then iterate /*Is next Y is divisible by 5? Skip.*/
var factors = []
y= k+2; do while x//y==0; $=$ y; x=x%y; end /*maybe reduce by Y.*/
while (n%2 == 0) {
factors.add(BigInt.two) end /*k*/
/* [↓] The $ list has a leading blank.*/
n = n / 2
if x==1 then return $ /*Is residual=unity? Then don't append.*/
}
return $ x /*return $ with appended residual. */</syntaxhighlight>
while (n%3 == 0) {
{{out|output|text=&nbsp; when using the default input:}}
factors.add(BigInt.three)
<pre>
n = n / 3
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.
</pre>
 
=={{header|RPL}}==
{{works with|HP|49}}
« FACTORS ""
OVER SIZE 1 - 1 '''FOR''' j
"" PICK3 j DUP 1 + SUB EVAL ROT
1 ROT '''START''' OVER + '''NEXT'''
NIP +
-2 '''STEP'''
NIP STR→
» '<span style="color:blue">CONCFACT</span>' STO
« 0 → iter
« '''WHILE''' DUP ISPRIME? NOT
'''REPEAT''' DUP <span style="color:blue">CONCFACT</span> 'iter' 1 STO+ '''END'''
'''IF''' iter '''THEN'''
1 iter '''FOR''' j
"HP" ROT + "(" + j + ") = " + SWAP +
'''NEXT'''
'''ELSE''' "HP" OVER + " = " + SWAP + '''END'''
» » '<span style="color:blue">HP</span>' STO
 
« n <span style="color:blue">HP</span> » 'n' 2 20 1 SEQ
{{out}}
<pre>
1: { "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" }
</pre>
=={{header|Ruby}}==
<syntaxhighlight lang="ruby">require 'prime'
 
def concat(n)
n.prime_division.map{|pr, exp| pr.to_s * exp }.join.to_i
end
 
def hp(n)
res = [n]
res << n = concat(n) until n.prime?
res
end
 
def hp_to_s(ar)
return "HP#{ar[0]}(1) = #{ar[0]}" if ar.size == 1
ar[0..-2].map.with_index(1){|n, i| "HP#{n}(#{(ar.size-i)}) = "}.join + ar.last.to_s
end
 
(2..20).each {|n| puts hp_to_s(hp(n)) }
</syntaxhighlight>{{out}}
<pre>HP2(1) = 2
HP3(1) = 3
HP4(2) = HP22(1) = 211
HP5(1) = 5
HP6(1) = 23
HP7(1) = 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(1) = 11
HP12(1) = 223
HP13(1) = 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(1) = 17
HP18(1) = 233
HP19(1) = 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
</pre>
 
=={{header|Rust}}==
<syntaxhighlight lang="rust">use std::str::FromStr;
use num_bigint::BigUint;
use num_prime::nt_funcs::{is_prime, factorize};
 
fn homechains(n: &BigUint) -> Vec<BigUint> {
let mut links = vec![BigUint::from_str("0").unwrap(); 0].to_vec();
if is_prime(n, None).probably() {
links.push(n.clone());
return links;
}
let mut s = String::from_str("").unwrap();
while (n%5 == 0) {
let d = factors.addfactorize(BigIntn.fiveclone());
for (p, e) in nd = n / 5{
let s2 = format!("{p}");
}
var k = BigInt for _ in 0.new(7).e {
var i = 0 s.push_str(&s2);
while (k * k <= n) {
if (n%k == 0) {
factors.add(k)
n = n / k
} else {
k = k + inc[i]
i = (i + 1) % 8
}
}
iflet (nk >= 1BigUint::from_str(&s) factors.addunwrap(n);
links.push(k.clone());
return factors
links.append(&mut homechains(&k));
return links;
}
 
fn home_chains_print(num: u64, chains: &mut Vec<BigUint>) {
var pollardRho = Fn.new { |n|
let mut clen = chains.len();
var g = Fn.new { |x, y| (x*x + BigInt.one) % n }
varif xclen == 1 BigInt.two{
println!("HP{num} ─► {num}");
var y = BigInt.two
var} zelse = BigInt.one{
if chains[clen - 1] == chains[clen - 2] {
var d = BigInt.one
var count = 0 chains.pop();
clen -= 1;
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
}
print!("HP{num}({clen}) ─► ");
}
for (i, k) in chains.iter().enumerate() {
if (d == n) return BigInt.zero
if clen - i > 1 {
return d
print!("HP{k}({}) ─► ", clen - i - 1);
}
if (i + 1) % 5 == 0 {
 
println!();
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.addAllprintln!(primeFactorsWheel.call(n)"{k}");
break
}
} else {
factors.addAll(primeFactorsWheel.call(n))
break
}
}
Sort.insertion(factors)
return factors
}
 
 
fn main() {
for num in 2_u64..21 {
let m = BigUint::from_str(&format!("{num}")).unwrap();
let mut chains = homechains(&m);
home_chains_print(num, &mut chains);
}
let mut chains = homechains(&BigUint::from_str("65").unwrap());
home_chains_print(65_u64, &mut chains);
}
</syntaxhighlight>{{out}}
<pre>
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
</pre>
 
=={{header|Sidef}}==
<syntaxhighlight lang="ruby">for n in (2..20, 65) {
 
var steps = []
var orig = n
 
for (var f = n.factor; true; f = n.factor) {
steps << f
n = Num(f.join)
break if n.is_prime
}
 
say ("HP(#{orig}) = ", steps.map { .join('_') }.join(' -> '))
}</syntaxhighlight>
{{out}}
<pre>
HP(2) = 2
HP(3) = 3
HP(4) = 2_2 -> 2_11
HP(5) = 5
HP(6) = 2_3
HP(7) = 7
HP(8) = 2_2_2 -> 2_3_37 -> 3_19_41 -> 3_3_3_7_13_13 -> 3_11123771 -> 7_149_317_941 -> 229_31219729 -> 11_2084656339 -> 3_347_911_118189 -> 11_613_496501723 -> 97_130517_917327 -> 53_1832651281459 -> 3_3_3_11_139_653_3863_5107
HP(9) = 3_3 -> 3_11
HP(10) = 2_5 -> 5_5 -> 5_11 -> 7_73
HP(11) = 11
HP(12) = 2_2_3
HP(13) = 13
HP(14) = 2_7 -> 3_3_3 -> 3_3_37 -> 47_71 -> 13_367
HP(15) = 3_5 -> 5_7 -> 3_19 -> 11_29
HP(16) = 2_2_2_2 -> 2_11_101 -> 3_11_6397 -> 3_163_6373
HP(17) = 17
HP(18) = 2_3_3
HP(19) = 19
HP(20) = 2_2_5 -> 3_3_5_5 -> 5_11_61 -> 11_4651 -> 3_3_12739 -> 17_194867 -> 19_41_22073 -> 709_273797 -> 3_97_137_17791 -> 11_3610337981 -> 7_3391_4786213 -> 3_3_3_3_7_23_31_1815403 -> 13_17_23_655857429041 -> 7_7_2688237874641409 -> 3_31_8308475676071413
HP(65) = 5_13 -> 3_3_3_19 -> 11_13_233 -> 11_101203 -> 3_3_23_53629 -> 3_3_1523_24247 -> 3_3_3_7_47_3732109 -> 11_18013_16843763 -> 151_740406071813 -> 3_13_13_54833_5458223 -> 3_3_97_179_373_7523_71411 -> 1571_1601_1350675311441 -> 3_3_13_33391_143947_279384649 -> 11_23_204069263_6417517893491 -> 7_11_1756639_83039633268945697 -> 29_29_5165653_13503983_12122544283 -> 228345060379_1282934064985326977 -> 3_3_3_2979253_3030445387_9367290955541 -> 1381_3211183211_75157763339900357651
</pre>
 
=={{header|Transd}}==
<syntaxhighlight lang="Scheme">#lang transd
 
MainModule: {
homePrime: (λ i BigLong()
(if (is-prime i) (lout "HP" i " = " i) continue)
(with n BigLong(i) ch Vector<BigLong>() st 1
(append ch n)
(while true
(= n (join (prime-factors n) ""))
(append ch n)
(if (is-probable-prime n 15)
(for l in Range(in: ch 0 -1) do
(textout "HP" l "("(- (size ch) @idx 1) ") = "))
(lout (back ch)) (ret)
else (+= st 1))
)
)
),
_start: (λ
(for i in Range(2 21) do (homePrime BigLong(i)))
(homePrime BigLong(65))
)
}</syntaxhighlight>
{{out}}
<pre>
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
</pre>
 
=={{header|Wren}}==
{{libheader|Wren-math}}
{{libheader|Wren-big}}
 
===Wren-cli===
The built-in routines use 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!
<syntaxhighlight lang="wren">import "./math" for Int
import "./big" for BigInt
var list = (2..20).toList
list.add(65)
Line 482 ⟶ 1,472:
var h = [j]
while (true) {
var k = primeFactorsBigInt.callprimeFactors(j).reduce("") { |acc, f| acc + f.toString }
j = BigInt.new(k)
h.add(j)
Line 493 ⟶ 1,483:
}
}
}</langsyntaxhighlight>
 
{{out}}
Line 517 ⟶ 1,507:
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
</pre>
<br>
 
===Embedded===
{{libheader|Wren-gmp}}
This reduces the overall time taken to 5.1 seconds. The factorization method used is essentially the same as the Wren-cli version so the vast improvement in performance is due solely to the use of GMP.
<syntaxhighlight lang="wren">/* Home_primes_2.wren */
 
import "./gmp" for Mpz
import "./math" for Int
 
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 = Mpz.from(i)
var h = [j.copy()]
while (true) {
var k = Mpz.primeFactors(j).reduce("") { |acc, f| acc + f.toString }
j = Mpz.fromStr(k)
h.add(j)
if (j.probPrime(15) > 0) {
for (l in n...0) System.write("HP%(h[n-l])(%(l)) = ")
System.print(h[n])
break
} else {
n = n + 1
}
}
}</syntaxhighlight>
 
{{out}}
<pre>
Same as Wren-cli version.
</pre>
Aerobar
1,150

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/312337...361375"