26
\$\begingroup\$

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 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
\$\endgroup\$
1

25 Answers 25

15
\$\begingroup\$

05AB1E, 3 bytes

ΔÒJ

Try it online!

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

\$\endgroup\$
1
  • \$\begingroup\$ WOW that is so short! \$\endgroup\$ Commented Apr 15, 2021 at 11:52
8
\$\begingroup\$

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
\$\endgroup\$
6
\$\begingroup\$

APL(Dyalog Extended), 12 bytes SBCS

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

Try it on APLgolf!

A dfn submission which takes a single argument.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Lol, this was mine {⍎⊃,/⍕¨3⌂pco⍵}⍣= but apparently pco only works with 32 bit integers. \$\endgroup\$ Commented Apr 14, 2021 at 21:28
5
\$\begingroup\$

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

\$\endgroup\$
2
  • \$\begingroup\$ @cairdcoinheringaahing Nice one - thanks! Please post suggestions as comments not edits. \$\endgroup\$
    – Noodle9
    Commented Apr 15, 2021 at 19:44
  • \$\begingroup\$ It looks like changing the condition to $10-$20 also works. Additionally, you can combine the two sed substitutions into one to save some more. \$\endgroup\$
    – user41805
    Commented Sep 10, 2021 at 8:12
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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.
\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

Ohm v2, 4 bytes

·ΘoJ

Try it online!

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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\$.

\$\endgroup\$
3
\$\begingroup\$

R + numbers, 74 73 bytes

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

Try it online!

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
1
  • \$\begingroup\$ 10 bytes \$\endgroup\$
    – Shaggy
    Commented Apr 19, 2021 at 9:09
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

Wolfram Language (Mathematica), 60 bytes

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

Try it online!

-14 bytes from @att

\$\endgroup\$
1
  • \$\begingroup\$ 60 bytes \$\endgroup\$
    – att
    Commented Apr 14, 2021 at 16:45
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
  • \$\begingroup\$ the command factor is contained in linux only. your "lazy port" does not work with windows powershell \$\endgroup\$
    – mazzy
    Commented Apr 15, 2021 at 4:22
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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)}")
      }
    }
  }
}

\$\endgroup\$
1
1
\$\begingroup\$

Uiua SBCS, 13 bytes

⍥(⋕/◇⊂°⋕°/×)∞

Try it!

⍥(⋕/◇⊂°⋕°/×)∞
⍥(         )∞  # to fixed point
        °/×    # factors
      °⋕       # unparse
   /◇⊂         # join all
  ⋕            # parse
\$\endgroup\$
1
\$\begingroup\$

APL(NARS), 54 chars

⎕fpc←10000⋄g←{¯2↓1⍕{0π⍵:⍵⋄∇{10x⊥⍎¨⍵}↑,/⍕¨k[⍋k]⊣k←π⍵}⍵}

The function is a little more long because not all number exit ordered from function π, example

   π11613496501723   
97 917327 130517 

see 917327>130517. I use {10x⊥⍎¨⍵} in place of just ⍎ for problems I don't remember, ({10v⊥⍎¨⍵} not seems right too) and "¯2↓1" because output result with number.0, but somethig easy resolvible.

It is enought fast, the output below in 2 seconds (I not ceck all below numbers only some ones)

   ⍪m,¨g¨m←(2..100)∼49 77 80 96   
 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
\$\endgroup\$
1
\$\begingroup\$

Bash, 99 bytes

f(){
a=($(factor $1 | sed 's/^.*: //'))
[ ${#a[@]} -ne 1 ] && f $(tr -d ' '<<<${a[@]}) || echo $a
}

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.