Zainspirowany tym pytaniem z Matematyki .

Problem

Niech nbędzie liczbą naturalną ≥ 2. Weź największy dzielnik n- który różni się od nsiebie - i odejmij go n. Powtarzaj, aż dostaniesz 1.

Pytanie

Ile kroków trzeba osiągnąć, 1aby uzyskać określoną liczbę n ≥ 2.

Szczegółowy przykład

Let n = 30.

Największy dzielnik:

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

To trwa 6 kroków do osiągnięcia 1.

Wejście

• Dane wejściowe to liczba całkowita n, gdzie n ≥ 2.
• Twój program powinien obsługiwać wprowadzanie danych do maksymalnej wartości całkowitej języka.

Wynik

• Po prostu wypisz liczbę kroków, takich jak 6.
• Wiodące / końcowe białe znaki lub znaki nowej linii są w porządku.

Przykłady

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

Wymagania

• Możesz uzyskać dane wejściowe z STDINargumentów wiersza poleceń jako parametry funkcji lub z najbliższego odpowiednika.
• Możesz napisać program lub funkcję. Jeśli jest to funkcja anonimowa, podaj przykład jej wywołania.
• To jest golf golfowy, więc wygrywa najkrótsza odpowiedź w bajtach.
• Standardowe luki są niedozwolone.

Tę serię można również znaleźć w OEIS: A064097

Quasi-logarytm zdefiniowany indukcyjnie przez a(1) = 0i a(p) = 1 + a(p-1)jeśli pjest liczbą pierwszą i a(n*m) = a(n) + a(m)jeśli m,n > 1.

Galaretka , 9 bajtów

ÆṪÐĿÆFL€S

Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe .

tło

Definicja sekwencji A064097 implikuje, że

Według formuły produktu Eulera

gdzie φ oznacza funkcję całkowitą Eulera, a p zmienia się tylko w liczbach pierwszych.

Łącząc oba, dedukujemy właściwość

gdzie ω oznacza liczbę różnych czynników pierwszych n .

Stosując wynikową formułę k + 1 razy, gdzie k jest wystarczająco duże, aby φ ^{k + 1} (n) = 1 , otrzymujemy

Z tej właściwości otrzymujemy wzór

gdzie zachowana jest ostatnia równość, ponieważ ω (1) = 0 .

Jak to działa

ÆṪÐĿÆ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 bajtów

Kod:

[DÒ¦P-¼D#]¾

Wyjaśnienie:

[        ]   # 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.

Wykorzystuje kodowanie CP-1252 . Wypróbuj online! .

Pyth, 11 bajtów

fq1=-Q/QhPQ

Zestaw testowy

Prosta pętla powtarzania aż do prawdziwej.

Wyjaśnienie:

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 bajtów

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

To nie zakończy tego ostatniego przypadku testowego w najbliższym czasie ...

Alternatywnie, oto 48-bajtowy, który zwraca Truezamiast 1dla n=2:

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

Galaretka , 10 bajtów

ÆfḊPạµÐĿi2

Wypróbuj online! lub zweryfikuj większość przypadków testowych . Ostatnie przypadki testowe kończą się szybko lokalnie.

Jak to działa

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

Siatkówka , 12

• 14 bajtów zapisanych dzięki @ MartinBüttner

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

Zakłada się, że dane wejściowe są podawane w postaci jednoargumentowej, a dane wyjściowe w postaci dziesiętnej. Jeśli nie jest to do przyjęcia, możemy to zrobić dla 6 bajtów więcej:

Retina , 18 lat

• 8 bajtów zapisanych dzięki @ MartinBüttner

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

Wypróbuj online - dodano 1 linię, aby uruchomić wszystkie przypadki testowe za jednym razem.

Niestety do obliczeń wykorzystuje się jedno, więc wprowadzenie danych z 2016 r. ¹⁵⁵ nie jest praktyczne.

• Pierwszy etap (2 linie) po prostu konwertuje dane dziesiętne na jedne jako ciąg 1s
• Drugi etap (1 linia) oblicza największy współczynnik n za pomocą grup dopasowania wyrażeń regularnych i szuka do niego i skutecznie odejmuje go od n. Wyrażenie regularne będzie pasować tyle razy, ile będzie to konieczne, aby zmniejszyć liczbę w jak największym stopniu. Liczba dopasowań wyrażeń regularnych będzie liczbą kroków i jest wyprowadzana na tym etapie.

Pyth - 15 14 13 bajtów

Specjalna obudowa 1naprawdę mnie zabija.

tl.u-N/Nh+PN2

Wypróbuj online tutaj .

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

Edytuj 6 bajtów zapisanych dzięki @ l4m2

(* 4 strikowane to nadal 4)

Funkcja rekurencyjna

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

Mniej golfa

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
}

Test

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 bajtów

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

Funkcja bez nazwy przyjmuje te same bajty:

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

Jest to bardzo prosta implementacja definicji jako funkcji rekurencyjnej.

Oktawa, 59 58 55 bajtów

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

Zaktualizowano dzięki Stewie Griffin, oszczędzając 1 bajt

Dalsza aktualizacja, oszczędność trzech kolejnych bajtów przy użyciu wyniku faktoryzacji w trakcie sprawdzania.

Przykładowe przebiegi:

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 bajtów

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

Stosowanie:

Prelude> f 30
Prelude> 6

Może być trochę nieefektywny w przypadku dużych liczb ze względu na generowanie listy.

Julia, 56 50 45 39 bajtów

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

Jest to funkcja rekurencyjna, która przyjmuje liczbę całkowitą i zwraca liczbę całkowitą.

Nie golfowany:

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

Wypróbuj online! (obejmuje wszystkie przypadki testowe)

Zaoszczędzono 6 bajtów dzięki Martinowi Büttnerowi i 11 dzięki Dennisowi!

PowerShell v2 +, 81 bajtów

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

Najsilniejsza z brutalnej siły.

Pobiera dane wejściowe $a, wchodzi w forpętlę, aż $abędzie mniejsza lub równa 1. W każdej pętli przechodzimy przez kolejną forpętlę, która odlicza czas $ado znalezienia dzielnika ( !($a%$i). W najgorszym przypadku znajdziemy się $i=1jako dzielnik. Kiedy to zrobimy, zwiększ nasz licznik $j, odejmij dzielnik $a-=$ii ustaw się, $i=0by wyrwać się z wewnętrznej pętli. W końcu osiągniemy stan, w którym zewnętrzna pętla jest fałszywa (tzn. $aOsiągnęła 1), więc wyjście $ji wyjście.

Uwaga : Zajmie to dużo czasu w przypadku większych liczb, zwłaszcza liczb pierwszych. Wejście 100 000 000 zajmuje ~ 35 sekund na moim laptopie Core i5. Edycja - właśnie przetestowałem [int]::MaxValue(2 ^ 32-1) i zajęło ~ 27 minut. Nie jest tak źle, jak sądzę.

Matlab, 58 bajtów

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

Japt , 12 bajtów (niekonkurujące)

@!(UµUk Å×}a

Przetestuj online! Nie konkuruje, ponieważ korzysta z wielu funkcji, które zostały dodane po opublikowaniu wyzwania.

Jak to działa

@   !(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

Ta technika została zainspirowana odpowiedzią 05AB1E . Użyto poprzedniej wersji ²¤(odepchnij 2, odetnij pierwsze dwa elementy) zamiast, Åponieważ jest on o jeden bajt krótszy niż s1 (zwróć uwagę na spację); Zrozumiałem dopiero po tym, że ponieważ dołącza on 2 do końca tablicy i wycina od początku , w rzeczywistości nie działa na żadnej nieparzystej liczbie złożonej, chociaż działa na wszystkich podanych przypadkach testowych.

Python 3, 75, 70 , 67 bajtów.

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]

Jest to dość proste rozwiązanie rekurencyjne. Zajmowanie bardzo dużej liczby przypadków testowych zajmuje BARDZO dużo czasu.

> <>, 32 bajty

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

Oczekuje liczby wejściowej nna stosie.

Ten program buduje pełną sekwencję na stosie. Ponieważ jedyną liczbą, która może do tego doprowadzić, 1jest 2budowanie sekwencji po jej 2osiągnięciu. Powoduje to również, że rozmiar stosu jest równy liczbie kroków, a nie liczbie kroków +1.

Rubinowy, 43 bajty

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

Znajdź najmniejszą liczbę i, która xdzieli x-ii powtarzaj, aż dotrzemy 1.

Haskell, 67 bajtów

Oto kod:

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

Oto jeden z powodów, dla których Haskell jest niesamowity:

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
  ]

Tak, w Haskell możesz zdefiniować -->równoważność ==.

Matlab, 107 bajtów

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

• Niekonkurencyjne, to nie jest iteracyjne tłumaczenie mojego ostatniego przedłożenia, to tylko kolejna bezpośrednia metoda algerbraiczna, podsumowuje wszystkie binarne logi wszystkich czynników pierwszych, trochę niejednoznaczne do zilustrowania.
• Będę grał w golfa, kiedy będę miał czas.

MATL, 17 16 bajtów

`tttYfl)/-tq]vnq

Wypróbuj online

Wyjaśnienie

        % 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 bajtów

1 bajt golfowany przez @Alchymist.

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

Wywołaj jako f (x, i y), gdzie x to wejście, a y to wyjście.

Julia, 39 36 bajtów

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

Wypróbuj online!

Clojure, 116 104 bajtów

(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 bajtów poprzez filtrowanie zakresu w celu znalezienia wielokrotności, a następnie użycie lastjednego, aby uzyskać największy

Naiwne rozwiązanie, które w zasadzie rozwiązuje problem w sposób opisany przez PO. Niestety znalezienie samego największego dzielnika zajmuje około połowy użytych bajtów. Przynajmniej powinienem mieć stąd dużo miejsca do gry w golfa.

Grał w golfa i testował:

(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 bajtów

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

Wypróbuj online!

Jak to działa

{                                 }   # 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 bajtów

L?tbhy-b*F+1tPb0

Wypróbuj online! (Na y.vkońcu jest wywołanie funkcji)

Oryginalne 17 bajtów:

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

Wypróbuj online! (Na y.vkońcu jest wywołanie funkcji)

(Właściwie odpowiedziałem na to pytanie w tym programie Pyth.)

Pyke, 11 bajtów (niekonkurencyjny)

D3Phf-oRr;o

Wykorzystuje to nowe zachowanie, w którym jeśli po goto pojawi się wyjątek, przywraca on stan sprzed goto (z wyjątkiem definicji zmiennych) i kontynuuje. W tym przypadku jest to równoważne z następującym kodem python:

# 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

Wszystko to jest możliwe przy użyciu Pyke bez konstrukcji pętli while - tak, goto!

Wypróbuj tutaj!

JavaScript (ES6), 70 54 bajtów

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

Implementacja podanej formuły rekurencyjnej, ale teraz zaktualizowana, aby użyć rekurencji również w celu znalezienia dzielnika.

Perl, 57 + 1 ( -pflaga) = 58 bajtów

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

Stosowanie:

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

Nie golfowany:

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 bajtów

#(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))

służy for :whendo znajdowania największego dzielnika, pętle, dopóki nie zostanie znaleziona taka wartość większa niż jeden.