Prime Factoral Roots

14

Zainspirowany pierwiastkami cyfrowymi, główny faktorowy pierwiastek z liczby to liczba, która pojawia się, gdy weźmiesz czynniki pierwsze liczby, zsumujesz je i powtórzysz proces na wynikowej liczbie, kontynuując aż do uzyskania liczby pierwszej ( który ma sam w sobie jedyny główny czynnik, a zatem jest swoim głównym pierwiastkiem faktorowym). Pierwotny pierwiastek faktoralny z 4 wynosi 4, ponieważ 2 * 2 = 2 + 2, i jest to jedyny pierwszoplanowy pierwiastkowy pierwiastek z liczby całkowitej większej niż 1 (co jest innym szczególnym przypadkiem, ponieważ nie ma żadnych czynników pierwszych). Sekwencja OEIS utworzona z głównych pierwiastków faktoralnych to A029908 .

Na przykład główny faktoralny rdzeń 24 to:

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.  

Twoje zadanie:

Napisz program lub funkcję, która znajdzie główny faktoralny rdzeń wejściowej liczby całkowitej.

Wejście:

Liczba całkowita, wprowadzana dowolną rozsądną metodą, od 2 do największej liczby całkowitej obsługiwanej przez Twój język (włącznie). W szczególności wybór języka, który ma nieproporcjonalnie niski maksymalny rozmiar liczby całkowitej, jest niedozwolony (a także narusza tę standardową lukę )

Wynik:

Liczba całkowita, główny faktorowy pierwiastek wejściowy.

Przypadki testowe:

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

Punktacja:

To jest , najniższy wynik w bajtach wygrywa!

Gryf
źródło
3
Czy można dodać 4do przypadków testowych, ponieważ jest to wyjątek i łatwo o nim zapomnieć podczas testowania odpowiedzi?
scottinet
Czy musimy wyprowadzać 1 na 1?
mój zaimek to monicareinstate
@someone according to the linked OEIS sequence, it should output 0 for 1
scottinet
2
@someone The challenge states that the input will be at least 2.
Martin Ender
@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.
Gryphon

Odpowiedzi:

15

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
scottinet
źródło
This seems to fail for 4.
Shaggy
1
@Shaggy fixed while saving 2 bytes
scottinet
10
Does this make anyone trying to beat this a FÒO-fighter?
steenbergh
At least it wasn't FOObar.
Magic Octopus Urn
14

Haskell, 61 bytes

import Data.Numbers.Primes
until=<<((==)=<<)$sum.primeFactors

Try it online!

Explanation

until=<<((==)=<<) takes a function f and applies it to input x until a fix point is reached, that is f x equals x. primeFactors returns the list of prime factors of a number, sum yields the sum of a list of numbers.

But wait, why does until=<<((==)=<<) the job and looks so weird?

If we assume f=sum.primeFactors, a more natural definition would be until(\x->f x==x)f, because until takes a predicate (a function which returns a boolean), a function which has the same input and return type (e.g. Int -> Int) and value of this type, and then applies the function to the value until the predicate is fulfilled.

until(\x->f x==x)f is the same as until(\x->(==)(f x)x)f, and as it holds that g (h x) x is the same as (g=<<h)x, we get until(\x->((==)=<<f)x)f. After Eta conversion, this becomes until((==)=<<f)f. But if we now treat (==)=<< as a function which is applied to f, we can see that until(((==)=<<)f)f is again of the form g (h x) x, with g=until, h=((==)=<<) and x=f, so it can be rewritten to (until=<<((==)=<<))f. Using the $ operator to get rid of the outer parentheses and substituting f with sum.primeFactors yields the solution from above.

Laikoni
źródło
4
=<<((==)=<<)$ Whaaaaaat.
totallyhuman
2
@icrieverytim I added an explanation. Feel free to ask in the Haskell chat room if you have further questions on how this sorcery works.
Laikoni
5

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
Laikoni
źródło
4

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
Erik the Outgolfer
źródło
Did you forget to update your explanation?
MCMastery
1
@MCMastery No, the code and the explanation are the same. The trailing GQ is implicit
totallyhuman
@MCMastery what i cri everytim said
Erik the Outgolfer
4

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!

ovs
źródło
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.
Kevin Cruijssen
1
@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
1
@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
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!
Kevin Cruijssen
4

Java 8, 175 144 142 141 bytes

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;n/=i,t+=x)for(x=i;x>9;x/=10)t+=x%10;}}

-1 byte thanks to @Nevay.

Unlike single bytes in some of the golfing languages, Java is pretty verbose for prime-checks, prime-factors, digit-sums, and such, so I guess less than 200 isn't too shabby.
Can most likely still be golfed by combining loops and not using a separated recursive method for the digit sum.

Explanation:

Try it here.

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 (1) indefinitely
      n=t){         //    After every iteration, replace `n` with the value `t`
    for(i=2;        //   Reset `i` to 2
        i<t;        //   Inner loop (2) from 2 to `t` (exclusive)
        t=t%i++<1?  //    If `t` is divisible by `i`:
           0        //     Set `t` to 0
          :         //    Else:
           t        //     Leave `t` the same
    );              //   End of inner loop (2)
    if(t>1          //   If `t` is not 0 (it means it's a prime),
       |n<5)        //   or if `n` is below 5 (for edge-cases `4` and 'prime' `1`)
      return n;     //    Return `n` as result
    for(t=0,        //   Reset `t` to 0
        i=1;        //   Reset `i` to 1
        i++<n;)     //   Inner loop (3) from 2 to `n` (inclusive)
      for(;n%i<1;   //    Inner loop (4) as long as `n` is divisible by `i`
          n/=i,     //      After every iteration: Divide `n` by `i`,
          t+=x)     //      and increase `t` by `x`
        for(x=i;    //     Reset `x` to `i`
            x>9;    //     Inner loop (5) as long as `x` contains more than 1 digit
            x/=10)  //       After every iteration, remove the trailing digit
          t+=n%10;  //      Increase `t` with the trailing digit of `n`
                    //     End of inner loop (5) (implicit / single-line body)
                    //    End of inner loop (4) (implicit / single-line body)
                    //   End of inner loop (3) (implicit / single-line body)
  }                 //  End of loop (1)
}                   // End of method
Kevin Cruijssen
źródło
6
+1 for bothering to write an explanation as verbose as if this was a golfing language.
my pronoun is monicareinstate
@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. :)
Kevin Cruijssen
i,t=n,x looks like it belongs in Python, haha
ETHproductions
@ETHproductions Hehe, too bad I still have to add the leading int (unlike Python). ;)
Kevin Cruijssen
You can use i++<n instead of ++i<=n.
Nevay
3

Jelly, 5 bytes

ÆfS$¡

Explanations:

Æf    list of prime factors
  S   sum
   $¡ repeat n times

Try it online!

my pronoun is monicareinstate
źródło
1
5 bytes
caird coinheringaahing
3

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.

Martin Ender
źródło
3

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
Cinaski
źródło
2

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
Mego
źródło
2

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.

Giuseppe
źródło
1

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!

Sherlock9
źródło
I think you've been outgolfed but, given your approach, I'm uncertain whether that answer works
caird coinheringaahing
@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
Sherlock9
Well, it happens. Although +1 for being the exact same code I thought of when I saw this challenge
caird coinheringaahing
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.
Chris
1

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)
Luis Mendo
źródło
This seems to fail for 4.
Shaggy
@Shaggy Thanks! Working on that
Luis Mendo
@Shaggy Solved now
Luis Mendo
1

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.

AdmBorkBork
źródło
0

Mathematica, 35 bytes

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

Try it online!

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

user202729
źródło
4
1##& is short for Times and FixedPoint can almost always be shortened with //.: #//.x_:>Tr[1##&@@@FactorInteger@x]&
Martin Ender
@MartinEnder Thanks! I should have already known about Times, but I've not known about the FixedPoint trick.
user202729
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
J42161217
@{no one} Sorry, language name (Mathics) was a mistake. {i cri evritime} fixed that.
user202729
0

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.

Snack
źródło
0

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
)
Herman L
źródło
0

Java 8, 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>0?f(n,d+1):d+f(n/d,2):0;}

Port of @ovs's amazing Python 2 answer.

Explanation:

Try it here.

n->{                  // Method with integer as both parameter and return-type
  for(int i=n;i-->0;  //  Loop the input amount of times
    n=f(n,2)          //   And change `n` that many times with a separate method call
  );                  //  End of loop
  return n;           //  Then return the integer `n` as result
}                     // End of method

int f(int n,int d){   // Separated method with 2 integer parameters and integer return-type
                      // (`d` is 2 when we initially call this recursive-method)
  return n>1?         //  If input `n` is larger than 1:
    n%d>0?            //   And it's not divisible by `d`:
     f(n,d+1)         //    Do a recursive-call with `n, d+1`
    :                 //   Else:
     d                //    Sum `d` with
      +f(n/d,2)       //    a recursive call with `n/d, 2`
   :                  //  Else:
    0;                //   Simply return 0
}                     // End of separated method
Kevin Cruijssen
źródło