# Prime Factoral Roots

Inspired by digital roots, the prime factoral root of a number is the number that emerges when you take the prime factors of a number, add them together, and repeat the process on the resulting number, continuing until you end up with a prime number (which has itself as its only prime factor, and is thus its own prime factoral root). The prime factoral root of 4 is 4, as 2*2=2+2, and this is the only non-prime prime factoral root of an integer greater than 1 (which is another special case, as it has no prime factors). The OEIS sequence formed by prime factoral roots is A029908.

For example, the prime factoral root of 24 is:

24=2*2*2*3

2+2+2+3=9=3*3

3+3=6=2*3

2+3=5, and the only prime factor of 5 is 5.  Therefore, the prime factoral root of 24 is 5.


Write a program or function that finds the prime factoral root of an input integer.

## Input:

An integer, input through any reasonable method, between 2 and the largest integer your language will support (inclusive). Specifically choosing a language that has an unreasonably low maximum integer size is not allowed (and also violates this standard loophole)

## Output:

An integer, the prime factoral root of the input.

## Test Cases:

4   -> 4
24  -> 5
11  -> 11
250 -> 17


## Scoring:

This is , lowest score in bytes wins!

• Can you add 4 in the test cases, since it's an exception and it's easy to forget about it while testing an answer? Oct 4, 2017 at 11:26
• Do we have to output 1 for 1? Oct 4, 2017 at 11:36
• @someone according to the linked OEIS sequence, it should output 0 for 1 Oct 4, 2017 at 11:55
• @someone The challenge states that the input will be at least 2. Oct 4, 2017 at 13:21
• @someone Sorry for being off for a while. As Martin said, the challenge specifically says that the input will be greater than one, and therefore behavior when the input is 1 is undefined. Oct 5, 2017 at 1:18

import Data.Numbers.Primes

• =<<((==)=<<)$ Whaaaaaat. Oct 5, 2017 at 4:52 • @icrieverytim I added an explanation. Feel free to ask in the Haskell chat room if you have further questions on how this sorcery works. Oct 5, 2017 at 8:14 # 05AB1E, 3 bytes FÒO  Try it online! Explanations: FÒO F Loops <input> times + 1 Ò List of prime factors w/ duplicates O Total sum of the list -- implicit output  • This seems to fail for 4. Oct 4, 2017 at 11:09 • @Shaggy fixed while saving 2 bytes Oct 4, 2017 at 11:21 • Does this make anyone trying to beat this a FÒO-fighter? Oct 4, 2017 at 14:57 • At least it wasn't FOObar. Oct 4, 2017 at 18:03 # Husk, 4 bytes ω(Σp  Try it online! Explanation: ω( -- apply the following function until the result no longer changes (fixpoint) Σ -- sum p -- the list of primefactors  # Pyth, 3 bytes usP  Try it here. Explanation: usPGQ The trailing GQ is implicit PG Get prime factors s Sum u Q Repeat until returned value no longer unique starting with the input  • Did you forget to update your explanation? Oct 6, 2017 at 1:56 • @MCMastery No, the code and the explanation are the same. The trailing GQ is implicit Oct 6, 2017 at 6:35 • @MCMastery what i cri everytim said Oct 6, 2017 at 11:21 # Python 2, 84 bytes f=lambda n,d=2:n>1and(n%d and f(n,d+1)or d+f(n/d)) i=input() exec'i=f(i);'*i print i  Try it online! • This may be a pretty dumb question, but how does f=lambda n,d=2:n>1and(n%d and f(n,d+1)or d+f(n/d)) work? I've never programmed in Python (mainly Java and C#), so I'm unsure what the result of this function is. Does this function modify the input n and return it afterwards, or is it similar to a boolean where n>1and(n%d and f(n,d+1)or d+f(n/d)) is either 0 or 1, or 0 or n, or something else? I'm trying to visualize how a port of this would look like in Java/C#, but I'm unable to because I don't really understand Python lambdas like this in general. Oct 4, 2017 at 14:41 • @KevinCruijssen this is equivalent to n>1 ? (n%d!=0 ? f(n, d+1) : d+f(n/d)) : n>1. In general terms x and y is equivalent to x ? y : x. x and y or z is equivalent to x ? y : z in most cases. – ovs Oct 4, 2017 at 15:06 • @KevinCruijssen a Java port would be something like f=(n,d=2)->n>1?n%d>0?f(n,d+1):d+f(n/d):0. – ovs Oct 4, 2017 at 15:08 • Ah ok. Thanks for the explanation, now it makes a lot more sense. And I remember x and y being x ? y : x from JavaScript as well. Thanks! Oct 4, 2017 at 17:30 # Java 8, 175144142141139 101 bytes n->{for(int i=n;i-->0;)n=f(n,2);return n;};int f(int n,int d){return n>1?n%d<1?f(n/d,2)+d:f(n,d+1):0;}  -38 bytes porting @ovs' Python answer, so make sure to upvote him as well! Try it online. n->{ // Method with integer as both parameter and return-type for(int i=n;i-->0;)// Loop the input n amount of times: n=f(n,2); // Change n that many times by calling the recursive method // with n,2 as parameters return n;} // Then return the potentially modified n as result int f(int n,int d){ // Separated method with 2 integer parameters & integer return // (d is 2 when we initially call this recursive-method) return n>1? // If input n is larger than 1: n%d<1? // If n is divisible by d: f(n/d // Divide n by d ,2) // Do a recursive call with n/d,2 as parameters +d // And add d to its result : // Else: f(n,d+1) // Do a recursive-call with the next d by using n,d+1 as // parameters : // Else: 0;} // Simply return 0  Original 175 144 142 141 139 bytes answer: n->{for(int i,t=n,x;;n=t){for(i=2;i<t;)t=t%i++<1?0:t;if(t>1|n<5)return n;for(t=0,i=1;i++<n;)for(;n%i<1;t+=x)for(n/=x=i;x>9;x/=10)t+=x%10;}}  -1 byte thanks to @Nevay -2 bytes thanks to @ceilingcat Explanation: Try it online. n->{ // Method with integer as both parameter and return-type for(int i, // Index-integer i t=n, // Temp integer t, starting at the input n x; // Temp integer x ; // Loop indefinitely: n=t){ // After every iteration, replace n with the value t for(i=2;i<t;) // Inner loop i in the range [2,t): t=t%i++<1? // If t is divisible by i: 0 // Set t to 0 : // Else: t; // Leave t the same if(t>1 // If t is not 0 or 1 (it means it's a prime), |n<5) // or if n is below 5 (for edge-cases n=1 and n=4) return n; // Return n as result for(t=0, // Reset t to 0 i=1; // Reset i to 1 i++<n;) // Inner loop i in the range (2,n]: for(;n%i<1; // Inner loop as long as n is divisible by i: t+=x) // After every iteration: Increase t by x for(n/=x=i; // Reset x to i // And divide n by i x>9; // Inner loop as long as x contains more than 1 digit: x/=10) // After every iteration, remove the trailing digit of x t+=x%10;}} // Increase t with the trailing digit of x  • +1 for bothering to write an explanation as verbose as if this was a golfing language. Oct 4, 2017 at 12:17 • @someone Thanks! Since someone asked me about an explanation of a Java answer of mine once in the past, I've been adding them to all my answers. :) Oct 4, 2017 at 12:23 • i,t=n,x looks like it belongs in Python, haha Oct 4, 2017 at 14:03 • @ETHproductions Hehe, too bad I still have to add the leading int  (unlike Python). ;) Oct 4, 2017 at 14:15 • You can use i++<n instead of ++i<=n. Oct 4, 2017 at 21:47 # Jelly, 5 bytes ÆfS$¡


Explanations:

Æf    list of prime factors
S   sum
$¡ repeat n times  Try it online! • 5 bytes Oct 4, 2017 at 11:07 ## Retina, 30 bytes {+(\1|\b11+?\B)+$
$1;$#1$* ;  Input and output in unary. Try it online! (Performs decimal/unary conversion for convenience.) ### Explanation {+(\1|\b11+?\B)+$
$1;$#1$*  The { instructs Retina to run the entire program in a loop until a full pass fails to modify the string, i.e. until a fixed point is reached. Consequently, the program itself computes one step of summing the prime factors of the current value. This stage itself computes the prime factorisation of the input. The + is similar to { but loops only this stage until it stops changing the string. The regex tries to match the final run of 1s by repeatedly matching the same substring (i.e. the factor). The way this is done is a bit convoluted due to the forward reference \1. On the first iteration, group 1 hasn't captured anything yet, so \1 fails unconditionally. Instead, we have to match \b11+?\B which is the smallest possible substring that starts at the beginning of the run, contains at least two 1s and doesn't cover the entire run. Subsequent iterations will not be able to use this alternative again, due to the \b. So on all further iterations, we're matching \1, i.e. the same substring over and over again. This process has to hit the end of the string exactly ($) to make sure we've captured and actual divisor. The benefit of using this somewhat tricky approach is that group 1 will have been used exactly n/d times, i.e. what remains after dividing out the divisor d.

We replace this match with d ($1), a separating ; and n/d ($#1$*, which inserts $#1 copies of 1, where $#1 is the number of captures made by group 1). This process stops once the final run in the string is itself a prime, because then the regex no longer matches. ;  All we need to do to sum the primes is to remove all the separators. # Ohm v2, 4 bytes ·ΘoΣ  Try it online! Explanation: ·Θ evaluate the block until the result returned has already been seen Σ sum o the full prime factorization  # Actually, 7 bytes ⌠w♂πΣ⌡Y  Try it online! Explanation: ⌠w♂πΣ⌡Y ⌠ ⌡Y do this until output stops changing (fixed-point combinator) w factor into [prime, exponent] pairs ♂π product of each pair Σ sum of products  # R + pracma, 53 bytes function(n){for(i in 1:n)n=sum(pracma::factors(n)) n}  Try it online! (r-fiddle) R doesn't have a prime factors builtin, but numerous packages (pracma, numbers, etc.) do, so I picked a conveniently short one. # Jelly, 6 bytes This answer uses one of Jelly's many prime factorization builtins, and the quick for repeat until the results are no longer unique. ÆfSµÐL  Try it online! • I think you've been outgolfed but, given your approach, I'm uncertain whether that answer works Oct 4, 2017 at 11:10 • @cairdcoinheringaahing I've just checked his answer (or rather, the Python equivalent) from 1 to 100000 and it works. I think 1 is the only case where the number of steps needed is equal to n (which is fine; with 1 we only need to run it once), and there don't seem to be any cases where the number of steps is greater than n (i.e. there don't seem to be any counterexamples). Ah well, I've been outgolfed :D Oct 4, 2017 at 11:25 • Well, it happens. Although +1 for being the exact same code I thought of when I saw this challenge Oct 4, 2017 at 11:27 • The sum of prime factors of n is always less than or equal to n, which makes it pretty easy to prove that n is always more than enough. Oct 5, 2017 at 1:37 # MATL, 6 bytes Uses scottinet's idea of looping more times than needed. Thanks also to Shaggy for a pointing out a mistake, now corrected. t:"Yfs  Try it online! ### Explanation t % Take input (implicit). Duplicate :" % Do the following that many times Yf % Array of prime factors s % Sum of array % End (implicit). Display (implicit)  • This seems to fail for 4. Oct 4, 2017 at 11:11 • @Shaggy Thanks! Working on that Oct 4, 2017 at 11:11 • @Shaggy Solved now Oct 4, 2017 at 11:16 # PowerShell, 124 bytes function f($a){for($i=2;$a-gt1){if(!($a%$i)){$i;$a/=$i}else{$i++}}}
for($x=$args[0];$l-ne$x){$l=$x;$x=(f($x))-join'+'|iex}$x  Try it online! PowerShell doesn't have any prime factorization built-ins, so this uses code from my answer on Prime Factors Buddies (the top line) to perform the factorization calculations. The second line is the meat of this program. We take input from $args into $x, then for loop until $l is -notequal to $x. (The first iteration, $l is $null and $x is an integer, so we'll loop at least once).

Inside the loop, we set our $l =$x to determine if we've hit the end of the loop or not. Then we get the factors of $x with f($x), -join those together with + and |iex them (short for Invoke-Expression and similar to eval). That's stored back into $x. Thus, we've hit the "end" where the prime factorization summed together is back to itself. Then, we simply place $x on the pipeline and output is implicit.

# Mathematica, 35 bytes

#//.x_:>Tr[1##&@@@FactorInteger@x]&


Try it online!

(Mathics does not support Tr. I have to implement it manually)

• 1##& is short for Times and FixedPoint can almost always be shortened with //.: #//.x_:>Tr[1##&@@@FactorInteger@x]& Oct 4, 2017 at 10:53
• @MartinEnder Thanks! I should have already known about Times, but I've not known about the FixedPoint trick. Oct 4, 2017 at 11:06
• Your code is written in Mathematica. This is not a Mathics function. You should either change the language name to Mathematica or Tr to Total Oct 4, 2017 at 11:36
• @{no one} Sorry, language name (Mathics) was a mistake. {i cri evritime} fixed that. Oct 4, 2017 at 12:28
• – user45941
Oct 4, 2017 at 13:56

# Ruby, 63 bytes

->n{n.times{n=n.prime_division.map{|x|x.reduce:*}.sum};n}


Try it online!

Uses the -rprime flag for +6 bytes to make use of Prime#prime_division.

prime_division returns pairs of [prime, exponent] (for example, for 24 we have the factors [2, 2, 2, 3] so it gives [[2, 3], [3, 1]]) so in each step we just multiply the members of those pairs together and sum the results.

# Javascript (ES6), 63 bytes

f=n=>(q=(p=(m,x)=>m<x?0:m%x?p(m,x+1):x+p(m/x,x))(n,2))^n?f(q):q
<input id=i type=number min=0 value=0 oninput="o.innerText=f(i.value)">
<p id=o></p>

## Ungolfed:

f=n=>(                  // Recursive function f
p=(m,x=2)=>(        //   Recursive function p, used to sum prime factors
m<x?            //     If m (the number to be factored) is less than x (the current
0           //     iteration), return 0
:m%x?           //     Else if m doesn't divide x
p(m,x+1)    //     run the next iteration
:               //     Else (if m divides x)
x+p(m/x,x)  //     Divide m by x and repeat the current iteration
),
q=p(n),             //   Set q to the sum of the prime factors of n
q^n?                //   If q != n then
f(q)            //     repeat f with q
:                   //   else
q               //     return q
)


# Factor, 33 bytes

[ [ factors Σ ] to-fixed-point ]


Try it online!

• to-fixed-point Apply a quotation to an object until it stops changing.
• factors Σ Sum of prime factors.