Calculate Home Primes

Question

The Home Prime of an integer \$n\$ is the value obtained by repeatedly factoring and concatenating \$n\$'s prime factors (in ascending order, including repeats) until reaching a fixed point (a prime). For example, the Home Prime (\$\text{HP}(n)\$) of \$10\$ is \$773\$ as:

$$\begin{align} 10 & = 2 \times 5 \to 25 \\ 25 & = 5 \times 5 \to 55 \\ 55 & = 5 \times 11 \to 511 \\ 511 & = 7 \times 73 \to 773 \\ \end{align}$$

There are two equivalent ways to consider when the sequence ends:

• It ends at a prime
• It reaches a fixed point, as the prime factors of a prime \$p\$ is just \$p\$

Note that the Home Prime of some numbers is currently unknown (e.g. \$49\$ or \$77\$).

---

You are to take a positive integer \$n \ge 2\$ as input through any convenient method or format and output the Home Prime of \$n\$. You may assume that you don't have to handle any input that would exceed the integer limit in your language at any step, and you may assume that the input will already have a known Home Prime (so 49 won't be an input).

Make sure you program handles all inputs correctly, not just those that are only semiprimes:

$$\begin{align} \text{HP}(24) = 331319 :\\ 24 & = 2 \times 2 \times 2 \times 3 \to 2223 \\ 2223 & = 3 \times 3 \times 13 \times 19 \to 331319 \end{align}$$

This is code-golf so the shortest code in bytes wins!

Test cases

These are the results for each \$2 \le n \le 100\$, excluding \$n = 49,77,80,96\$ which don't terminate on TIO in my example program.

  2                                  2
  3                                  3
  4                                211
  5                                  5
  6                                 23
  7                                  7
  8                3331113965338635107
  9                                311
 10                                773
 11                                 11
 12                                223
 13                                 13
 14                              13367
 15                               1129
 16                           31636373
 17                                 17
 18                                233
 19                                 19
 20                3318308475676071413
 21                                 37
 22                                211
 23                                 23
 24                             331319
 25                                773
 26                               3251
 27                              13367
 28                                227
 29                                 29
 30                                547
 31                                 31
 32                             241271
 33                                311
 34                              31397
 35                               1129
 36                              71129
 37                                 37
 38                                373
 39                                313
 40                      3314192745739
 41                                 41
 42                                379
 43                                 43
 44                        22815088913
 45                            3411949
 46                                223
 47                                 47
 48             6161791591356884791277
 50                               3517
 51                                317
 52                               2213
 53                                 53
 54                               2333
 55                                773
 56                              37463
 57                               1129
 58                                229
 59                                 59
 60                              35149
 61                                 61
 62                              31237
 63                                337
 64                      1272505013723
 65 1381321118321175157763339900357651
 66                               2311
 67                                 67
 68                               3739
 69                              33191
 70                                257
 71                                 71
 72                            1119179
 73                                 73
 74                                379
 75                                571
 76                             333271
 78                         3129706267
 79                                 79
 81                    193089459713411
 82                                241
 83                                 83
 84                               2237
 85                               3137
 86          6012903280474189529884459
 87         41431881512748629379008933
 88                             719167
 89                                 89
 90                              71171
 91                          236122171
 92                             331319
 93                                331
 94                               1319
 95                              36389
 97                                 97
 98                                277
 99                              71143
100                             317047

Answer 1

05AB1E, 3 bytes

ΔÒJ

Try it online!

Δ run until the output doesn't change:
Ò prime factors including duplicates
J join into an integer

Answer 2

JavaScript (ES6),  58  55 bytes

f=n=>n-(g=d=>q=n>1?n%d?g(d+1):d+g(d,n/=d):'')(2)?f(q):q

Try it online!

Commented

f = n =>               // f is a recursive function taking the input n
  n - (                // subtract from n the result of a call to ...
    g = d =>           // ... g: a recursive function taking a divisor d
    q =                //   save in q:
      n > 1 ?          //     if n is greater than 1:
        n % d ?        //       if d is not a divisor of n:
          g(d + 1)     //         increment d until it is
        :              //       else:
          d +          //         append d
          g(d,         //         append the result of a recursive call
               n /= d) //         with n divided by d
      :                //     else:
        ''             //       stop and force coercion to a string
  )(2)                 // initial call to g with d = 2
  ?                    // if it's not equal to n:
    f(q)               //   recursive call to f with n = q
  :                    // else:
    q                  //   we're done: return q

Answer 3

APL(Dyalog Extended), 12 bytes ^SBCS

{⍎⊃,/⍕¨⍭⍵}⍣=

Try it on APLgolf!

A dfn submission which takes a single argument.

Answer 4

Bash, ^{84 82} 71 bytes

Saved 11 bytes thanks to caird coinheringaahing!!!

for((;$1-${2-0};)){ set - `factor $1|sed 's/.*://;s/ //g'` $1;};echo $1

Try it online!

Returns the home prime of \$n\$ quickly (performs all testcase in less than 2 seconds on TIO).

Answer 5

Haskell, 79 bytes

until((==)<*>g)g
g=read.f
f 1=""
f n=[show p++f(div n p)|p<-[2..],mod n p<1]!!0

Try it online!

The relevant function is until((==)<*>g)g, which takes as input a number n and returns its Home prime.

Answer 6

Husk, 6 bytes

ω(rṁsp

Try it online!

ω(        # iterate until reaching a fixed point:
     p    #  get the prime factors
   ṁs     #  convert each to a string & concatenate
  r       #  convert the string to a value

Answer 7

Vyxal, 5 4 bytes

‡ǐṅẊ

Try it Online!

Jelly really do be getting rekt by stack languages though :p

This isn't 4 bytes because strings and integers aren't interchangeable like 05ab1e (and by extension Ohm), but that's okay. I added better type cohesion.

Explained

‡ǐṅẊ
‡ǐṅ  # lambda x: "".join(prime_factorisation(x))
   Ẋ # repeat the above on the input until it doesn't change.

Answer 8

Pyth, 14 bytes

W!P_Q=QsjkPQ;Q

Try it online!

Explanation

Q     # integer input
W!P_Q # While Q is not prime
=Q    # Set Q to
PQ    # Returns prime factors of Q in increasing order.
k     # Empty string
jk    # Join them
s     # Convert to integer
;     # End of loop
Q     # Print the final value of Q

Answer 9

Ohm v2, 4 bytes

·ΘoJ

Try it online!

Answer 10

Jelly, 6 bytes

ÆfV$ÐL

Try it online!

This seems oddly long, but the prime factorize built-in is two bytes, I don't think there's a way to bypass needing the $, and the loop-until-not-unique built-in is only one byte long for the accumulator version.

Answer 11

R + numbers, 74 73 bytes

n=scan();while(F<-el(Reduce(paste0,numbers::primeFactors(n)):0)-n)n=n+F;n

Try it online!

Answer 12

Japt, 12 bytes

@=k ¬n)j}a;U

Try it

@...}a  - first number to return a truthy value when passed trough:
@=        > ignore input and assign 1st input U : *
k ¬n)       * prime factors of U joined and converted to a number
j         > return(is prime?)
;U      - print U

Answer 13

Japt, 11 bytes

j ?U:ßUk ¬n 
j ?         // If the input is prime
   U        // we're done, return the input.
    :       // Otherwise,
     ß      // recursively rerun
      Uk    // with the input's prime factors
         ¬n // joined together as a string and parsed to a number.

Try it here.

Answer 14

Retina 0.8.2, 37 bytes

{`.+
$*_
+`(__+?)(\1)*$
$.1_$#2$*_
_

Try it online! Somewhat slow, so link only includes faster test cases. Explanation:

{`

Repeat until the fixed point.

.+
$*_

Convert to unary.

+`

Repeat until all prime factors have been found.

(__+?)(\1)*$

Find the lowest factor of the remainder.

$.1_$#2$*_

Prefix the decimal of the factor to the quotient, thus concatenating it to the factors found so far.

_

Delete the trailing unary 1.

Answer 15

Python 3, 109 bytes

def f(n,m=0):
 while n-m:
  l=m=n;n=0
  for i in range(2,l+1):
   while l%i<1:n=int(f'{n}{i}');l/=i
 return n

Try it online!

Quite verbose, returns the home prime of \$n\$.

Answer 16

Wolfram Language (Mathematica), 60 bytes

#//.x_:>FromDigits[ToString/@(""<>Table@@@FactorInteger@x)]&

Try it online!

-14 bytes from @att

Answer 17

Pyth, 5 bytes

usjkP

Try it online!

Pyth could tie 05AB1E if it had a "join into integer" byte, or Ohm if it could take the primes factors of a string. Beats Jelly even without them, which surprises me.

Answer 18

Arturo, 49 bytes

$->n[until->prime? n[n:do join factors.prime n]n]

Try it

Really useful:

• join [12, 3, 45] -> "12345"
• do "12345" -> 12345

Answer 19

PowerShell, 88 bytes

param($n)while($n-ne$m){$m=$n;$n=[int](((factor $m)-replace"^\d+: ").split()-join"")};$n

Try it online!

Well, I'm lazy, just ported @Noodle9

PowerShell, 203 bytes

param($k)$s='$f;$n/=$f';function F($n){$m=[math]::sqrt($n);$f=2;while(!($n%$f)){iex $s};$f=3;while($f-le$m-and$n-ge$m){while(!($n%$f)){iex $s};$f+=2};$n};while($k-ne$g){$g=$k;$k=[int]((F($g))-join'')};$k

Try it online!

This one has some thought put into it...

F() is a function that returns the prime factors of a number, it works like

1. Handle 2 as a prime
2. Then brute force odd numbers
3. Stop when the factor to test exceeds the square root of the number, or the remaining quotient is less than the square root of the number

Answer 20

Scratch, 320 bytes

Try it online!

Numbers that use values greater than 1 sextillion break because Scratch automatically converts them to scientific notation. Alternatively, 38 blocks.

when gf clicked
delete all of[P v
ask()and wait
set[N v]to(answer
repeat until<(length of[P v])=(1
repeat(length of[P v
set[N v]to(join(item(length of[P v])of[P v])(N
delete(length of[P v])of[P v
end
repeat until<(N)=(1
set[F v]to(2
repeat until<((N)/(F))=(round((N)/(F
change[F v]by(1
end
set[N v]to((N)/(F
add(F)to[P v

Answer 21

Japt, 10 bytes

@j}a@=k ¬n

Try it

Japt -h, 6 bytes

Assumes that it takes no more than n iterations to reach p.

Æ=k ¬n

Try it

Answer 22

Scala, 233 212 bytes

saved 21 bytes thanks to the comment of @The Thonnu

Golfed version, try it online!

type L=Long
def f(n:L,m:L=0):Long={@scala.annotation.tailrec def g(n:L,m:L):L=if(n==m)n else{var M=n;var N=0L;var l=M;for(i<-2 to l.toInt)while(l%i==0){N=N.toString.concat(i.toString).toLong;l/=i};g(N,M)};g(n,m)}

Ungolfed version

import scala.annotation.tailrec

object Main {
  def f(n: Long, m: Long = 0): Long = {
    @tailrec
    def innerF(n: Long, m: Long): Long = {
      if (n == m) n
      else {
        var newM = n
        var newN = 0L
        var l = newM

        for (i <- 2 to l.toInt) {
          while (l % i == 0) {
            newN = newN.toString.concat(i.toString).toLong
            l /= i
          }
        }

        innerF(newN, newM)
      }
    }

    innerF(n, m)
  }

  def main(args: Array[String]): Unit = {
    val tests = List(2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20)
    val expected = List(2, 3, 211, 5, 23, 7, 3331113965338635107L, 311, 773, 11, 223, 13, 13367, 1129, 31636373, 17, 233, 19, 3318308475676071413L)
    val checker = List("❌", "✓")

    for ((t, e) <- tests.zip(expected)) {
      if (e.toString.length > 10) {
        println(s"$t -> too big")
      } else {
        val s = f(t)
        println(s"$t -> $s ${checker(if (e == s) 1 else 0)}")
      }
    }
  }
}