To powinno być proste wyzwanie.

Biorąc pod uwagę liczbę n >= 0, Wyjście super logarytm (lub dziennik *, log-gwiazda, albo powtórzyć logarytm , które są równoważne, ponieważ nnigdy nie jest negatywna na to wyzwanie.) Z n.

Jest to jedna z dwóch odwrotnych funkcji do tetracji . Drugim jest super-root , który jest w pokrewnym pytaniu .

Przykłady

Input       Output
0           0
1           0
2           1
3           2
4           2
...
15          2
16          3
...
3814279     3
3814280     4

Zasady

• Chociaż nie musisz obsługiwać miejsc po przecinku.
• Musisz wesprzeć wejście co najmniej 3814280 = ceiling(e^e^e).
• Nie możesz na stałe zakodować takich wartości jak 3814280. (Twój program musi teoretycznie obsługiwać wyższe liczby.) Chcę, aby algorytm został wdrożony.
• Najkrótszy kod wygrywa.

Powiązane OEIS

Galaretka , 8 bajtów

ÆlÐĿĊḊi1

Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe .

tło

Zaczynamy od sukcesywnego przyjmowania naturalnych logarytmów danych wejściowych i kolejnych wyników, aż wynik się nie zmieni. Działa to, ponieważ rozszerzenie logarytmu naturalnego na płaszczyznę złożoną ma punkt stały ; jeśli z = e ^{-W (-1)} ≈ 0,318 + 1,337i - gdzie W oznacza funkcję L Lbert - mamy log (z) = z .

Dla danych wejściowych n , po obliczeniu [n, log (n), log (log (n)),…, z] najpierw stosujemy funkcję pułapu do każdego z wyników. Implementacja Jelly ( Ċ) faktycznie oblicza urojoną część liczby zespolonej zamiast ^† , ale i tak nas to nie interesuje.

Gdy k- ^ta aplikacja dziennika da wartość mniejszą lub równą 1 , Ċzwróci 1 po raz pierwszy. Liczony od 0 indeks pierwszego 1 jest pożądanym wynikiem.

Prosta implementacja (obliczanie indeksu 1, dekrementacja) kończy się niepowodzeniem z powodu przypadku krawędzi 0 , który nie ma wartości 1 na liście logarytmów. W rzeczywistości dla wejścia 0 sekwencja logarytmów wynosi

[0, None]

Jest tak, ponieważ logarytm Jelly ( Æl) jest przeciążony; najpierw próbuje math.log(logarytm rzeczywisty), potem cmath.log(logarytm złożony), a na koniec „poddaje się” i wraca None. Na szczęście Ċjest podobnie przeciążony i po prostu zwraca argument, jeśli nie może zaokrąglić w górę lub wyimaginować.

Podobnie, wejście 1 zwraca

[1, 0, None]

co może stwarzać problemy w innych podejściach, które obejmują lub nie obejmują Ċ.

Jednym ze sposobów rozwiązania tego problemu jest zastosowanie Ḋ(usuń kolejkę; usuwa pierwszy element) z tablicy logarytmów. To mapy

0ÆlÐĿ -> [0, None]    -> [None]
1ÆlÐĿ -> [1, 0, None] -> [0, None]

więc żadna lista nie ma teraz 1 . W ten sposób znalezienie indeksu pierwszego 1 zwróci 0 (nie znaleziono), co jest pożądanym wyjściem dla wejść 0 i 1 .

Jak to działa

ÆlÐĿĊḊi1  Main link. Argument: n (non-negative integer)

  ÐĿ      Apply the following link until the results are no longer unique.
Æl          Natural logarithm.
          Return the array of all unique results.
    Ċ     Round all resulting real numbers up to the nearest integer. This takes
          the imaginary part of complex numbers and does nothing for non-numbers.
     Ḋ    Dequeue; remove the first item (n) of the array of results.
      i1  Find the first index of 1 (0 if not found).

^† _{Jest to jeden z niewielu atomów galaretki, które są przeciążone w nieoczywisty sposób.}

Galaretka , 9 bajtów

Æl>1$пL’

Wypróbuj online!

Zestaw testowy. (Lekko zmieniony.)

Wyjaśnienie

Æl>1$пL’
     п    while loop, collect all intermediate results.
  >1$      condition: z>1
Æl         body: natural logarithm.
       L   length of the array containing all intermediate results,
           meaning number of iterations
        ’  minus one.

C, 38 bajtów

f(double n){return n>1?1+f(log(n)):0;}

Dość oczywiste.

Wypróbuj na ideone.

JavaScript, 45 27 26 bajtów

l=a=>a>1&&1+l(Math.log(a))

Oto pakiet testowy (3. wersja)

Dzięki @LeakyNun za zapisanie 1 bajtu z funkcją warunkową, a następnie konwersję funkcji na lambda, a @Neil za wskazanie fałszu jest w porządku zwracana wartość dla <= 1 (zmieniono test na == zamiast ===)

Mathematica, 21 bajtów

If[#>1,1+#0@Log@#,0]&

Rekurencyjna anonimowa funkcja. Pobiera na wejściu liczbę całkowitą i zwraca swój logarytm jako wynik. Po prostu używa podanej definicji.

Dyalog APL , 13 bajtów

Bezpośrednie tłumaczenie OP:

{⍵≤1:0⋄1+∇⍟⍵}

Wypróbuj APL online!

Pyth, 10 bajtów

L&>b1hy.lb

Zestaw testowy.

To definiuje funkcję.

Haskell, 23 bajty

l x|x>1=1+l(log x)|1<2=0

Przykład użycia: l 3814280-> 4.

Python 3, 45 bajtów

import math
s=lambda x:x>1and-~s(math.log(x))

Na x <= 1to zwraca False(co jest == 0w Pythonie).

05AB1E, 16 13 bajtów

[Dî2‹#¼žr.n]¾

Wyjaśnienie

              # implicit input n
[          ]  # infinite loop
 Dî2‹#        # break if n rounded up is less than 2
      ¼       # else, increase counter
       žr.n   # set next n = log(n)
            ¾ # push counter and implicitly print

Wypróbuj online

MATL , 15 12 bajtów

0`ZetG>~}x@q

Wypróbuj online! Lub sprawdź wszystkie przypadki testowe (nieco zmodyfikowana wersja do obsługi kilku danych wejściowych).

Jak to działa

Począwszy od 0, stosuj iterowane potęgowanie aż do przekroczenia wartości wejściowej. Dane wyjściowe to liczba iteracji minus 1.

0       % Push 0
`       % Do...while loop
  Ze    %   Exponential
  t     %   Duplicate
  G     %   Push input
  >~    %   Is current value less than or equal to the input? If so: next iteration
}       % Finally (code executed at the end of the last iteration)
  x     %   Delete
  @q    %   Iteration index minus 1
        % Implicitly end loop
        % Implicitly display stack

J , 21 19 18 16 bajtów

Zapisano 2 bajty na Dziurawą Zakonnicę, 1 bajt na Galena Iwanowa i 2 bajty na FrownyFrog!

2#@}.(0>.^.)^:a:

Wypróbuj online!

Przypadki testowe

ls =: >:@$:@^.`0:@.(<:&1)
   ls 0
0
   ls 1
0
   ls 2
1
   ls 3
2
   ls 4
2
   ls 15
2
   ls 16
3
   ls 3814280
4

Julia, 17 bajtów

!x=x>1&&1+!log(x)

Wypróbuj online!

MATLAB / Octave, 44 bajty

function a=g(n);a=0;if n>1;a=1+g(log(n));end

Próbowałem zrobić to wszystko jako jedna anonimowa funkcja, ale zapomniałem, że MATLAB / Octave kontynuuje ocenę wyrażeń, nawet jeśli są one pomnożone przez wartość logiczną false (zero):

f=@(n)(n>1)*(1+f(log(n)))

R, 38 37 bajtów

f=function(x)if(x>1)1+f(log(x))else 0

Dzięki @ user5957401 za dodatkowy bajt!

Przypadki testowe:

> f(0)
[1] 0
> f(1)
[1] 0
> f(2)
[1] 1
> f(3)
[1] 2
> f(4)
[1] 2
> f(3814279)
[1] 3
> f(3814280)
[1] 4

R , 34 bajty

f=pryr::f(`if`(n>1,1+f(log(n)),0))

Wypróbuj online!

Możliwe jest podejście nierekurencyjne: 36 bajtów i pobiera dane wejściowe ze standardowego wejścia.

n=scan()
while((n=log(n))>0)F=F+1
+F

Java 7, 47 bajtów

int c(double n){return n>1?1+c(Math.log(n)):0;}

Wypróbuj online.

Powyższa metoda rekurencyjna w stylu Java 7 jest o 2 bajty krótsza niż iteracyjna lambda w stylu Java 8:

n->{int c=0;for(;n>1;c++)n=Math.log(n);return c;}

Wypróbuj online.

Wyjaśnienie:

int c(double n){      // Method with double parameter and integer return-type
  return n>1?         //  If the input is larger than 1:
    1+                //   Return 1 +
      c(Math.log(n))  //   A recursive call with log(input)
   :                  //  Else:
    0;                //   Return 0 instead

n->{                  // Method with double parameter and integer return-type
  int c=0;            //  Create a counter, starting at 0
  for(;n>1;           //  Loop as long as the input is still larger than 1:
    c++)              //   Increase the counter by 1
    n=Math.log(n);    //   And update the input to log(input)
  return c;}          //  After the loop: return the counter as result

Emacs Lisp, 38 bajtów

(defun l(n)(if(> n 1)(1+(l(log n)))0))

Przypadki testowe:

(mapcar 'l '(0 1 2 3 4 15 16 3814279 3814280))
;; (0 0 1 2 2 2 3 3 4)

Galaretka , 8 bajtów

-Ælß$Ị?‘

Prosta implementacja definicji. Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe .

Jak to działa

-Ælß$Ị?‘  Main link. Argument: x

     Ị    Insignificant; test if |x| ≤ 1.
      ?   If the result is 1:
-           Return -1.
          Else:
   $        Execute the monadic chain formed by the two links to the left.
Æl            Apply natural logarithm to x.
  ß           Recursively call the main link.
       ‘  Increment the result.

Perl 5, 35 bajtów

Bardzo prosty, wymaga -M5.016(który jest bezpłatny) włączenia __SUB__słowa kluczowego w celu anonimowej rekurencji.

sub{$_[0]>1?1+__SUB__->(log pop):0}

Inną alternatywą jest

sub{$_[0]>1?1+__SUB__->(log pop):0}

który ma 34 bajty i daje takie same dane wyjściowe dla wszystkich danych wejściowych> 1, ale zwraca specjalną wartość false dla danych wejściowych <= 1. Fałsz jest liczbowo równy zero, ale jest drukowany jako „” (pusty ciąg znaków), więc prawdopodobnie nie robi „ zakwalifikować się.

CJam (16 bajtów)

rd{_1>}{_ml}w],(

Demo online

Prosta pętla while z warunkiem wstępnym. (To, czego naprawdę chcę tutaj, to operacja rozwijania w stylu Golfscript, ale CJam nie ma takiej operacji, a zmienna zmienna w GolfScript jest bałaganiarska i wcale nie jest golfowa).

PARI / GP , 24 bajty

Prosta rekurencja.

f(n)=if(n>1,1+f(log(n)))

Rakieta, 61 bajtów

(λ(x)(letrec([a(λ(b)(if(> b 1)(+ 1 (a(log b)))0))])(a x)))

Klon, 32,30 29 bajtów

f:=x->`if`(x>1,1+f(log(x)),0)

Przypadki testowe:

> f(0.);
  0
> f(1.);
  0
> f(2.);
  1
> f(3.);
  2
> f(4.);
  2
> f(3814279.);
  3
> f(3814280.);
  4

R, 36 bajtów

Nieco inne podejście niż Plannapus

->n;a=0;while(n>1){a=a+1;n=log(n)};a

Używa odpowiedniego przypisania do uruchomienia kodu - więc żądany numer musi go poprzedzić. to znaczy

10->n;a=0;while(n>1){a=a+1;n=log(n)};a

Mathematica, 29 bajtów

Prosty jak diabli i działa zarówno na komicznie duże, jak i negatywne dane wejściowe:

f[x_]:=If[x>1,1+f[Log[x]],0]

Rubinowy, 29 bajtów

l=->n{n<=1?0:1+l[Math.log n]}

Perl 6 , 21 bajtów

{($_,*.log...1>=*)-1}

Wypróbuj online!

Wyrażenie w nawiasie to sekwencja. $_, argument funkcji, jest pierwszym elementem. *.loggeneruje każdy kolejny element, biorąc dziennik poprzedniego elementu. Sekwencja jest kontynuowana, dopóki warunek końcowy nie 1 >= *jest prawdziwy: 1 jest większy lub równy bieżącemu elementowi. Odejmowanie 1 od sekwencji wymusza jej liczbę: długość.