Oblicz super-logarytm

29

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.

log * (n): = {0 jeśli n <= 1;  1 + log * (log (n)) jeśli n> 1}

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

mbomb007
źródło
Związane z.
Oliver Ni

Odpowiedzi:

14

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.

Dennis
źródło
11

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.
Leaky Nun
źródło
7

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

CShark
źródło
Robiłem to bez es6, ale tak, to byłoby o 1 bajt krótsze, dzięki.
CShark,
Dlaczego nie używałbyś lambda?
Leaky Nun
nie ma dobrego powodu, po prostu tak często go nie używałem, więc nie jest to mój pierwszy instynkt
CShark
Najwyraźniej wolno nam zwrócić falsezamiast 0 (ponieważ automatycznie konwertuje na 0 w wyrażeniu całkowitym), w którym to przypadku możesz upuścić |0.
Neil,
Pozwoliłoby to zaoszczędzić 1 bajt, ale co rozumiesz przez „automatycznie konwertuje na 0”? Co to jest"?
CShark,
6

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.

LegionMammal978
źródło
3
Rzeczywiście spojrzałem z wyprzedzeniem, aby sprawdzić, czy jest wbudowany. Byłem zaskoczony, kiedy nie było. : D
mbomb007,
5

Pyth, 10 bajtów

L&>b1hy.lb

Zestaw testowy.

To definiuje funkcję.

Leaky Nun
źródło
Nie widzę żadnych danych wyjściowych w twoim pakiecie testowym. Tylko kilka pustych wierszy na wyjściu.
mbomb007,
@ mbomb007 Naprawiono.
Leaky Nun
O wiele fajniejsze: tl.u?>N1.l;-)
Jakube,
@Jakube Możesz to opublikować!
Leaky Nun
5

Haskell, 23 bajty

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

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

nimi
źródło
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).

Lynn
źródło
Tak, Falsemożna użyć do 0.
mbomb007,
Pokonałeś też moją naiwną implementację (używając andraczej niż if else). Grats
mbomb007,
4

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

Emigna
źródło
3

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
Luis Mendo
źródło
3

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
Conor O'Brien
źródło
Oto moje 18-bajtowe rozwiązanie: 2#@}.^.^:(0<])^:a:(Zacząłem przeszukiwać to, co okazało się duplikatem tego problemu).
Galen Iwanow
2#@}.(0>.^.)^:a:wydaje się działać.
FrownyFrog
Nie jestem jednak pewien, czy jest równoważny.
FrownyFrog,
2

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

costrom
źródło
Tak, byłoby miło mieć produkt powodujący zwarcie :-)
Luis Mendo
2

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
plannapus
źródło
Myślę, że możesz zapisać bajt, używając dosłownej instrukcji if, else. tzn. if(x>1)1+f(log(x))else 0jest o jeden bajt krótszy.
user5957401,
2

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

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
Kevin Cruijssen
źródło
Możesz go skrócić w przypadku Java 8 lambda.
mbomb007
@ mbomb007 odpowiedział trzy lata później, haha ​​.. (wtedy grałem tylko w golfa w Javie 7), ale wciąż odpowiadam na twoje pytanie: nie, niestety lambda Java 8 jest o 2 bajty dłuższa niż metoda rekurencyjna. Dodałem to do mojej odpowiedzi, a także dodałem wyjaśnienie.
Kevin Cruijssen
Więc nie możesz robić rekurencyjnych lambdów?
mbomb007
@ mbomb007 Nie, w Javie niestety nie. W Pythonie, JavaScript i myślę, że również C # .NET, rekurencyjne lambdy są możliwe, ale w Javie nie z jakiegoś powodu ..
Kevin Cruijssen
1

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)
Lord Yuuma
źródło
1

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.
Dennis
źródło
1

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

Hobbs
źródło
Świetna odpowiedź. Możesz wygrać 1 bajt, robiąc sub{($_=pop)>1?1+__SUB__->(log):0}jednak
Dada,
1

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

Peter Taylor
źródło
Nawiasem mówiąc, jest to moja 80. odpowiedź z matematyki i przyniosła mi dziś moją drugą plakietkę.
Peter Taylor,
1

PARI / GP , 24 bajty

Prosta rekurencja.

f(n)=if(n>1,1+f(log(n)))
Charles
źródło
1

Rakieta, 61 bajtów

(λ(x)(letrec([a(λ(b)(if(> b 1)(+ 1 (a(log b)))0))])(a x)))
Steven H.
źródło
1

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
DSkoog
źródło
1

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
użytkownik5957401
źródło
0

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]

enter image description here

Landak
źródło
0

Rubinowy, 29 bajtów

l=->n{n<=1?0:1+l[Math.log n]}
Seims
źródło
-1 bajt poprzez przepisanie n<=1?a:bjako n>1?b:ai -1 dodatkowy bajt z anonimowymi funkcjami lambda .
Po prostu piękna sztuka,
0

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ść.

Sean
źródło