Home primes

This task has been clarified. Its programming examples are in need of review to ensure that they still fit the requirements of the task.

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).

Prime numbers are their own Home prime;

So:

   HP2 = 2
   
   HP7 = 7

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

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

Task

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

Stretch goal

Find and show the iteration chain for 65.

Impossible goal

Show the the Home prime for HP49.

See also

OEIS:A037274 - Home primes for n >= 2 OEIS:A056938 - Concatenation chain for HP49

Factor

Works with: Factor version 0.99 2021-02-05

<lang factor>USING: formatting kernel make math math.parser math.primes math.primes.factors math.ranges present prettyprint sequences sequences.extras ;

squish ( seq -- n ) [ present ] map-concat dec> ;

next ( m -- n ) factors squish ; inline

(chain) ( n -- ) [ dup prime? ] [ dup , next ] until , ;

chain ( n -- seq ) [ (chain) ] { } make ;

prime. ( n -- ) dup "HP%d = %d\n" printf ;

setup ( seq -- n s r ) unclip-last swap dup length 1 [a,b] ;

multi. ( n -- ) chain setup [ "HP%d(%d) = " printf ] 2each . ;

chain. ( n -- ) dup prime? [ prime. ] [ multi. ] if ;

2 20 [a,b] [ chain. ] each</lang>

Output:

HP2 = 2
HP3 = 3
HP4(2) = HP22(1) = 211
HP5 = 5
HP6(1) = 23
HP7 = 7
HP8(13) = HP222(12) = HP2337(11) = HP31941(10) = HP33371313(9) = HP311123771(8) = HP7149317941(7) = HP22931219729(6) = HP112084656339(5) = HP3347911118189(4) = HP11613496501723(3) = HP97130517917327(2) = HP531832651281459(1) = 3331113965338635107
HP9(2) = HP33(1) = 311
HP10(4) = HP25(3) = HP55(2) = HP511(1) = 773
HP11 = 11
HP12(1) = 223
HP13 = 13
HP14(5) = HP27(4) = HP333(3) = HP3337(2) = HP4771(1) = 13367
HP15(4) = HP35(3) = HP57(2) = HP319(1) = 1129
HP16(4) = HP2222(3) = HP211101(2) = HP3116397(1) = 31636373
HP17 = 17
HP18(1) = 233
HP19 = 19
HP20(15) = HP225(14) = HP3355(13) = HP51161(12) = HP114651(11) = HP3312739(10) = HP17194867(9) = HP194122073(8) = HP709273797(7) = HP39713717791(6) = HP113610337981(5) = HP733914786213(4) = HP3333723311815403(3) = HP131723655857429041(2) = HP772688237874641409(1) = 3318308475676071413

Julia

<lang julia>using Primes

function homeprimechain(n::BigInt)

   isprime(n) && return [n]
   concat = prod(string(i)^j for (i, j) in factor(n).pe)
   return pushfirst!(homeprimechain(parse(BigInt, concat)), n)

end homeprimechain(n::Integer) = homeprimechain(BigInt(n))

function printHPiter(n, numperline = 4)

   chain = homeprimechain(n)
   len = length(chain)
   for (i, ent) in enumerate(chain)
       print(i < len ? "HP$ent" * "($(len - i)) = " * (i % numperline == 0 ? "\n" : "") : "$ent is prime.\n\n")
   end

end

for i in [2:20; 65]

  print("Home Prime chain for $i: ")
  printHPiter(i)

end

</lang>

Output:

Home Prime chain for 2: 2 is prime.

Home Prime chain for 3: 3 is prime.

Home Prime chain for 4: HP4(2) = HP22(1) = 211 is prime.

Home Prime chain for 5: 5 is prime.

Home Prime chain for 6: HP6(1) = 23 is prime.

Home Prime chain for 7: 7 is prime.

Home Prime chain for 8: HP8(13) = HP222(12) = HP2337(11) = HP31941(10) =
HP33371313(9) = HP311123771(8) = HP7149317941(7) = HP22931219729(6) =
HP112084656339(5) = HP3347911118189(4) = HP11613496501723(3) = HP97130517917327(2) =
HP531832651281459(1) = 3331113965338635107 is prime.

Home Prime chain for 9: HP9(2) = HP33(1) = 311 is prime.

Home Prime chain for 10: HP10(4) = HP25(3) = HP55(2) = HP511(1) =
773 is prime.

Home Prime chain for 11: 11 is prime.

Home Prime chain for 12: HP12(1) = 223 is prime.

Home Prime chain for 13: 13 is prime.

Home Prime chain for 14: HP14(5) = HP27(4) = HP333(3) = HP3337(2) =
HP4771(1) = 13367 is prime.

Home Prime chain for 15: HP15(4) = HP35(3) = HP57(2) = HP319(1) =
1129 is prime.

Home Prime chain for 16: HP16(4) = HP2222(3) = HP211101(2) = HP3116397(1) = 
31636373 is prime.

Home Prime chain for 17: 17 is prime.

Home Prime chain for 18: HP18(1) = 233 is prime.

Home Prime chain for 19: 19 is prime.

Home Prime chain for 20: HP20(15) = HP225(14) = HP3355(13) = HP51161(12) =
HP114651(11) = HP3312739(10) = HP17194867(9) = HP194122073(8) =
HP709273797(7) = HP39713717791(6) = HP113610337981(5) = HP733914786213(4) =
HP3333723311815403(3) = HP131723655857429041(2) = HP772688237874641409(1) = 3318308475676071413 is prime.

Home Prime chain for 65: HP65(19) = HP513(18) = HP33319(17) = HP1113233(16) = 
HP11101203(15) = HP332353629(14) = HP33152324247(13) = HP3337473732109(12) =
HP111801316843763(11) = HP151740406071813(10) = HP31313548335458223(9) = HP3397179373752371411(8) =
HP157116011350675311441(7) = HP331333391143947279384649(6) = HP11232040692636417517893491(5) = HP711175663983039633268945697(4) =
HP292951656531350398312122544283(3) = HP2283450603791282934064985326977(2) = HP333297925330304453879367290955541(1) = 1381321118321175157763339900357651 is prime.

Raku

Using Prime::Factor from the Raku ecosystem.

<lang perl6>use Prime::Factor;

for flat 2..20, 65 -> $m {

   my (@steps, @factors) = $m;
   @steps.push: @factors.join.Int while (@factors = prime-factors @steps[*-1]) > 1;
   my $step = +@steps;
   say +@steps > 1
       ?? (@steps[0..*-2].map( { "HP$_\({--$step})" } ).join: ' = ')
       !! ("HP$m"), " = ", @steps[*-1];

}</lang>

Output:

HP2 = 2
HP3 = 3
HP4(2) = HP22(1) = 211
HP5 = 5
HP6(1) = 23
HP7 = 7
HP8(13) = HP222(12) = HP2337(11) = HP31941(10) = HP33371313(9) = HP311123771(8) = HP7149317941(7) = HP22931219729(6) = HP112084656339(5) = HP3347911118189(4) = HP11613496501723(3) = HP97130517917327(2) = HP531832651281459(1) = 3331113965338635107
HP9(2) = HP33(1) = 311
HP10(4) = HP25(3) = HP55(2) = HP511(1) = 773
HP11 = 11
HP12(1) = 223
HP13 = 13
HP14(5) = HP27(4) = HP333(3) = HP3337(2) = HP4771(1) = 13367
HP15(4) = HP35(3) = HP57(2) = HP319(1) = 1129
HP16(4) = HP2222(3) = HP211101(2) = HP3116397(1) = 31636373
HP17 = 17
HP18(1) = 233
HP19 = 19
HP20(15) = HP225(14) = HP3355(13) = HP51161(12) = HP114651(11) = HP3312739(10) = HP17194867(9) = HP194122073(8) = HP709273797(7) = HP39713717791(6) = HP113610337981(5) = HP733914786213(4) = HP3333723311815403(3) = HP131723655857429041(2) = HP772688237874641409(1) = 3318308475676071413
HP65(19) = HP513(18) = HP33319(17) = HP1113233(16) = HP11101203(15) = HP332353629(14) = HP33152324247(13) = HP3337473732109(12) = HP111801316843763(11) = HP151740406071813(10) = HP31313548335458223(9) = HP3397179373752371411(8) = HP157116011350675311441(7) = HP331333391143947279384649(6) = HP11232040692636417517893491(5) = HP711175663983039633268945697(4) = HP292951656531350398312122544283(3) = HP2283450603791282934064985326977(2) = HP333297925330304453879367290955541(1) = 1381321118321175157763339900357651

Wren

Library: Wren-math

Library: Wren-big

Library: Wren-sort

This uses a combination of the Pollard Rho algorithm and wheel based factorization to try and factorize the large numbers involved here in a reasonable time.

Reaches HP20 in about 0.52 seconds but HP65 took just under 40 minutes! <lang ecmascript>import "/math" for Int import "/big" for BigInt import "/sort" for Sort

// simple wheel based prime factors routine for BigInt var primeFactorsWheel = Fn.new { |n|

   var inc = [4, 2, 4, 2, 4, 6, 2, 6]
   var factors = []
   while (n%2 == 0) {
       factors.add(BigInt.two)
       n = n / 2
   }
   while (n%3 == 0) {
       factors.add(BigInt.three)
       n = n / 3
   }
   while (n%5 == 0) {
       factors.add(BigInt.five)
       n = n / 5
   }
   var k = BigInt.new(7)
   var i = 0
   while (k * k <= n) {
       if (n%k == 0) {
           factors.add(k)
           n = n / k
       } else {
           k = k + inc[i]
           i = (i + 1) % 8
       }
   }
   if (n > 1) factors.add(n)
   return factors

}

var pollardRho = Fn.new { |n|

   var g = Fn.new { |x, y| (x*x + BigInt.one) % n }
   var x = BigInt.two
   var y = BigInt.two
   var z = BigInt.one
   var d = BigInt.one
   var count = 0
   while (true) {
       x = g.call(x, n)
       y = g.call(g.call(y, n), n)
       d = (x - y).abs % n
       z = z * d
       count = count + 1
       if (count == 100) {
           d = BigInt.gcd(z, n)
           if (d != BigInt.one) break
           z = BigInt.one
           count = 0
       }
   }
   if (d == n) return BigInt.zero
   return d

}

var primeFactors = Fn.new { |n|

   var factors = []
   while (n > 1) {
       if (n > BigInt.maxSmall/100) {
           var d = pollardRho.call(n)
           if (d != 0) {
               factors.addAll(primeFactorsWheel.call(d))
               n = n / d
               if (n.isProbablePrime(2)) {
                   factors.add(n)
                   break
               }
           } else {
               factors.addAll(primeFactorsWheel.call(n))
               break
           }
       } else {
           factors.addAll(primeFactorsWheel.call(n))
           break
       }
   }
   Sort.insertion(factors)
   return factors

}

var list = (2..20).toList list.add(65) for (i in list) {

   if (Int.isPrime(i)) {
       System.print("HP%(i) = %(i)")
       continue
   }
   var n = 1
   var j = BigInt.new(i)
   var h = [j]
   while (true) {
       var k = primeFactors.call(j).reduce("") { |acc, f| acc + f.toString }
       j = BigInt.new(k)
       h.add(j)
       if (j.isProbablePrime(2)) {
           for (l in n...0) System.write("HP%(h[n-l])(%(l)) = ")
           System.print(h[n])
           break
       } else {
           n = n + 1
       }
   }

}</lang>

Output:

HP2 = 2
HP3 = 3
HP4(2) = HP22(1) = 211
HP5 = 5
HP6(1) = 23
HP7 = 7
HP8(13) = HP222(12) = HP2337(11) = HP31941(10) = HP33371313(9) = HP311123771(8) = HP7149317941(7) = HP22931219729(6) = HP112084656339(5) = HP3347911118189(4) = HP11613496501723(3) = HP97130517917327(2) = HP531832651281459(1) = 3331113965338635107
HP9(2) = HP33(1) = 311
HP10(4) = HP25(3) = HP55(2) = HP511(1) = 773
HP11 = 11
HP12(1) = 223
HP13 = 13
HP14(5) = HP27(4) = HP333(3) = HP3337(2) = HP4771(1) = 13367
HP15(4) = HP35(3) = HP57(2) = HP319(1) = 1129
HP16(4) = HP2222(3) = HP211101(2) = HP3116397(1) = 31636373
HP17 = 17
HP18(1) = 233
HP19 = 19
HP20(15) = HP225(14) = HP3355(13) = HP51161(12) = HP114651(11) = HP3312739(10) = HP17194867(9) = HP194122073(8) = HP709273797(7) = HP39713717791(6) = HP113610337981(5) = HP733914786213(4) = HP3333723311815403(3) = HP131723655857429041(2) = HP772688237874641409(1) = 3318308475676071413
HP65(19) = HP513(18) = HP33319(17) = HP1113233(16) = HP11101203(15) = HP332353629(14) = HP33152324247(13) = HP3337473732109(12) = HP111801316843763(11) = HP151740406071813(10) = HP31313548335458223(9) = HP3397179373752371411(8) = HP157116011350675311441(7) = HP331333391143947279384649(6) = HP11232040692636417517893491(5) = HP711175663983039633268945697(4) = HP292951656531350398312122544283(3) = HP2283450603791282934064985326977(2) = HP333297925330304453879367290955541(1) = 1381321118321175157763339900357651