18
\$\begingroup\$

Given a positive integer n and a number a, the n-th tetration of a is defined as a^(a^(a^(...^a))), where ^ denotes exponentiation (or power) and the expression contains the number a exactly n times.

In other words, tetration is right-associative iterated exponentiation. For n=4 and a=1.6 the tetration is 1.6^(1.6^(1.6^1.6)) ≈ 3.5743.

The inverse function of tetration with respect to n is the super-logarithm. In the previous example, 4 is the super-logarithm of 3.5743 with "super-base" 1.6.

The challenge

Given a positive integer n, find x such that n is the super-logarithm of itself in super-base x. That is, find x such that x^(x^(x^(...^x))) (with x appearing n times) equals n.

Rules

Program or function allowed.

Input and output formats are flexible as usual.

The algorithm should theoretically work for all positive integers. In practice, input may be limited to a maximum value owing to memory, time or data-type restrictions. However, the code must work for inputs up to 100 at least in less than a minute.

The algorithm should theoretically give the result with 0.001 precision. In practice, the output precision may be worse because of accumulated errors in numerical computations. However, the output must be accurate up to 0.001 for the indicated test cases.

Shortest code wins.

Test cases

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

Reference implementation

Here's a reference implementation in Matlab / Octave (try it at 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)

For N = 10 this gives result = 1.5085.

The following code is a check of the output precision, using variable-precision arithmetic:

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

This gives:

  • For x = 1.5085: y = 10.00173...
  • For x = 1.5085 + .001: y = 10.9075
  • For x = 1.5085 - .001 it gives y = 9.23248.

so 1.5085 is a valid solution with .001 precision.

\$\endgroup\$
  • \$\begingroup\$ Related. The differences are that the (super-)base of the super-logarithm here is not fixed, and the result is not an integer in general. \$\endgroup\$ – Luis Mendo Sep 14 '16 at 8:49
  • \$\begingroup\$ It seems like the function converges rather quickly. If our algorithm is simply a curve fit that's within 0.001, does that count as theoretically working for all positive integers? \$\endgroup\$ – xnor Sep 14 '16 at 9:32
  • 2
    \$\begingroup\$ Hmm, wolframalpha already has trouble with test case 6.. "Standard computation time exceeded..." \$\endgroup\$ – Kevin Cruijssen Sep 14 '16 at 9:48
  • \$\begingroup\$ @KevinCruijssen I have a reference implementation in Matlab based on binary search which is reasonably fast. I can post it if that's helpful \$\endgroup\$ – Luis Mendo Sep 14 '16 at 9:57
  • 1
    \$\begingroup\$ Does x converge as n approaches infinity? \$\endgroup\$ – mbomb007 Sep 16 '16 at 14:49

11 Answers 11

3
\$\begingroup\$

Dyalog APL, 33 25 bytes

Needs ⎕IO←0 which is default on many systems.

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

Theoretically calculates for all integers, but practically limited to very small one only.

TryAPL online!

\$\endgroup\$
  • \$\begingroup\$ Does it work fast enough on the input 100? \$\endgroup\$ – Greg Martin Sep 14 '16 at 22:28
  • \$\begingroup\$ @GregMartin Not enough memory. \$\endgroup\$ – Adám Sep 14 '16 at 22:31
10
\$\begingroup\$

Haskell, 55 54 52 bytes

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

Usage:

> s 100
1.445600000000061

Thanks to @nimi for 1 byte!
Thanks to @xnor for 2!

\$\endgroup\$
  • 1
    \$\begingroup\$ [ ]!!0 instead of head[ ] saves a byte \$\endgroup\$ – nimi Sep 14 '16 at 22:04
  • 1
    \$\begingroup\$ s n=[x|x<-[2,1.9999..],n>iterate(x**)1!!n]!!0 would be shorter if you could get Haskell to accept its types. \$\endgroup\$ – xnor Sep 15 '16 at 0:07
  • \$\begingroup\$ @xnor I played around with iterate when I wrote it actually, but somehow it turned out longer at the time \$\endgroup\$ – BlackCap Sep 15 '16 at 0:15
6
\$\begingroup\$

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

ES6

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

ES7

Using ** as suggested by DanTheMan:

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

Example

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

\$\endgroup\$
  • \$\begingroup\$ If you use ES7, you can use ** instead of Math.pow. \$\endgroup\$ – DanTheMan Sep 14 '16 at 18:07
4
\$\begingroup\$

Mathematica, 40 33 bytes

Thanks to murphy for an almost 20% savings!

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

Nest[x^#&,1,n] produces the nth tetration of x. So Nest[x^#&,1,#]<# tests whether the (input)th tetration of x is less than (input). We simply start at x=1 and add 0.001 repeatedly until the tetration is too large, then output the last x value (so the answer is guaranteed to be larger than the exact value, but within 0.001).

As I'm slowly learning: //.x_:>y/;z or //.x_/;z:>y means "look for anything that matches the template x, but only things for which the test z returns true; and then operate on x by the rule y; repeatedly until nothing changes". Here the template x_ is just "any number I see", although in other contexts it could be further constrained.

When the input is at least 45, the tetration increases so rapidly that that last step causes an overflow error; but the value of x is still updated and output correctly. Decreasing the step-size from 0.001 to 0.0001 fixes this problem for inputs up to 112, and gives a more precise answer to boot (and still runs quickly, in about a quarter second). But that's one extra byte, so forget that!

Original version:

x=1;(While[Nest[x^#&,1,#]<#,x+=.001];x)&
\$\endgroup\$
  • \$\begingroup\$ Golfed it a bit: 1//.x_:>x+.001/;Nest[x^#&,1,#]<#& \$\endgroup\$ – murphy Sep 14 '16 at 20:11
  • \$\begingroup\$ @murphy: great! I swear I'll yet get to the point where I can use //. without help :) \$\endgroup\$ – Greg Martin Sep 14 '16 at 22:21
4
\$\begingroup\$

J, 39 31 28 bytes

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

Based on the reference implementation. It is only accurate to three decimal places.

Saved 8 bytes using the method from @Adám's solution.

Usage

Extra commands used to format multiple input/output.

   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

Explanation

(>./@(]*[>^/@#"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
\$\endgroup\$
4
\$\begingroup\$

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)

Test output (skipping the actual print statements):

   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
\$\endgroup\$
  • \$\begingroup\$ golfed to 119 bytes \$\endgroup\$ – mbomb007 Sep 16 '16 at 15:16
  • \$\begingroup\$ It computes s(1000000) pretty quickly \$\endgroup\$ – mbomb007 Sep 16 '16 at 15:39
3
\$\begingroup\$

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

Testing:

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

Output:

1.028125
1.6275390625
1.5695312499999998
1.5085021972656247
1.4585809230804445
1.4485038772225378
1.4456728475168346

Detailed 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)]))
\$\endgroup\$
2
\$\begingroup\$

Perl 6, 42 bytes

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

( Translation of example Matlab code )

Test:

#! /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
\$\endgroup\$
1
\$\begingroup\$

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;
\$\endgroup\$
1
\$\begingroup\$

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)

less golfed + numbers

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
\$\endgroup\$
1
\$\begingroup\$

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

Using reduce with :from-end t avoids the need of doing a "reversing exponentiation" intermediate lambda (basically (lambda (x y) (expt y x)), saving 14 bytes (12, if you remove removable spaces).

We still need to handle float overflow, but an ignore-errors form returns nil if an error happened, so we can use or to provide a default value.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.