Étant donné un entier positif n et un nombre a , la n -ième tétration de a est définie comme un ^ ( a ^ ( a ^ (... ^ a ))), où ^ désigne l'exponentiation (ou la puissance) et l'expression contient le nombre a exactement n fois.

En d'autres termes, la tétration est une exponentiation itérative associative à droite. Pour n = 4 et a = 1,6, la tétration est de 1,6 ^ (1,6 ^ (1,6 ^ 1,6)) ≈ 3,5743.

La fonction inverse de la tétration par rapport à n est le super-logarithme . Dans l'exemple précédent, 4 est le super-logarithme de 3,5743 avec "super-base" 1,6.

Le défi

Étant donné un entier positif n , trouvez x tel que n est le super-logarithme de lui-même dans la super-base x . Autrement dit, trouver x tel que x ^ ( x ^ ( x ^ (... ^ x ))) (avec x apparaissant n fois) est égal à n .

Règles

Programme ou fonction autorisé.

Les formats d'entrée et de sortie sont flexibles comme d'habitude.

L'algorithme devrait théoriquement fonctionner pour tous les entiers positifs. En pratique, l'entrée peut être limitée à une valeur maximale en raison de restrictions de mémoire, de temps ou de type de données. Cependant, le code doit fonctionner pour les entrées jusqu'à 100au moins en moins d'une minute.

L'algorithme devrait théoriquement donner le résultat avec 0.001précision. En pratique, la précision de sortie peut être pire en raison des erreurs accumulées dans les calculs numériques. Cependant, la sortie doit être précise jusqu'à 0.001pour les cas de test indiqués.

Le code le plus court gagne.

Cas de test

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

Implémentation de référence

Voici une implémentation de référence dans Matlab / Octave (essayez-la sur 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)

Car N = 10cela donne result = 1.5085.

Le code suivant est une vérification de la précision de sortie, à l'aide d'une arithmétique à précision variable:

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

Cela donne:

• Pour x = 1.5085:y = 10.00173...
• Pour x = 1.5085 + .001:y = 10.9075
• Car x = 1.5085 - .001ça donne y = 9.23248.

1.5085est donc une solution valable avec .001précision.

Dyalog APL , 33 25 octets

Besoins ⎕IO←0par défaut sur de nombreux systèmes.

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

Calcule théoriquement pour tous les entiers, mais pratiquement limité à un très petit seul.

TryAPL en ligne!

Haskell, 55 54 52 octets

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

Usage:

> s 100
1.445600000000061

Merci à @nimi pour 1 octet!
Merci à @xnor pour 2!

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

ES6

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

ES7

Utilisation **comme suggéré par DanTheMan:

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

Exemple

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 octets

Merci à murphy pour une économie de près de 20%!

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

Nest[x^#&,1,n]produit la nième tétration de x. Teste donc Nest[x^#&,1,#]<#si la (entrée) e tétration de x est inférieure à (entrée). Nous commençons simplement à x = 1 et ajoutons 0,001 à plusieurs reprises jusqu'à ce que la tétration soit trop grande, puis sortons la dernière valeur x (donc la réponse est garantie d'être plus grande que la valeur exacte, mais dans 0,001).

Comme j'apprends lentement: //.x_:>y/;zou //.x_/;z:>ysignifie "rechercher tout ce qui correspond au modèle x, mais uniquement les choses pour lesquelles le test z renvoie vrai; puis opérer sur x par la règle y; à plusieurs reprises jusqu'à ce que rien ne change". Ici, le modèle x_est simplement "n'importe quel nombre que je vois", bien que dans d'autres contextes, il puisse être encore plus contraint.

Lorsque l'entrée est d'au moins 45, la tétration augmente si rapidement que cette dernière étape provoque une erreur de débordement; mais la valeur de x est toujours mise à jour et émise correctement. La diminution de la taille de pas de 0,001 à 0,0001 corrige ce problème pour les entrées jusqu'à 112, et donne une réponse plus précise au démarrage (et fonctionne toujours rapidement, en environ un quart de seconde). Mais c'est un octet supplémentaire, alors oubliez ça!

Version originale:

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

J, 39 31 28 octets

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

Basé sur l'implémentation de référence. Il n'est précis qu'à trois décimales près.

8 octets enregistrés en utilisant la méthode de la solution de @ Adám .

Usage

Commandes supplémentaires utilisées pour formater plusieurs entrées / sorties.

   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

Explication

(>./@(]*[>^/@#"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 octets

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)

Sortie de test (en ignorant les instructions d'impression réelles):

   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

Raquette 187 octets

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

Essai:

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

Production:

1.028125
1.6275390625
1.5695312499999998
1.5085021972656247
1.4585809230804445
1.4485038772225378
1.4456728475168346

Version détaillée:

(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 octets

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

(Traduction d'un exemple de code Matlab)

Tester:

#! /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 octets

$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;

Axiome 587 octets

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)

moins de golf + numéros

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

Lisp commun, 207 octets

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

L'utilisation de reducewith :from-end tévite la nécessité de faire une lambda intermédiaire "exponentiation inversée" (en gros (lambda (x y) (expt y x)), économiser 14 octets (12, si vous supprimez les espaces amovibles).

Nous devons toujours gérer le débordement du flottant, mais un ignore-errorsformulaire retourne nilsi une erreur s'est produite, nous pouvons donc utiliser orpour fournir une valeur par défaut.