Inspiré par cette question sur les mathématiques .

Le problème

Soit nun nombre naturel ≥ 2. Prenez le plus grand diviseur de n- qui est différent de nlui-même - et soustrayez-le n. Répétez jusqu'à ce que vous obtenez 1.

La question

Combien de pas faut-il pour atteindre 1un nombre donné n ≥ 2.

Exemple détaillé

Let n = 30.

Le plus grand diviseur de:

1.   30 is 15  -->  30 - 15 = 15
2.   15 is  5  -->  15 -  5 = 10
3.   10 is  5  -->  10 -  5 =  5
4.    5 is  1  -->   5 -  1 =  4
5.    4 is  2  -->   4 -  2 =  2
6.    2 is  1  -->   2 -  1 =  1

Il faut 6 étapes pour y arriver 1.

Contribution

• L'entrée est un entier n, où n ≥ 2.
• Votre programme doit prendre en charge la saisie jusqu’à la valeur entière maximale de la langue.

Sortie

• Indiquez simplement le nombre d'étapes, comme 6.
• Les espaces blancs ou les nouvelles lignes sont acceptables.

Exemples

f(5)        --> 3
f(30)       --> 6
f(31)       --> 7
f(32)       --> 5
f(100)      --> 8
f(200)      --> 9
f(2016^155) --> 2015

Exigences

• Vous pouvez obtenir des entrées à partir d’ STDINarguments de ligne de commande, de paramètres de fonction ou de l’équivalent le plus proche.
• Vous pouvez écrire un programme ou une fonction. S'il s'agit d'une fonction anonyme, veuillez inclure un exemple expliquant comment l'invoquer.
• C'est la réponse code-golf, donc la réponse la plus courte en octets est gagnante.
• Les failles standard sont interdites.

Cette série est également disponible sur OEIS: A064097

Un quasi-logarithme défini inductivement par a(1) = 0et a(p) = 1 + a(p-1)si pest premier et a(n*m) = a(n) + a(m)si m,n > 1.

Gelée , 9 octets

ÆṪÐĿÆFL€S

Essayez-le en ligne! ou vérifier tous les cas de test .

Contexte

La définition de la séquence A064097 implique que

Par la formule du produit d'Euler

où φ désigne la fonction totale d'Euler et p ne varie que sur les nombres premiers.

En combinant les deux, on déduit la propriété

où ω désigne le nombre de facteurs premiers distincts de n .

En appliquant la formule résultante k + 1 fois, où k est suffisamment grand pour que φ ^{k + 1} (n) = 1 , on obtient

De cette propriété, on obtient la formule

où la dernière égalité est vraie parce que ω (1) = 0 .

Comment ça fonctionne

ÆṪÐĿÆFL€S  Main link. Argument: n

  ÐĿ       Repeatedly apply the link to the left until the results are no longer
           unique, and return the list of unique results.
ÆṪ           Apply Euler's totient function.
           Since φ(1) = 1, This computes φ-towers until 1 is reached.
    ÆF     Break each resulting integer into [prime, exponent] pairs.
      L€   Compute the length of each list.
           This counts the number of distinct prime factors.
        S  Add the results.

05AB1E , 13 à 11 octets

Code:

[DÒ¦P-¼D#]¾

Explication:

[        ]   # An infinite loop and...
       D#        break out of the loop when the value is equal to 1.
 D           # Duplicate top of the stack (or in the beginning: duplicate input).
  Ò          # Get the prime factors, in the form [2, 3, 5]
   ¦         # Remove the first prime factor (the smallest one), in order to get 
               the largest product.
    P        # Take the product, [3, 5] -> 15, [] -> 1.
     -       # Substract from the current value.
      ¼      # Add one to the counting variable.
          ¾  # Push the counting variable and implicitly print that value.

Utilise le codage CP-1252 . Essayez-le en ligne! .

Pyth, 11 octets

fq1=-Q/QhPQ

Suite de tests

Une boucle simple qui répète jusqu'à la vérité.

Explication:

fq1=-Q/QhPQ
               Implicit: Q = eval(input())
f              Apply the following function until it is truthy,
               incrementing T each time starting at 1:
         PQ    Take the prime factorization of Q
        h      Take its first element, the smallest factor of Q
      /Q       Divide Q by that, giving Q's largest factor
    -Q         Subtract the result from Q
   =           Assign Q to that value
 q1            Check if Q is now 1.

Python 2, 50 49 octets

f=lambda n,k=1:2/n or n%(n-k)and f(n,k+1)or-~f(k)

Cela ne va pas finir bientôt ce dernier cas de test ...

Alternativement, voici un 48 octets qui renvoie Trueau lieu de 1pour n=2:

f=lambda n,k=1:n<3or n%(n-k)and f(n,k+1)or-~f(k)

Gelée , 10 octets

ÆfḊPạµÐĿi2

Essayez-le en ligne! ou vérifier la plupart des cas de test . Les derniers cas de test se terminent rapidement localement.

Comment ça fonctionne

ÆfḊPạµÐĿi2  Main link. Argument: n (integer)

Æf          Factorize n, yielding a list of primes, [] for 1, or [0] for 0.
  Ḋ         Dequeue; remove the first (smallest) element.
   P        Take the product.
            This yields the largest proper divisor if n > 1, 1 if n < 2.
    ạ       Yield the abs. value of the difference of the divisor (or 1) and n.
     µ      Convert the chain to the left into a link.
      ÐĿ    Repeatedly execute the link until the results are no longer unique.
            Collect all intermediate results in a list.
            For each starting value of n, the last results are 2 -> 1 -> 0 (-> 1).
        i2  Compute the 1-based index of 2.

Rétine , 12

• 14 octets enregistrés grâce à @ MartinBüttner

(1 +) (? = \ 1 + $)

Cela suppose une entrée donnée en unaire et une sortie donnée en décimal. Si cela n'est pas acceptable, nous pouvons le faire pour 6 octets de plus:

Rétine , 18

• 8 octets enregistrés grâce à @ MartinBüttner

. +
$ *
(1 +) (? = \ 1 + $)

Essayez-le en ligne - 1ère ligne ajoutée pour exécuter tous les tests en une fois.

Malheureusement, cela utilise unaire pour les calculs, de sorte que la saisie de 2016 ¹⁵⁵ n'est pas pratique.

• La première étape (2 lignes) convertit simplement l’entrée décimale en unaire en chaîne de 1s
• La deuxième étape (1 ligne) calcule le facteur le plus important de n en utilisant des groupes de correspondance de regex et recherche-le et le soustrait efficacement de n. Cette expression régulière correspond autant de fois que nécessaire pour réduire le nombre autant que possible. Le nombre de correspondances de regex correspond au nombre d'étapes et est généré par cette étape.

Pyth - 15 14 13 octets

Un boîtier spécial 1me tue vraiment.

tl.u-N/Nh+PN2

Essayez-le en ligne ici .

tl                One minus the length of
 .u               Cumulative fixed point operator implicitly on input
  -N              N -
   /N             N /
    h             Smallest prime factor
     +PN2         Prime factorization of lambda var, with two added to work with 1

JavaScript (ES6), * 44 38

Éditer 6 octets sauvés grâce @ l4m2

(* 4 frappés, c'est encore 4)

Fonction récursive

f=(n,d=n)=>n>1?n%--d?f(n,d):f(n-d)+1:0

Moins joué au golf

f=(n, d=n-1)=>{
  if (n>1)
    if(n % d != 0)
      return f(n, d-1) // same number, try a smaller divisor
    else
      return f(n-d)+1  // reduce number, increment step, repeat
  else
    return 0
}

Tester

f=(n,d=n)=>n>1?n%--d?f(n,d):f(n-d)+1:0

console.log=x=>O.textContent+=x+'\n';

[5,30,31,32,100,200].forEach(x=>console.log(x+' -> '+f(x)))

<pre id=O></pre>

Mathematica, 36 octets

f@1=0;f@n_:=f[n-Divisors[n][[-2]]]+1

Une fonction non nommée prend les mêmes octets:

If[#<2,0,#0[#-Divisors[#][[-2]]]+1]&

Ceci est une implémentation très simple de la définition en tant que fonction récursive.

Octave, 59 58 55 octets

function r=f(x)r=0;while(x-=x/factor(x)(1));r++;end;end

Mis à jour grâce à Stewie Griffin, économisant 1 octet

Mise à jour supplémentaire, enregistrement de trois octets supplémentaires en utilisant le résultat de la factorisation dans la vérification en cours.

Échantillons:

octave:41> f(5)
ans =  3
octave:42> f(30)
ans =  6
octave:43> f(31)
ans =  7
octave:44> f(32)
ans =  5
octave:45> f(100)
ans =  8
octave:46> f(200)
ans =  9

Haskell, 59 octets

f 1=0;f n=1+(f$n-(last$filter(\x->n`mod`x==0)[1..n`div`2]))

Usage:

Prelude> f 30
Prelude> 6

Cela peut être un peu inefficace pour les grands nombres en raison de la génération de la liste.

Julia, 56 50 45 39 octets

f(n)=n>1&&f(n-n÷first(factor(n))[1])+1

C'est une fonction récursive qui accepte un entier et retourne un entier.

Ungolfed:

function f(n)
    if n < 2
        # No decrementing necessary
        return 0
    else
        # As Dennis showed in his Jelly answer, we don't need to
        # divide by the smallest prime factor; any prime factor
        # will do. Since `factor` returns a `Dict` which isn't
        # sorted, `first` doesn't always get the smallest, and
        # that's okay.
        return f(n - n ÷ first(factor(n))[1]) + 1
    end
end

Essayez-le en ligne! (inclut tous les cas de test)

6 octets sauvés grâce à Martin Büttner et 11 grâce à Dennis!

PowerShell v2 +, 81 octets

param($a)for(;$a-gt1){for($i=$a-1;$i-gt0;$i--){if(!($a%$i)){$j++;$a-=$i;$i=0}}}$j

Brutest de force brute.

Prend entrée $a, entre dans une forboucle jusqu’à ce qu’il $asoit inférieur ou égal à 1. Chaque boucle passe par une autre forboucle qui compte à rebours $ajusqu'à ce que nous trouvions un diviseur ( !($a%$i). Au pire, nous trouverons $i=1un diviseur. Lorsque nous le faisons, incrémentez notre compteur $j, soustrayez notre diviseur $a-=$iet définissez-le $i=0pour sortir de la boucle interne. Finalement, nous atteindrons une condition où la boucle externe est fausse (c'est-à-dire qu'elle $aa été atteinte 1), donc output $jet exit.

Attention : Cela prendra beaucoup de temps sur les grands nombres, en particulier les nombres premiers. Une entrée de 100 000 000 prend environ 35 secondes sur mon ordinateur portable Core i5. Edit - vient de tester avec [int]::MaxValue(2 ^ 32-1), et cela a pris ~ 27 minutes. Pas trop mal, je suppose.

Matlab, 58 octets

function p=l(a),p=0;if(a-1),p=1+l(a-a/min(factor(a)));end

Japt , 12 octets (non concurrents)

@!(UµUk Å×}a

Testez-le en ligne! Non compétitif car il utilise un ensemble de fonctionnalités qui ont été ajoutées bien après la publication du défi.

Comment ça fonctionne

@   !(Uµ Uk Å  ×   }a
XYZ{!(U-=Uk s1 r*1 }a
                       // Implicit: U = input integer
XYZ{               }a  // Return the smallest non-negative integer X which returns
                       // a truthy value when run through this function:
         Uk            //   Take the prime factorization of U.
            s1         //   Slice off the first item.
                       //   Now we have all but the smallest prime factor of U.
               r*1     //   Reduce the result by multiplication, starting at 1.
                       //   This takes the product of the array, which is the
                       //   largest divisor of U.
      U-=              //   Subtract the result from U.
    !(                 //   Return !U (which is basically U == 0).
                       //   Since we started at 0, U == 1 after 1 less iteration than
                       //   the desired result. U == 0 works because the smallest
                       //   divisor of 1 is 1, so the next term after 1 is 0.
                       // Implicit: output result of last expression

Cette technique a été inspirée par la réponse 05AB1E . Une version précédente utilisée ²¤(poussez 2, coupez les deux premiers éléments) à la place de Åparce qu’elle a un octet plus court que s1 (espace de fin de note); Je ne me suis rendu compte qu'après coup que parce que cela ajoute un 2 à la fin du tableau et des tranches dès le début , il échoue en fait pour tout nombre composé impair, bien que cela fonctionne pour tous les cas de test donnés.

Python 3, 75, 70 , 67 octets.

g=lambda x,y=0:y*(x<2)or[g(x-z,y+1)for z in range(1,x)if x%z<1][-1]

C'est une solution récursive assez simple. Il faut TRÈS longtemps pour les cas de test à nombre élevé.

> <>, 32 octets

<\?=2:-$@:$/:
1-$:@@:@%?!\
;/ln

Attend le numéro d'entrée n, sur la pile.

Ce programme construit la séquence complète sur la pile. Comme le seul nombre pouvant conduire à 1est 2, la construction de la séquence s'arrête quand 2est atteint. Cela fait également en sorte que la taille de la pile soit égale au nombre d'étapes, plutôt qu'au nombre d'étapes +1.

Ruby, 43 octets

f=->x{x<2?0:1+f[(1..x).find{|i|x%(x-i)<1}]}

Trouvez le plus petit nombre itel que xdivise x-iet recurse jusqu'à ce que nous atteignions 1.

Haskell, 67 octets

Voici le code:

a&b|b<2=0|a==b=1+2&(b-1)|mod b a<1=1+2&(b-div b a)|1<2=(a+1)&b
(2&)

Et voici une des raisons pour lesquelles Haskell est génial:

f = (2&)

(-->) :: Eq a => a -> a -> Bool
(-->) = (==)

h=[f(5)        --> 3
  ,f(30)       --> 6
  ,f(31)       --> 7
  ,f(32)       --> 5
  ,f(100)      --> 8
  ,f(200)      --> 9
  ,f(2016^155) --> 2015
  ]

Oui, dans Haskell, vous pouvez définir -->l'équivalent ==.

Matlab, 107 octets

a=input('');b=factor(a-isprime(a));c=log2(a);while(max(b)>1),b=max(factor(max(b)-1));c=c+1;end,disp(fix(c))

• Non concurrente, ce n'est pas la traduction itérative de ma dernière soumission, c'est juste une autre méthode algerbrique directe, elle résume toutes les traces binaires de tous les facteurs premiers, un peu ambiguë pour illustrer.
• Je vais jouer au golf plus quand j'ai le temps.

MATL, 17 16 octets

`tttYfl)/-tq]vnq

Essayez-le en ligne

Explication

        % Implicitly grab input
`       % Do while loop
    ttt % Make three copies of top stack element
    Yf  % Compute all prime factors
    l)  % Grab the smallest one
    /   % Divide by this to get the biggest divisor
    -   % Subtract the biggest divisor
    t   % Duplicate the result
    q   % Subtract one (causes loop to terminate when the value is 1). This
        % is functionally equivalent to doing 1> (since the input will always be positive) 
        % with fewer bytes
]       % End do...while loop
v       % Vertically concatenate stack contents (consumes entire stack)
n       % Determine length of the result
q       % Subtract 1 from the length
        % Implicitly display result

C99, 62 61 octets

1 octet joué par @Alchymist.

f(a,c,b)long*c,a,b;{for(*c=0,b=a;a^1;a%--b||(++*c,b=a-=b));}  

Appelez en tant que f (x, & y), où x est l'entrée et y la sortie.

Julia, 39 36 octets

\(n,k=2)=n%k>0?n>1&&n\-~k:\(n-n/k)+1

Essayez-le en ligne!

Clojure, 116 104 octets

(fn[n](loop[m n t 1](let[s(- m(last(filter #(=(rem m %)0)(range 1 m))))](if(< s 2)t(recur s (inc t))))))

-12 octets en filtrant une plage pour trouver des multiples, puis en utilisant lastune pour obtenir la plus grande

Solution naïve qui résout fondamentalement le problème décrit par le PO. Malheureusement, trouver le plus grand diviseur prend à lui seul la moitié des octets utilisés. Au moins, je devrais avoir beaucoup d’espace pour jouer au golf à partir d’ici.

Prégolfé et testé:

(defn great-divider [n]
  ; Filter a range to find multiples, then take the last one to get the largest
  (last
     (filter #(= (rem n %) 0)
             (range 1 n))))

(defn sub-great-divide [n]
  (loop [m n
         step 1]
    (let [g-d (great-divider m) ; Find greatest divisor of m
          diff (- m g-d)] ; Find the difference
      (println m " is " g-d " --> " m " - " g-d " = " diff)
      (if (< diff 2)
        step
        (recur diff (inc step))))))

(sub-great-divide 30)

30  is  15  -->  30  -  15  =  15
15  is  5  -->  15  -  5  =  10
10  is  5  -->  10  -  5  =  5
5  is  1  -->  5  -  1  =  4
4  is  2  -->  4  -  2  =  2
2  is  1  -->  2  -  1  =  1
6

Perl 6 , 35 octets

{+({$_ -first $_%%*,[R,] ^$_}...1)}

Essayez-le en ligne!

Comment ça fonctionne

{                                 }   # A bare block lambda.
                    [R,] ^$_          # Construct range from arg minus 1, down to 0.
        first $_%%*,                  # Get first element that is a divisor of the arg.
    $_ -                              # Subtract it from the arg.
   {                        }...1     # Do this iteratively, until 1 is reached.
 +(                              )    # Return the number of values generated this way.

Pyth, 17 16 octets

L?tbhy-b*F+1tPb0

Essayez-le en ligne! (Le y.và la fin est pour l'appel de fonction)

Original 17 octets:

L?tb+1y-b*F+1tPb0

Essayez-le en ligne! (Le y.và la fin est pour l'appel de fonction)

(J'ai effectivement répondu à cette question avec ce programme Pyth.)

Pyke, 11 octets (sans compétition)

D3Phf-oRr;o

Ceci utilise un nouveau comportement dans lequel, si une exception est déclenchée après un goto, elle restaure l'état d'avant le goto (à l'exception des définitions de variable) et se poursuit. Dans ce cas, cela équivaut au code python suivant:

# Implicit input and variable setup
inp = input()
o = 0
# End implicit
try:
    while 1:
        inp -= factors(inp)[0] # If factors is called on the value 1, it returns an empty
                               # list which when the first element tries to be accessed
                               # raises an exception
        o += 1 # Using `o` returns the current value of `o` and increments it
except:
    print o # This in effect gets the number of times the loop went

Tout cela est possible en utilisant Pyke sans construction de boucle while - yay goto!

Essayez-le ici!

JavaScript (ES6), 70 54 octets

f=(n,i=2)=>n<i?0:n%i?f(n,i+1):n>i?f(i)+f(n/i):1+f(n-1)

Implémentation de la formule récursive fournie, mais maintenant mise à jour pour utiliser aussi la récursivité pour trouver le diviseur.

Perl, 57 + 1 ( -pdrapeau) = 58 octets

$n=$_;$n-=$n/(grep!($n%$_),2..$n/2,$n)[0],$\++while$n>1}{

Usage:

> echo 31 | perl -pe '$n=$_;$n-=$n/(grep!($n%$_),2..$n/2,$n)[0],$\++while$n>1}{'

Ungolfed:

while (<>) {
# code above added by -p
    # $_ has input value
    # $\ has undef (or 0)
    my $n = $_;
    while ($n > 1) {
        my $d = 1;
        for (2 .. ($n / 2)) {
            if ($n % $_ == 0) {
                $d = $n / $_;
                last;
            }
        }
        $n -= $d;
        $\++;
    }
} {
# code below added by -p
    print;  # prints $_ (undef here) and $\
}

Clojure, 98 96 octets

#(loop[n % i -1](if n(recur(first(for[j(range(dec n)0 -1):when(=(mod n j)0)](- n j)))(inc i))i))

utilise for :whenpour trouver le plus grand diviseur, boucle jusqu'à ce qu'une valeur supérieure à un ne soit trouvée.