Home primes

You are encouraged to solve this task according to the task description, using any language you may know.
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
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
- 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
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++
}
}
}
}
- 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
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
- 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
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();
}
- Output:
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
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
- 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.
Mathematica /Wolfram Language
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], ", "]]
- Output:
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
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.
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
- 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
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);
}
- 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. 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.
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";
}
- 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]
Python
Abhorrently Slow, but it works.
# 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}")
- Output:
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
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.
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)
REXX
All code inline
/*REXX program finds and displays the home prime of a range of positive integers. */
numeric digits 20 /*ensure handling of larger integers. */
parse arg LO HI . /*obtain optional arguments from the CL*/
if LO=='' | LO=="," then LO= 2 /*Not specified? Then use the default.*/
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.*/
end /*n*/
exit 0 /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
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.*/
parse var k '' -1 _ /*obtain the last decimal digit of K. */
if _\==5 then do while x//k==0; $=$ k; x=x%k; end /*maybe reduce by K.*/
if _ ==3 then iterate /*Is next Y is divisible by 5? Skip.*/
y= k+2; do while x//y==0; $=$ y; x=x%y; end /*maybe reduce by Y.*/
end /*k*/
/* [↓] The $ list has a leading blank.*/
if x==1 then return $ /*Is residual=unity? Then don't append.*/
return $ x /*return $ with appended residual. */
- output when using the default input:
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. > 1000 seconds
Using standard procedures
Libraries: How to use
Libraries: Source code
Procedure Factors() in Sequences returns the number of prime factors and stores them in fact.. That's why below code could be compact and elegant. The program shows all HPx, x = 1...48, as given in sequence A037274 of the OEIS. Stretch goal HP65 was out of REXX' reach.
include Settings
say version; say 'Home Primes'; say
numeric digits 22
do i = 1 to 48
call Home i
end
exit
Home:
procedure expose fact. glob. work.
arg xx
call Time('r')
yy = xx/1
/* Collect chain */
n = 0
do while Factors(yy) > 1
n = n+1; work.n = yy; yy = ''
do i = 1 to fact.0
yy = yy||fact.factor.i
end
end
/* Show results */
if n = 0 then
call Charout ,'HP'xx '= '
else do
do i = 1 to n
call Charout ,'HP'work.i'('n-i+1') = '
end
end
call Charout ,yy
say
say Time('e')/1 'seconds'
say
return
include Abend
include Functions
include Numbers
include Sequences
- Output:
REXX-ooRexx_5.0.0(MT)_64-bit 6.05 23 Dec 2022 Home Primes HP1 = 1 0 seconds HP2 = 2 0 seconds HP3 = 3 0 seconds HP4(2) = HP22(1) = 211 0 seconds HP5 = 5 0 seconds HP6(1) = 23 0 seconds HP7 = 7 0 seconds 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 0.125 seconds HP9(2) = HP33(1) = 311 0 seconds HP10(4) = HP25(3) = HP55(2) = HP511(1) = 773 0 seconds HP11 = 11 0 seconds HP12(1) = 223 0 seconds HP13 = 13 0 seconds HP14(5) = HP27(4) = HP333(3) = HP3337(2) = HP4771(1) = 13367 0 seconds HP15(4) = HP35(3) = HP57(2) = HP319(1) = 1129 0 seconds HP16(4) = HP2222(3) = HP211101(2) = HP3116397(1) = 31636373 0 seconds HP17 = 17 0 seconds HP18(1) = 233 0 seconds HP19 = 19 0 seconds 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 10.975 seconds HP21(1) = 37 0 seconds HP22(1) = 211 0 seconds HP23 = 23 0 seconds HP24(2) = HP2223(1) = 331319 0 seconds HP25(3) = HP55(2) = HP511(1) = 773 0 seconds HP26(4) = HP213(3) = HP371(2) = HP753(1) = 3251 0 seconds HP27(4) = HP333(3) = HP3337(2) = HP4771(1) = 13367 0 seconds HP28(1) = 227 0 seconds HP29 = 29 0 seconds HP30(2) = HP235(1) = 547 0 seconds HP31 = 31 0 seconds HP32(2) = HP22222(1) = 241271 0 seconds HP33(1) = 311 0 seconds HP34(5) = HP217(4) = HP731(3) = HP1743(2) = HP3783(1) = 31397 0 seconds HP35(3) = HP57(2) = HP319(1) = 1129 0 seconds HP36(2) = HP2233(1) = 71129 0 seconds HP37 = 37 0 seconds HP38(2) = HP219(1) = 373 0 seconds HP39(1) = 313 0 seconds HP40(9) = HP2225(8) = HP5589(7) = HP3333323(6) = HP77591153(5) = HP292675557(4) = HP3313147049(3) = HP80910194019(2) = HP353639502807(1) = 3314192745739 0 seconds HP41 = 41 0 seconds HP42(2) = HP237(1) = 379 0 seconds HP43 = 43 0 seconds HP44(9) = HP2211(8) = HP31167(7) = HP333463(6) = HP13113227(5) = HP173229331(4) = HP1115748121(3) = HP5412062381(2) = HP11607810553(1) = 22815088913 0 seconds HP45(6) = HP335(5) = HP567(4) = HP33337(3) = HP173753(2) = HP239727(1) = 3411949 0 seconds HP46(1) = 223 0 seconds HP47 = 47 0 seconds HP48(15) = HP22223(14) = HP71313(13) = HP3112161(12) = HP313199401(11) = HP19431093517(10) = HP11171098771087(9) = HP231481703946591(8) = HP33753671034726207(7) = HP311251223678242069(6) = HP2345832952795526741(5) = HP35957822911130063089(4) = HP83599633943011938251(3) = HP314912354898161457127(2) = HP467793678496358995643(1) = 6161791591356884791277 219.75 seconds
RPL
« FACTORS "" OVER SIZE 1 - 1 FOR j "" PICK3 j DUP 1 + SUB EVAL ROT 1 ROT START OVER + NEXT NIP + -2 STEP NIP STR→ » 'CONCFACT' STO « 0 → iter « WHILE DUP ISPRIME? NOT REPEAT DUP CONCFACT 'iter' 1 STO+ END IF iter THEN 1 iter FOR j "HP" ROT + "(" + j + ") = " + SWAP + NEXT ELSE "HP" OVER + " = " + SWAP + END » » 'HP' STO
« n HP » 'n' 2 20 1 SEQ
- Output:
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" }
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)) }
- Output:
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
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();
let d = factorize(n.clone());
for (p, e) in d {
let s2 = format!("{p}");
for _ in 0..e {
s.push_str(&s2);
}
}
let k = BigUint::from_str(&s).unwrap();
links.push(k.clone());
links.append(&mut homechains(&k));
return links;
}
fn home_chains_print(num: u64, chains: &mut Vec<BigUint>) {
let mut clen = chains.len();
if clen == 1 {
println!("HP{num} ─► {num}");
} else {
if chains[clen - 1] == chains[clen - 2] {
chains.pop();
clen -= 1;
}
print!("HP{num}({clen}) ─► ");
for (i, k) in chains.iter().enumerate() {
if clen - i > 1 {
print!("HP{k}({}) ─► ", clen - i - 1);
if (i + 1) % 5 == 0 {
println!();
}
} else {
println!("{k}");
}
}
}
}
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);
}
- 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
Sidef
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(' -> '))
}
- Output:
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
Transd
#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))
)
}
- 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
Wren
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!
import "./math" for Int
import "./big" for BigInt
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 = BigInt.primeFactors(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
}
}
}
- 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
Embedded
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.
/* 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
}
}
}
- Output:
Same as Wren-cli version.