Bei einer positiven ganzen Zahl n und eine Anzahl ein , die n -te tetration of a ist definiert als ein ^ ( ein ^ ( ein ^ (^ ... ein ))), wobei ^ bezeichnet Potenzierung (oder Leistung) und der Ausdruck enthält die nummer a genau n mal.

Mit anderen Worten, Tetration ist rechtsassoziativ iterierte Potenzierung. Für n = 4 und a = 1,6 beträgt die Tetration 1,6 ^ (1,6 ^ (1,6 ^ 1,6)) ≈ 3,5743.

Die inverse Funktion der tetration mit Bezug auf n ist der Super-Logarithmus . Im vorherigen Beispiel ist 4 der Superlogarithmus von 3,5743 mit "Super-Base" 1,6.

Die Herausforderung

Wenn eine positive ganze Zahl n gegeben ist , finde x so, dass n der Superlogarithmus von sich selbst in der Super-Basis x ist . Das heißt, finden x , so daß x ^ ( x ^ ( x ^ (... ^ x ))) (mit x erscheinenden n mal) gleich n .

Regeln

Programm oder Funktion erlaubt.

Eingabe- und Ausgabeformate sind wie gewohnt flexibel.

Der Algorithmus sollte theoretisch für alle positiven ganzen Zahlen funktionieren. In der Praxis kann die Eingabe aufgrund von Speicher-, Zeit- oder Datentypbeschränkungen auf einen Maximalwert beschränkt sein. Der Code muss jedoch für Eingaben 100mindestens in weniger als einer Minute funktionieren .

Der Algorithmus sollte theoretisch das Ergebnis mit 0.001Präzision liefern . In der Praxis kann die Ausgabegenauigkeit aufgrund von akkumulierten Fehlern bei numerischen Berechnungen schlechter sein. Die Ausgabe muss jedoch bis zu 0.001den angegebenen Testfällen genau sein .

Kürzester Code gewinnt.

Testfälle

1    ->  1
3    ->  1.635078
6    ->  1.568644
10   ->  1.508498
25   ->  1.458582
50   ->  1.448504
100  ->  1.445673

Referenzimplementierung

Hier ist eine Referenzimplementierung in Matlab / Octave (versuchen Sie es bei Ideone ).

N = 10; % input
t = .0001:.0001:2; % range of possible values: [.0001 .0002 ... 2]
r = t;
for k = 2:N
    r = t.^r; % repeated exponentiation, element-wise
end
[~, ind] = min(abs(r-N)); % index of entry of r that is closest to N
result = t(ind);
disp(result)

Dafür N = 10gibt es result = 1.5085.

Der folgende Code dient zur Überprüfung der Ausgabegenauigkeit mithilfe von Arithmetik mit variabler Genauigkeit:

N = 10;
x = 1.5085; % result to be tested for that N. Add or subtract 1e-3 to see that
            % the obtained y is farther from N
s = num2str(x); % string representation
se = s;
for n = 2:N;
    se = [s '^(' se ')']; % build string that evaluates to iterated exponentiation
end
y = vpa(se, 1000) % evaluate with variable-precision arithmetic

Das gibt:

• Für x = 1.5085:y = 10.00173...
• Für x = 1.5085 + .001:y = 10.9075
• Denn x = 1.5085 - .001es gibt y = 9.23248.

Das 1.5085ist eine gültige Lösung mit .001Präzision.

Dyalog APL , 33 25 Bytes

Bedürfnisse, ⎕IO←0die auf vielen Systemen Standard sind.

⌈/⎕(⊢×⊣≥(*/⍴)¨)(1+⍳÷⊢)1E4

Theoretisch berechnet für alle ganzen Zahlen, aber praktisch nur für sehr kleine.

TryAPL online!

Haskell, 55 54 52 Bytes

s n=[x|x<-[2,1.9999..],n>iterate(x**)1!!floor n]!!0

Verwendung:

> s 100
1.445600000000061

Danke an @nimi für 1 Byte!
Danke an @xnor für 2!

Javascript, ES6: 77 Byte / ES7: 57 53 Byte

ES6

n=>eval("for(x=n,s='x';--x;s=`Math.pow(x,${s})`);for(x=2;eval(s)>n;)x-=.001")

ES7

Verwendung **wie von DanTheMan vorgeschlagen:

n=>eval("for(x=2;eval('x**'.repeat(n)+1)>n;)x-=.001")

Beispiel

let f =
n=>eval("for(x=n,s='x';--x;s=`Math.pow(x,${s})`);for(x=2;eval(s)>n;)x-=.001")

console.log(f(25));

Mathematica, 40 33 Bytes

Dank Murphy für fast 20% Ersparnis!

1//.x_:>x+.001/;Nest[x^#&,1,#]<#&

Nest[x^#&,1,n]erzeugt die n-te Tetration von x. Nest[x^#&,1,#]<#Prüft also , ob die (Eingabe) -te Tetration von x kleiner als (Eingabe) ist. Wir beginnen einfach bei x = 1 und addieren 0,001 so oft, bis die Tetration zu groß ist, und geben dann den letzten x-Wert aus (damit die Antwort garantiert größer als der exakte Wert ist, aber innerhalb von 0,001).

Wie ich langsam lerne: //.x_:>y/;zoder //.x_/;z:>ybedeutet "Suche nach etwas, das mit der Vorlage x übereinstimmt, aber nur nach Dingen, für die der Test z true zurückgibt; und bearbeite dann x durch die Regel y; so oft, bis sich nichts mehr ändert". Hier ist das Template x_nur "irgendeine Zahl, die ich sehe", obwohl es in anderen Zusammenhängen weiter eingeschränkt werden könnte.

Wenn die Eingabe mindestens 45 ist, steigt die Tetration so schnell an, dass dieser letzte Schritt einen Überlauffehler verursacht. Der Wert von x wird jedoch weiterhin aktualisiert und korrekt ausgegeben. Das Verringern der Schrittgröße von 0,001 auf 0,0001 behebt dieses Problem für Eingaben bis zu 112 und gibt eine genauere Antwort auf das Booten (und läuft immer noch schnell, in ungefähr einer Viertelsekunde). Aber das ist ein zusätzliches Byte, also vergiss das!

Originalfassung:

x=1;(While[Nest[x^#&,1,#]<#,x+=.001];x)&

J, 39 31 28 Bytes

(>./@(]*[>^/@#"0)1+i.%])&1e4

Basierend auf der Referenzimplementierung. Es ist nur auf drei Dezimalstellen genau.

8 Bytes mit der Methode von @ Adáms Lösung gespeichert .

Verwendung

Zusätzliche Befehle zum Formatieren mehrerer Ein- / Ausgaben.

   f =: (>./@(]*[>^/@#"0)1+i.%])&1e4
   (,.f"0) 1 3 6 10 25 50 100
  1      0
  3  1.635
  6 1.5686
 10 1.5084
 25 1.4585
 50 1.4485
100 1.4456
   f 1000
1.4446

Erläuterung

(>./@(]*[>^/@#"0)1+i.%])&1e4  Input: n
                         1e4  The constant 10000
(                      )      Operate on n (LHS) and 10000 (RHS)
                   i.           The range [0, 10000)
                      ]         Get (RHS) 10000
                     %          Divide each in the range by 10000
                 1+             Add 1 to each
     (          )               Operate on n (LHS) and the range (RHS)
             #"0                  For each in the range, create a list of n copies
          ^/@                     Reduce each list of copies using exponentation
                                  J parses from right-to-left which makes this
                                  equivalent to the tetration
        [                         Get n
         >                        Test if each value is less than n
      ]                           Get the initial range
       *                          Multiply elementwise
 >./@                           Reduce using max and return

Python, 184 Bytes

def s(n):
 def j(b,i):
  if i<0.1**12:
   return b
  m = b+i
  try:
   v = reduce(lambda a,b:b**a,[m]*n)
  except:
   v = n+1
  return j(m,i/2) if v<n else j(b,i/2)
 return j(1.0,0.5)

Testausgabe (Überspringen der tatsächlichen Druckanweisungen):

   s(1) 1.0
   s(3) 1.63507847464
   s(6) 1.5686440646
  s(10) 1.50849792026
  s(25) 1.45858186605
  s(50) 1.44850389566
 s(100) 1.44567285047

Schläger 187 Bytes

(define(f x n)(define o 1)(for((i n))(set! o(expt x o)))o)
(define(ur y(l 0.1)(u 10))(define t(/(+ l u)2))(define o(f t y))
(cond[(<(abs(- o y)) 0.1)t][(> o y)(ur y l t)][else(ur y t u)]))

Testen:

(ur 1)
(ur 3)
(ur 6)
(ur 10)
(ur 25)
(ur 50)
(ur 100)

Ausgabe:

1.028125
1.6275390625
1.5695312499999998
1.5085021972656247
1.4585809230804445
1.4485038772225378
1.4456728475168346

Ausführliche Version:

(define (f x n)
  (define out 1)
  (for((i n))
    (set! out(expt x out)))
  out)

(define (uniroot y (lower 0.1) (upper 10))
  (define trying (/ (+ lower upper) 2))
  (define out (f trying y))
  (cond
    [(<(abs(- out y)) 0.1)
     trying]
    [(> out y)
     (uniroot y lower trying)]
    [else
      (uniroot y trying upper)]))

Perl 6 , 42 Bytes

{(0,.0001…2).min:{abs $_-[**] $^r xx$_}}

(Übersetzung eines Matlab-Beispielcodes)

Prüfung:

#! /usr/bin/env perl6
use v6.c;
use Test;

my &code = {(0,.0001…2).min:{abs $_-[**] $^r xx$_}}

my @tests = (
  1   => 1,
  3   => 1.635078,
  6   => 1.568644,
  10  => 1.508498,
  25  => 1.458582,
  50  => 1.448504,
  100 => 1.445673,
);

plan +@tests + 1;

my $start-time = now;

for @tests -> $_ ( :key($input), :value($expected) ) {
  my $result = code $input;
  is-approx $result, $expected, "$result ≅ $expected", :abs-tol(0.001)
}

my $finish-time = now;
my $total-time = $finish-time - $start-time;
cmp-ok $total-time, &[<], 60, "$total-time.fmt('%.3f') is less than a minute";

1..8
ok 1 - 1 ≅ 1
ok 2 - 1.6351 ≅ 1.635078
ok 3 - 1.5686 ≅ 1.568644
ok 4 - 1.5085 ≅ 1.508498
ok 5 - 1.4586 ≅ 1.458582
ok 6 - 1.4485 ≅ 1.448504
ok 7 - 1.4456 ≅ 1.445673
ok 8 - 53.302 seconds is less than a minute

PHP, 103 Bytes

$z=2;while($z-$a>9**-9){for($r=$s=($a+$z)/2,$i=0;++$i<$n=$argv[1];)$r=$s**$r;$r<$n?$a=$s:$z=$s;}echo$s;

Axiom 587 Bytes

l(a,b)==(local i;i:=1;r:=a;repeat(if i>=b then break;r:=a^r;i:=i+1);r);g(q,n)==(local r,y,y1,y2,t,v,e,d,i;n<=0 or n>1000 or q>1000 or q<0 => 0;e:=1/(10**(digits()-3));v:=0.01; d:=0.01;repeat(if l(v,n)>=q then break;v:=v+d;if v>=1 and n>25 then d:=0.001;if v>=1.4 and n>40 then d:=0.0001;if v>=1.44 and n>80 then d:=0.00001;if v>=1.445 and n>85 then d:=0.000001);if l(v-d,n)>q then y1:=0.0 else y1:=v-d;y2:=v;y:=l(v,n);i:=1;if abs(y-q)>e then repeat(t:=(y2-y1)/2.0;v:=y1+t;y:=l(v,n);i:=i+1;if i>100 then break;if t<=e then break;if y<q then y1:=v else y2:=v);if i>100 then output "#i#";v)

weniger Golf + Zahlen

l(a,b)==
  local i
  i:=1;r:=a;repeat(if i>=b then break;r:=a^r;i:=i+1)
  r
g(q,n)==
 local r, y, y1,y2,t,v,e,d, i
 n<=0 or n>1000 or q>1000 or q<0 => 0  
 e:=1/(10**(digits()-3))
 v:=0.01; d:=0.01  
 repeat  --cerco dove vi e' il punto di cambiamento di segno di l(v,n)-q
    if l(v,n)>=q then break
    v:=v+d 
    if v>=1     and n>25 then d:=0.001
    if v>=1.4   and n>40 then d:=0.0001
    if v>=1.44  and n>80 then d:=0.00001
    if v>=1.445 and n>85 then d:=0.000001
 if l(v-d,n)>q then y1:=0.0
 else               y1:=v-d 
 y2:=v; y:=l(v,n); i:=1  -- applico il metodo della ricerca binaria
 if abs(y-q)>e then      -- con la variabile i di sicurezza
    repeat 
       t:=(y2-y1)/2.0; v:=y1+t; y:=l(v,n)
       i:=i+1
       if i>100 then break
       if t<=e  then break 
       if  y<q  then y1:=v
       else          y2:=v
 if i>100 then output "#i#"
 v

(3) -> [g(1,1), g(3,3), g(6,6), g(10,10), g(25,25), g(50,50), g(100,100)]
   Compiling function l with type (Float,PositiveInteger) -> Float
   Compiling function g with type (PositiveInteger,PositiveInteger) ->
      Float

   (3)
   [1.0000000000 000000001, 1.6350784746 363752387, 1.5686440646 047324687,
    1.5084979202 595960768, 1.4585818660 492876919, 1.4485038956 661040907,
    1.4456728504 738144738]
                                                             Type: List Float

Common Lisp, 207 Bytes

(defun superlog(n)(let((a 1d0)(i 0.5))(loop until(< i 1d-12)do(let((v(or(ignore-errors(reduce #'expt(loop for q below n collect(+ a i)):from-end t))(1+ n))))(when(< v n)(setq a (+ a i)))(setq i(/ i 2)))) a))

Durch die Verwendung von reducewith wird :from-end tdie Notwendigkeit einer "Umkehrung der Exponentiation" von Lambda-Zwischenwerten vermieden (im Grunde (lambda (x y) (expt y x))werden 14 Byte gespart (12, wenn Sie entfernbare Leerzeichen entfernen).

Wir müssen den Float-Überlauf noch behandeln, aber ein ignore-errorsFormular wird zurückgegeben, nilwenn ein Fehler aufgetreten ist, sodass wir oreinen Standardwert bereitstellen können.