Berechnen Sie den Super-Logarithmus

29

Dies sollte eine einfache Herausforderung sein.

Bei einer gegebenen Zahl n >= 0wird der Superlogarithmus (oder der Logarithmus *, der Log-Stern oder der iterierte Logarithmus , die äquivalent sind, da er nfür diese Herausforderung niemals negativ ist) von ausgegeben n.

log * (n): = {0 wenn n <= 1;  1 + log * (log (n)), wenn n> 1}

Dies ist eine der beiden Umkehrfunktionen zur Tetration . Die andere ist die Superwurzel , die sich in einer verwandten Frage befindet .

Beispiele

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

Regeln

  • Sie müssen keine Dezimalstellen unterstützen, auch wenn Sie dies möchten.
  • Sie müssen die Eingabe von mindestens unterstützen 3814280 = ceiling(e^e^e).
  • Sie können die Werte wie nicht hart codieren 3814280. (Ihr Programm muss theoretisch höhere Zahlen unterstützen.) Ich möchte, dass ein Algorithmus implementiert wird.
  • Kürzester Code gewinnt.

Verwandte OEIS

mbomb007
quelle
Verbunden.
Oliver Ni

Antworten:

14

Gelee , 8 Bytes

ÆlÐĿĊḊi1

Probieren Sie es online! oder überprüfen Sie alle Testfälle .

Hintergrund

Wir beginnen damit, nacheinander natürliche Logarithmen der Eingabe und der nachfolgenden Ergebnisse zu verwenden, bis sich das Ergebnis nicht mehr ändert. Dies funktioniert, weil die Ausdehnung des natürlichen Logarithmus auf die komplexe Ebene einen festen Punkt hat . wenn z = e - W (-1) ≤ 0,318 + 1,337i - wobei W die Lambert - W - Funktion bezeichnet - haben wir log (z) = z .

Für die Eingabe n wenden wir nach der Berechnung von [n, log (n), log (log (n)), ..., z] zunächst die Deckenfunktion auf jedes der Ergebnisse an. Jellys Implementierung ( Ċ) berechnet stattdessen den Imaginärteil der komplexen Zahl , was uns jedoch sowieso nicht interessiert.

Sobald der k - te Anwendung der log einen Wert kleiner als oder gleich ergibt 1 , Ċkehrt 1 zum ersten Mal. Der auf 0 basierende Index dieser ersten 1 ist das gewünschte Ergebnis.

Die unkomplizierte Implementierung (1-basierten Index berechnen, dekrementieren) schlägt fehl, da der Kantenfall 0 keine 1 in der Liste der Logarithmen enthält. Tatsächlich ist für den Eingang 0 die Reihenfolge der Logarithmen

[0, None]

Dies liegt daran, dass der Logarithmus von Jelly ( Æl) überladen ist. es versucht zuerst math.log(realer Logarithmus), dann cmath.log(komplexer Logarithmus) und gibt schließlich "auf" und kehrt zurück None. Glücklicherweise Ċist es ähnlich überladen und gibt einfach das Argument zurück, wenn es nicht aufrunden oder einen imaginären Teil übernehmen kann.

Ebenso wird Eingang 1 zurückgegeben

[1, 0, None]

Dies kann bei anderen Ansätzen zu Problemen führen Ċ.

Eine Möglichkeit, dieses Problem zu beheben, besteht darin , das Array von Logarithmen zuzuweisen (aus der Warteschlange zu entfernen; erstes Element zu entfernen). Diese Karten

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

Daher hat keine der Listen jetzt eine 1 . Auf diese Weise, den Index der ersten Auffinden 1 zurückkehren wird 0 (nicht gefunden), die die gewünschte Ausgabe für die Eingänge 0 und 1 .

Wie es funktioniert

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

Dies ist eines der wenigen Atome in Jelly, die auf nicht offensichtliche Weise überladen sind.

Dennis
quelle
11

Gelee , 9 Bytes

Æl>1$пL’

Probieren Sie es online!

Testsuite. (Leicht verändert.)

Erläuterung

Æ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.
Undichte Nonne
quelle
7

Javascript, 45 27 26 Bytes

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

Hier ist die Testsuite (3. Version)

Vielen Dank an @LeakyNun für das Speichern von 1 Byte mit der bedingten und anschließenden Konvertierung der Funktion in Lambda.

CShark
quelle
Ich habe es ohne es6 gemacht, aber das wäre ja 1 Byte kürzer, danke.
CShark
Warum würden Sie nicht Lambda verwenden?
Undichte Nonne
Kein guter Grund, ich habe es nur nicht so oft benutzt, also ist es nicht mein erster Instinkt
CShark
Anscheinend dürfen wir falseanstelle von 0 zurückgeben (da es in einem ganzzahligen Ausdruck automatisch in 0 konvertiert wird). In diesem Fall können Sie die fallen lassen |0.
Neil
Das würde 1 Byte sparen, aber was meinst du mit "es wird automatisch in 0 konvertiert"? Was ist es"?
CShark
6

Mathematica, 21 Bytes

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

Rekursive anonyme Funktion. Nimmt eine Ganzzahl als Eingabe und gibt ihren Superlogarithmus als Ausgabe zurück. Verwendet einfach die angegebene Definition.

LegionMammal978
quelle
3
Eigentlich habe ich vorab nachgesehen, ob ein eingebautes vorhanden ist. Ich war überrascht, als es keine gab. : D
mbomb007
5

Dyalog APL , 13 Bytes

Direkte Übersetzung von OP:

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

TryAPL online!

Adam
quelle
5

Pyth, 10 Bytes

L&>b1hy.lb

Testsuite.

Dies definiert eine Funktion.

Undichte Nonne
quelle
Ich sehe keine Ausgabe in Ihrer Testsuite. Nur ein paar leere Zeilen in der Ausgabe.
mbomb007
@ mbomb007 Behoben.
Undichte Nonne
tl.u?>N1.l
Viel
@ Jakube Du könntest das posten!
Undichte Nonne
5

Haskell, 23 Bytes

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

Anwendungsbeispiel: l 3814280-> 4.

nimi
quelle
4

Python 3, 45 Bytes

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

Für x <= 1kehrt dies zurück False(was == 0in Python ist).

Lynn
quelle
Ja, Falsekann für verwendet werden 0.
mbomb007
Außerdem hast du meine naive Implementierung übertroffen (indem du andeher als verwendest if else). Grats.
mbomb007
4

05AB1E, 16 13 Bytes

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

Erläuterung

              # 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

Probieren Sie es online aus

Emigna
quelle
3

MATL , 15 12 Bytes

0`ZetG>~}x@q

Probieren Sie es online! Oder überprüfen Sie alle Testfälle (leicht modifizierte Version, um mehrere Eingaben zu verarbeiten).

Wie es funktioniert

Wenden Sie beginnend mit 0 die iterierte Exponentiation an, bis die Eingabe überschritten wird. Die Ausgabe ist die Anzahl der Iterationen 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
quelle
3

J , 21, 19, 18 16 Bytes

2 Byte für Leaky Nun, 1 Byte für Galen Ivanov und 2 Byte für FrownyFrog gespeichert!

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

Probieren Sie es online!

Testfälle

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
quelle
Hier ist meine 18-Byte-Lösung: 2#@}.^.^:(0<])^:a:(Ich fing an, das, was sich herausstellte, als Trottel dieses Problems zu betrachten.)
Galen Ivanov
2#@}.(0>.^.)^:a:scheint zu funktionieren.
FrownyFrog
Ich bin mir nicht sicher, ob es äquivalent ist.
FrownyFrog
2

MATLAB / Octave, 44 Bytes

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

Es wurde versucht, alles als eine anonyme Funktion auszuführen, aber ich habe vergessen, dass MATLAB / Octave weiterhin Ausdrücke auswertet, auch wenn sie mit einem booleschen Wert false (Null) multipliziert werden:

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

costrom
quelle
Ja, es wäre schön, ein Kurzschlussprodukt zu haben :-)
Luis Mendo
2

R, 38 37 Bytes

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

Vielen Dank an user5957401 für das zusätzliche Byte!

Testfälle:

> 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
quelle
Ich denke, Sie können ein Byte speichern, indem Sie eine wörtliche if, else-Anweisung verwenden. dh if(x>1)1+f(log(x))else 0ist ein Byte kürzer.
user5957401
2

R , 34 Bytes

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

Probieren Sie es online!

Ein nicht rekursiver Ansatz ist möglich: 36 Bytes und nimmt die Eingabe von stdin entgegen.

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

Java 7, 47 Bytes

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

Probieren Sie es online aus.

Die oben beschriebene Methode im rekursiven Java 7-Stil ist 2 Byte kürzer als ein iteratives Lambda im Java 8-Stil:

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

Probieren Sie es online aus.

Erläuterung:

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
quelle
Mit einem Java-8-Lambda könnte es kürzer werden.
mbomb007
@ mbomb007 antwortete drei Jahre später, haha ​​.. (zu der Zeit war ich nur Code-Golfer in Java 7), aber um Ihre Frage zu beantworten: Nein, leider ist ein Java 8 Lambda 2 Bytes länger als die rekursive Methode. Ich habe es meiner Antwort hinzugefügt, und ich habe auch eine Erklärung hinzugefügt.
Kevin Cruijssen
Sie können also keine rekursiven Lambdas machen?
mbomb007
@ mbomb007 Nein, in Java leider nicht. In Python, JavaScript und meiner Meinung nach auch in C # .NET sind rekursive Lambdas möglich, in Java jedoch aus irgendeinem Grund nicht.
Kevin Cruijssen
1

Emacs Lisp, 38 Bytes

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

Testfälle:

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

Gelee , 8 Bytes

-Ælß$Ị?‘

Einfache Umsetzung der Definition. Probieren Sie es online! oder überprüfen Sie alle Testfälle .

Wie es funktioniert

-Æ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
quelle
1

Perl 5, 35 Bytes

Sehr einfach, benötigt -M5.016(was kostenlos ist), um das __SUB__Schlüsselwort für die anonyme Rekursion zu aktivieren .

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

Eine andere Alternative ist

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

Dies ist 34 Byte und gibt für alle Eingaben> 1 die gleiche Ausgabe aus, gibt jedoch den speziellen falschen Wert für Eingaben <= 1 zurück. False ist numerisch gleich Null, wird jedoch als "" (leere Zeichenfolge) ausgegeben. t qualifizieren.

hobbs
quelle
Gute Antwort. Sie können jedoch 1 Byte gewinnen, sub{($_=pop)>1?1+__SUB__->(log):0}wenn Sie dies tun
Dada
1

CJam (16 Bytes)

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

Online-Demo

Einfache While-Schleife mit Vorbedingung. (Was ich hier wirklich möchte, ist eine Entfaltungsoperation im Golfscript-Stil, aber CJam hat keine, und Gleitkomma in GolfScript ist chaotisch und überhaupt nicht Golf).

Peter Taylor
quelle
Abgesehen davon ist dies meine 80. Antwort in Mathematik und ich habe mir heute mein zweites Tag-Abzeichen verdient.
Peter Taylor
1

PARI / GP , 24 Bytes

Nur die einfache Rekursion.

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

Schläger, 61 Bytes

(λ(x)(letrec([a(λ(b)(if(> b 1)(+ 1 (a(log b)))0))])(a x)))
Steven H.
quelle
1

Ahorn, 32,30 29 Bytes

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

Testfälle:

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

R, 36 Bytes

Etwas anderer Ansatz als bei Plannapus

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

Verwendet eine Rechtezuweisung, um den Code auszuführen - daher muss die gewünschte Nummer davor stehen. dh

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

Mathematica, 29 Bytes

Einfach wie die Hölle und funktioniert sowohl für komisch große als auch für negative Eingänge:

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

Bildbeschreibung hier eingeben

Landak
quelle
0

Ruby, 29 Bytes

l=->n{n<=1?0:1+l[Math.log n]}
Seims
quelle
-1 Byte durch Umschreiben n<=1?a:bals n>1?b:aund -1 Byte mit anonymen Lambda-Funktionen .
Simply Beautiful Art
0

Perl 6 , 21 Bytes

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

Probieren Sie es online!

Der Ausdruck in Klammern ist eine Sequenz. $_, das Argument für die Funktion, ist das erste Element. *.loggeneriert jedes nachfolgende Element, indem es das Protokoll des vorherigen Elements aufnimmt. Die Sequenz wird fortgesetzt, bis die Endebedingung 1 >= *wahr ist: 1 ist größer oder gleich dem aktuellen Element. Das Subtrahieren von 1 von der Sequenz zwingt es zu einer Zahl: seiner Länge.

Sean
quelle