Inspirée des racines numériques, la racine factorielle principale d'un nombre est le nombre qui émerge lorsque vous prenez les facteurs premiers d'un nombre, les additionnez et répétez le processus sur le nombre résultant, en continuant jusqu'à ce que vous obteniez un nombre premier ( qui a lui-même comme seul facteur premier, et est donc sa propre racine factorielle). La racine factorielle première de 4 est 4, comme 2 * 2 = 2 + 2, et c'est la seule racine factorielle première non première d'un entier supérieur à 1 (ce qui est un autre cas spécial, car il n'a pas de facteurs premiers). La séquence OEIS formée par les racines factorielles principales est A029908 .

Par exemple, la racine factorielle principale de 24 est:

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.  

Ta tâche:

Écrivez un programme ou une fonction qui trouve la racine factorielle principale d'un entier en entrée.

Contribution:

Un entier, entré par toute méthode raisonnable, entre 2 et le plus grand entier pris en charge par votre langue (inclus). Plus précisément, le choix d'une langue dont la taille maximale maximale est déraisonnablement faible n'est pas autorisé (et viole également cette échappatoire standard )

Production:

Un entier, la racine factorielle principale de l'entrée.

Cas de test:

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

Notation:

C'est le code-golf , le score le plus bas en octets gagne!

05AB1E , 3 octets

FÒO

Essayez-le en ligne!

Explications:

FÒO   
F    Loops <input> times + 1
 Ò   List of prime factors w/ duplicates
  O  Total sum of the list
     -- implicit output

Haskell , 61 octets

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

Essayez-le en ligne!

Explication

until=<<((==)=<<)prend une fonction fet l'applique à l'entrée xjusqu'à ce qu'un point fixe soit atteint, c'est-à-dire f xégal x. primeFactorsrenvoie la liste des facteurs premiers d'un nombre, sumdonne la somme d'une liste de nombres.

Mais attendez, pourquoi until=<<((==)=<<) le travail et si étrange?

Si nous supposons f=sum.primeFactors, une définition plus naturelle serait until(\x->f x==x)f, car untilprend un prédicat (une fonction qui renvoie un booléen), une fonction qui a le même type d'entrée et de retour (par exemple Int -> Int) et la même valeur de ce type, puis applique la fonction à la jusqu'à ce que le prédicat soit rempli.

until(\x->f x==x)fest le même que until(\x->(==)(f x)x)f, et comme il g (h x) xest le même que (g=<<h)x, nous obtenons until(\x->((==)=<<f)x)f. Après la conversion Eta , cela devient until((==)=<<f)f. Mais si nous traitons maintenant (==)=<<comme une fonction qui est appliquée à f, nous pouvons voir que until(((==)=<<)f)fc'est encore de la forme g (h x) x, avec g=until, h=((==)=<<)et x=f, donc elle peut être réécrite en(until=<<((==)=<<))f . L'utilisation de l' $opérateur pour se débarrasser des parenthèses externes et le remplacement fpar sum.primeFactorsdonne la solution d'en haut.

Husk , 4 octets

ω(Σp

Essayez-le en ligne!

Explication:

ω(   -- apply the following function until the result no longer changes (fixpoint)
  Σ  -- sum
   p -- the list of primefactors

Pyth , 3 octets

usP

Essayez-le ici.

Explication:

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

Python 2 , 84 octets

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

Essayez-le en ligne!

Java 8, 175 144 142 141 141 octets

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 octet grâce à @Nevay .

Contrairement aux octets uniques dans certains des langages de golf, Java est assez verbeux pour les vérifications de prime, les facteurs premiers, les sommes numériques, etc., donc je suppose que moins de 200 n'est pas trop minable.
Peut très probablement encore être joué en combinant des boucles et en n'utilisant pas une méthode récursive séparée pour la somme des chiffres .

Explication:

Essayez-le ici.

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

Gelée , 5 octets

ÆfS$¡

Explications:

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

Essayez-le en ligne!

Rétine , 30 octets

{+`(\1|\b11+?\B)+$
$1;$#1$*
;

Entrée et sortie unaires .

Essayez-le en ligne! (Effectue une conversion décimale / unaire pour plus de commodité.)

Explication

{+`(\1|\b11+?\B)+$
$1;$#1$*

Le programme {demande à Retina d'exécuter le programme entier en boucle jusqu'à ce qu'un passage complet ne parvienne pas à modifier la chaîne, c'est-à-dire jusqu'à ce qu'un point fixe soit atteint. Par conséquent, le programme lui-même calcule une étape de sommation des facteurs premiers de la valeur actuelle.

Cette étape elle-même calcule la factorisation première de l'entrée. Le +est similaire à {mais boucle uniquement cette étape jusqu'à ce qu'il arrête de changer la chaîne. La regex essaie de faire correspondre la séquence finale de 1s en faisant correspondre à plusieurs reprises la même sous-chaîne (c'est-à-dire le facteur). La façon dont cela est fait est un peu compliquée en raison de la référence directe \1. Lors de la première itération, le groupe 1n'a encore rien capturé, \1échoue donc sans condition. Au lieu de cela, nous devons faire correspondre \b11+?\Bquelle est la plus petite sous-chaîne possible qui commence au début de l'exécution, en contient au moins deux , c'est-à-dire la même sous-chaîne encore et encore. Ce processus doit frapper la fin de la chaîne exactement (1 s et ne couvre pas l'ensemble de l'exécution. Les itérations suivantes ne pourront plus utiliser cette alternative, en raison du \b. Donc, pour toutes les autres itérations, nous faisons correspondre\1$ ) pour s'assurer que nous avons capturé et diviseur réel. L'avantage d'utiliser cette approche quelque peu délicate est que le groupe 1aura été utilisé exactement n / d fois, c'est-à-dire ce qui reste après la division du diviseur d .

Nous remplaçons cette correspondance par d ( $1), une séparation ;et n / d ( $#1$*, qui insère des $#1copies de 1, où $#1est le nombre de captures effectuées par groupe 1).

Ce processus s'arrête une fois que l'exécution finale de la chaîne est elle-même un nombre premier, car alors l'expression régulière ne correspond plus.

;

Tout ce que nous devons faire pour additionner les nombres premiers est de supprimer tous les séparateurs.

Ohm v2 , 4 octets

·ΘoΣ

Essayez-le en ligne!

Explication:

·Θ    evaluate the block until the result returned has already been seen
   Σ  sum
  o   the full prime factorization

En fait , 7 octets

⌠w♂πΣ⌡Y

Essayez-le en ligne!

Explication:

⌠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 octets

function(n){for(i in 1:n)n=sum(pracma::factors(n))
n}

Essayez-le en ligne! (r-violon)

R n'a pas de facteurs premiers BUILTIN, mais de nombreux forfaits ( pracma, numbers, etc.) faire, donc j'ai choisi un court commodément.

Gelée , 6 octets

Cette réponse utilise l'un des nombreux prédéfinis de factorisation de Jelly, et le rapide pour repeat until the results are no longer unique.

ÆfSµÐL

Essayez-le en ligne!

MATL, 6 bytes

Utilise l'idée de scottinet de boucler plus de fois que nécessaire. Merci également à Shaggy d' avoir signalé une erreur, maintenant corrigée.

t:"Yfs

Essayez-le en ligne!

Explication

t       % Take input (implicit). Duplicate
:"      % Do the following that many times
  Yf    %   Array of prime factors
  s     %   Sum of array
        % End (implicit). Display (implicit)

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)

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
)

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