Which really big number is bigger?

Question

This question is tricky (and in particular harder than Which big number is bigger?), for those who like more challenging puzzles.

Input

Integers a1, a2, a3, a4, a5, b1, b2, b3, b4, b5 each in the range 1 to 10.

Output

True if a1^(a2^(a3^(a4^a5))) > b1^(b2^(b3^(b4^b5))) and False otherwise.

^ is exponentiation in this question.

Rules

This is code-golf. Your code must terminate correctly within 10 seconds for any valid input on TIO. If your language is not on TIO, the code should finish under 10 seconds on your machine.

You can output anything Truthy for True and anything Falsey for False.

Test cases

Recall that by the rules of exponentiaon, a1^(a2^(a3^(a4^a5))) == a1^a2^a3^a4^a5.

10^10^10^10^10 > 10^10^10^10^9
1^2^3^4^5 < 5^4^3^2^1
2^2^2^2^3 > 10^4^3^2^2
6^7^8^9^10 is not bigger than 6^7^8^9^10
10^6^4^2^2 < 10^6^2^4^2
2^2^2^2^10 > 2^2^2^10^2
10^9^8^7^6 < 6^7^8^9^10 
3^1^10^10^10 > 2^1^10^10^10 
9^10^10^10^10 < 10^9^10^10^10

New test cases from Kevin Cruijssen

[10,10,10,10,10, 10,10,10,10,9] #true
[2,2,2,2,3,      10,4,3,2,2]    #true
[2,2,2,2,10,     2,2,2,10,2]    #true
[10,10,10,10,10, 9,10,10,10,10] #true
[3,2,2,1,1,      2,5,1,1,1]     #true
[2,2,3,10,1,     2,7,3,9,1]     #true
[7,9,10,10,10,   6,9,10,10,10]  #true
[3,2,2,2,2,      2,2,2,2,2]     #true
[8,3,1,2,1,      2,2,3,1,1]     #true
[2,4,2,1,1,      3,3,2,1,1]     #true
[5,4,3,2,1,      1,2,3,4,5]     #true

[1,2,3,4,5,      5,4,3,2,1]     #false
[6,7,8,9,10,     6,7,8,9,10]    #false
[10,6,4,2,2,     10,6,2,4,2]    #false
[10,9,8,7,6,     6,7,8,9,10]    #false
[1,10,10,10,10,  1,10,10,10,9]  #false
[2,4,1,1,1,      2,2,2,1,1]     #false
[2,2,2,1,1,      2,4,1,1,1]     #false
[2,5,1,1,1,      3,2,2,1,1]     #false
[4,2,1,1,1,      2,4,1,1,1]     #false
[2,4,1,1,1,      4,2,1,1,1]     #false
[2,3,10,1,1,     8,3,9,1,1]     #false
[8,3,9,1,1,      2,3,10,1,1]    #false
[2,4,1,1,1,      3,3,1,1,1]     #false
[2,2,1,9,9,      2,2,1,10,10]   #false
[2,2,1,10,10,    2,2,1,9,9]     #false
[1,1,1,1,1,      1,2,1,1,1]     #false

Answer 1

Ruby, 150 bytes

See revisions for previous byte counts.

->a,b,c,d,e,f,g,h,i,j{l=->s,t=c{Math.log(s,t)};y,z=l[l[g,b]]-d**e+l[h]*i**=j,l[l[a,f]*b**c,g];a>1?f<2?1:b<2||g<2?z>h:c<2||d<2?l[z,h]>i:y==0?a>f:y<0:p}

-10 bytes thanks to @ValueInk

+16 bytes thanks to @RosLuP for bugs.

Try it online.

Compare different base powers-towers (of 'height' five)?

Ungolfed code:

-> a, b, c, d, e, f, g, h, i, j {
    l =-> s, t = c {Math.log(s, t)}
    i **= j
    y = l[l[g, b]] - d ** e + l[h] * i
    z = l[l[a, f] * b ** c, g]
    if a == 1
        return p
    elsif f == 1
        return 1
    elsif b == 1 || g == 1
        return z > h
    elsif d == 1 || c == 1
        return l[z, h] > i
    elsif y == 0
        return a > f
    else
        return y < 0
    end
}

Code breakdown:

l =-> s, t = c {Math.log(s, t)}

This is the base t logarithm, which will be used to reduce the size of the numbers we are comparing. It defaults to base c when only one argument is given.

i **= j
y = l[l[g, b]] - d ** e + l[h] * i
z = l[l[a, f] * b ** c, g]

This updates i = i ** j since i never gets used on it's own, and y is the result of logging b^c^d^e == g^h^i(^j) twice and moving everything to one side. We then let z = l[a, f] * b ** c as the log base g of the log base f of a ** b ** c.

if a == 1
    return p
elsif f == 1
    return 1

1^b^c^d^e = 1 is never greater than f^g^h^i^j, and likewise, a^b^c^d^e is always greater than 1^g^h^i^j = 1 if a != 1. Note that return p returns nil, which is falsey, and return 1 returns 1, which is truthy.

elsif b == 1
    return z > h

If b == 1 or g == 1, then this reduces to comparing a ** b ** c to f ** g ** h, which is done with two logs to both sides.

elsif d == 1 || c == 1
    return l[z, h] > i

This compares a ** b ** c with f ** g ** h ** i by rearranging it as log[log[b ** c * log[a, f], g], h] compared to i. (Recall that i **= j in the beginning and z = log[b ** c * log[a, f], g].)

elsif y == 0
    return a > f
else
    return y < 0
end

This compares the 4 highest powers after logging both sides twice. If they are equal, it compares the base.

Answer 2

Python 2, 671 612 495 490 611 597 bytes

lambda a,b:P(S(a,b))>P(S(b,a))if P(a)==P(b)else P(a)>P(b)
def S(a,b):
  if a and a[-1]==b[-1]:
    a.pop()
    b.pop()
    return S(a,b)
from math import*
L=log
E=exp
N=lambda m,n,x:N(m,n+1,L(x))if x>=1else N(m,n-1,E(x))if x<0else(m+n,x)
A=lambda a,n,x:(0,1)if a==1else(1,R(x,n)*L(a))if a<1else N(2,*C(L(L(a)),x,n-1))if n else(1,x*L(a))
def C(c,x,n):
 if c*n==0:return(0if c else n,x+c)
 z=R(x,n-1)
 if z<=L(abs(c)):return(0,E(z)+c)
 return N(1,*C(L(1-E(L(-c)-z)if c<0else 1+E(L(c)-z)),x,n-1))
def R(x,n):
 try:exec'x=E(x)'*n
 except:x=float('inf')
 return x
P=lambda b:b and N(0,*A(b[0],*P(b[1:])))or(0,1)

-59 bytes thanks to @EmbodimentOfIgnorance
-117 bytes thanks to @Neil
+121 bytes for about five bug-fixes, all found by @ngn

Takes the inputs as two lists. NOTE: Also works with larger lists or those of unequal length. EDIT: No longer true; it still works if P(a) and P(b) result in different tuples, but if they are the same this updated code above only works with lists with a fixed size of 5 now.

Try it online.

Explanation:

Golfed version of this answer on math.stackexchange.com, so all credit goes to @ThomasAhle.

To quote his answer:

The idea is to represent power towers as a single floating point number with \$n\$ exponentiations: \$(x\mid n) := exp^n(x)\$. Normalizing \$x\in[0,1)\$, this format allows easy comparison between numbers.

What remains is a way to calculate \$a^{(x\mid n)}\$ for any real, positive \$a\$. My Python code below is an attempt to do so, while being as numerically stable as possibly, e.g. by using the log-sum trick. My code runs in time proportional to the height of the tower (number of apow calls) and the iterated-log of it's value (number of recursive calls).

I haven't been able to find two towers with values close enough to case my method to fail. At least for integer exponents. With fractional exponents it is possible to create very towers too close for my representation to handle. E.g. \$2^{2^{2^{2^0}}}<2^{2^{2^{2^{(1/2)^{2^{2^{2^2}}}}}}}\$

I would be interested in suggestions to other types of counter examples, especially integer ones.

It seems to me that for the problem to be in P, we need to non-numerical methods. It doesn't seem unlikely at all, that certain analytical cases are harder than P.

Examples:

powtow([2,2,2,2,2,2,2,2,2,2,2,2,2,2,4,2,2,2]) = (0.1184590219613409, 18)
powtow([9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9]) = (0.10111176550354063, 18)

powtow([2,2,5,2,7,4,9,3,7,6,9,9,9,9,3,2]) = (0.10111176550354042, 17)
powtow([3,3,6,3,9,4,2,3,2,2,2,2,2,3,3,3]) = (0.19648862015624008, 17)

Counter examples:

powtow([2,2,2,2,2,2,2]) = (0.8639310719129168, 6)
powtow([3,2,2,2,2,2,2]) = (0.8639310719129168, 6)

Regarding the counter examples, he mentions the following in the comment-section:

I believe if we bound the exponents so \$1<a<100\$ (or maybe a much larger upper bound) we can use my method for comparing the height 3 or 4 head of the tower. It should be strong enough to tell us if they are equal or one is larger. Plan B is to choose the highest tower. Plan C is the interesting one: At this point the values of the rest of the tower only matter if the heads are equal, so we can walk down the towers in parallel, stopping as soon as we see a differing value.

Hence the main thing to be proven is that once the head of a tower exceeds a certain point, and the rest of the exponents are bounded (and equally numerous), we can simply look at the top differing value. It's a bit counter intuitive, but it seems very likely from the simple inequalities you get.

Since plan A and B are irrelevant in this challenge, since the height is 5 for both power-towers we input, plan C it is. So I've changed P(a)>P(b) to P(S(a,b))>P(S(b,a))if P(a)==P(b)else P(a)>P(b) with the recursive function S(a,b). If P(a) and P(b) result in the same tuple, the P(S(a,b))>P(S(b,a)) will first remove trailing values which are equal at the same indices, before doing to same P(A)>P(B) check on these now shorter lists.

Answer 3

05AB1E, 96 104 bytes

3èI4èmU8.$`m©I7èI2è.n*I6èI1è.nI2è.n+Vнi0ë5èi1ë2ô1èßi¦2£`mIнI5è.n*I6è.nDI7èDi\1›·<žm*ë.n}®›ëXYQiнI5è›ëXY›

Port of @SimplyBeautifulArt's Ruby answer, so make sure to upvote him!

+8 bytes as work-around, because \$\log_1(x)\$ should result in POSITIVE_INFINITY for \$x\gt1\$ and NEGATIVE_INFINITY for \$x\lt1\$, but results in 0.0 for both cases instead in 05AB1E (i.e. test cases [3,2,2,1,1,2,5,1,1,1] (POSITIVE_INFINITE case) and [2,4,1,1,1,3,3,1,1,1] (NEGATIVE_INFINITY case).

Input as a list of ten integers: [a,b,c,d,e,f,g,h,i,j].

Try it online or verify all test cases.

Explanation:

3èI4èm         # Calculate d**e
      U        # And pop and store it in variable `X`
8.$`m          # Calculate i**j
     ©         # Store it in variable `®` (without popping)
I7èI2è.n       # Calculate c_log(h)
 *             # Multiply it with i**j that was still on the stack: i**j * c_log(h)
I6èI1è.nI2è.n  # Calculate c_log(b_log(g))
 +             # And sum them together: i**j * c_log(h) + c_log(b_log(g))
  V            # Pop and store the result in variable `Y`

нi             # If `a` is 1:
 0             #  Push 0 (falsey)
ë5èi           # Else-if `f` is 1:
 1             #  Push 1 (truthy)
ë2ô1èßi        # Else-if the lowest value of [c,d] is 1:
 ¦2£`m         #  Calculate b**c
 IнI5è.n       #  Calculate f_log(a)
  *            #  Multiply them together: b**c * f_log(a)
   I6è.n       #  Calculate g_log(^): g_log(b**c * f_log(a))
 D             #  Duplicate it
  I7è          #  Push h
     Di        #  Duplicate it as well, and if h is exactly 1:
       \       #   Discard the duplicated h
       1›      #   Check if the calculated g_log(b**c * f_log(a)) is larger than 1
               #   (which results in 0 for falsey and 1 for truthy)
         ·<    #   Double it, and decrease it by 1 (it becomes -1 for falsey; 1 for truthy)
           žm* #   Multiply that by 9876543210 (to mimic POSITIVE/NEGATIVE INFINITY)
      ë        #  Else:
       .n      #   Calculate h_log(g_log(b**c * f_log(a))) instead
      }        #  After the if-else:
       ®›      #  Check whether the top of the stack is larger than variable `®`
ëXYQi          # Else-if variables `X` and `Y` are equal:
     нI5è›     #  Check whether `a` is larger than `f`
ë              # Else:
 XY›           #  Check whether `X` is larger than `Y`
               # (after which the top of the stack is output implicitly as result)

If anyone wants to try and golf it further, here is a helper program I've used to get the correct variables from the input-list.

Answer 4

C, 168 180 bytes

C port from Kevin Cruijssen's answer.

#define l(a,b)log(a)/log(b)
z(a,b,c,d,e,f,g,h,i,j){float t=pow(i,j),y=l(l(g,b),c)-pow(d,e)+l(h,c)*t,z=l(l(a,f)*pow(b,c),g);return~-a&&f<2|(b<2|g<2?z>h:c<2|d<2?l(z,h)>t:y?y<0:a>f);}

Try it online

Answer 5

APL(NARS), chars 118, bytes 236

{p←{(a b c d)←⍵⋄a=1:¯1⋄b=1:⍟⍟a⋄(⍟⍟a)+(c*d)×⍟b}⋄(=/(a b)←{p 1↓⍵}¨⍺⍵)∧k←(∞ ∞)≡(m n)←{p(3↑⍵),*/3↓⍵}¨⍺⍵:(↑⍺)>↑⍵⋄k:a>b⋄m>n}

The function above call z, in "a z w" would return 1 if the number in a is greater than the number in w, otherwise it would return 0.

If I have

f(a,b,c,d,e)=a^b^c^d^e

It will be f(aa)>f(bb) with both aa and bb array of 5 positive numbers if and only if (if the a>1 of aa and bb) log(log(f(aa)))>log(log(f(bb))) one has to use the log() laws:

log(A*B)=log(A)+log(B)
log(A^B)=B*log(A)

for build v(aa)=log(log(aa))=v(a,b,c,d,e)=log(log(a))+log(b)(c^(d^e))={p(3↑⍵),/3↓⍵} function and so the exercise is find when v(aa)>v(bb).

But there is a case where v(aa) and v(bb) are both infinite (APL has end the float space) in that case i would use the unsecure function

s(a,b,c,d,e)=log(log(b))+log(c)*(d^e)={p 1↓⍵}

that i not fully understand if it is ok and it not take in count a parameter too... test:

  z←{p←{(a b c d)←⍵⋄a=1:¯1⋄b=1:⍟⍟a⋄(⍟⍟a)+(c*d)×⍟b}⋄(=/(a b)←{p 1↓⍵}¨⍺⍵)∧k←(∞ ∞)≡(m n)←{p(3↑⍵),*/3↓⍵}¨⍺⍵:(↑⍺)>↑⍵⋄k:a>b⋄m>n}
  10 10 10 10 10 z 10 10 10 10 9
1
  1 2 3 4 5 z 5 4 3 2 1
0
  2 2 2 2 3 z 10 4 3 2 2
1
  10 6 4 2 2 z 10 6 2 4 2
0
  2 2 2 2 10 z 2 2 2 10 2
1
  10 9 8 7 6 z 6 7 8 9 10
0
  10 10 10 10 10 z 10 10 10 10 9
1      
  2 2 2 2 3   z    10 4 3 2 2
1
  2 2 2 2 10   z   2 2 2 10 2
1
  10 10 10 10 10 z 9 10 10 10 10
1
  3 2 2 1 1   z    2 5 1 1 1
1
  2 2 3 10 1  z    2 7 3 9 1
1
  7 9 10 10 10 z   6 9 10 10 10
1
  3 2 2 2 2    z   2 2 2 2 2
1
  3 10 10 10 10 z  2 10 10 10 10
1
  8 3 1 2 1    z   2 2 3 1 1
1
  2 4 2 1 1    z   3 3 2 1 1
1
  5 4 3 2 1    z   1 2 3 4 5
1
  1 2 3 4 5    z   5 4 3 2 1
0
  6 7 8 9 10    z  6 7 8 9 10
0
  10 6 4 2 2 z     10 6 2 4 2
0
  10 9 8 7 6  z   6 7 8 9 10
0
  1 10 10 10 10 z 1 10 10 10 9
0
  2 4 1 1 1 z     2 2 2 1 1
0
  2 2 2 1 1    z  2 4 1 1 1
0
  2 5 1 1 1   z   3 2 2 1 1
0
  4 2 1 1 1   z   2 4 1 1 1
0
  2 4 1 1 1   z   4 2 1 1 1
0
  2 3 10 1 1  z   8 3 9 1 1
0
  8 3 9 1 1   z   2 3 10 1 1
0
  2 4 1 1 1   z   3 3 1 1 1
0
  2 2 1 9 9   z   2 2 1 10 10
0
  2 2 1 10 10 z   2 2 1 9 9
0
  1 1 1 1 1   z   1 2 1 1 1
0
  1 1 1 1 2   z   1 1 1 1 1
0
  1 1 1 1 1   z   1 1 1 1 1
0
  9 10 10 10 10 z  10 9 10 10 10
1
  9 10 10 10 10 z  10 10 10 10 10
0
  10 10 10 10 10 z  10 10 10 10 10
0
  11 10 10 10 10 z  10 10 10 10 10
1

Answer 6

Java 8, 299 288 286 252 210 208 224 bytes

Math M;(a,b,c,d,e,f,g,h,i,j)->{double t=M.pow(i,j),y=l(l(g,b),c)-M.pow(d,e)+l(h,c)*t,z=l(l(a,f)*M.pow(b,c),g);return a>1&&f<2|(b<2|g<2?z>h:c<2|d<2?l(z,h)>t:y==0?a>f:y<0);}double l(double...A){return M.log(A[0])/M.log(A[1]);}

Port of @SimplyBeautifulArt's Ruby answer, so make sure to upvote him!
-14 bytes thanks to @SimplyBeautifulArt.
+17 bytes for the same bug-fixes as the Ruby answer.

Try it online.

Explanation:

Math M;                      // Math M=null on class-level to save bytes

(a,b,c,d,e,f,g,h,i,j)->{     // Method with ten integer parameters and boolean return-type
  double t=M.pow(i,j),       //  Temp `t` = `i` to the power `j`
    y=l(l(g,b),c)            //  Temp `y` = `c`_log(`b`_log(`g`))
      -M.pow(d,e)            //  - `d` to the power `e`
      +l(h,c)*t,             //  + `c`_log(`h`) * `t`
    z=l(l(a,f)*M.pow(b,c),g);//  Temp `z` = `g`_log(`f`_log(`a`) * `b` to the power `c`)
  return a>1&&               //  If `a` is 1:
                             //   Return false
   f<2|(                     //  Else-if `f` is 1:
                             //   Return true
    b<2|g<2?                 //  Else-if either `b` or `g` is 1:
     z>h                     //   Return whether `z` is larger than `h`
    :c<2|d<2?                //  Else-if either `c` or `d` is 1:
     l(z,h)>t                //    Return whether `h`_log(`z`) is larger than `t`
    :y==0?                   //   Else-if `y` is 0:
      a>f                    //    Return whether `a` is larger than `f`
    :                        //   Else:
     y<0);}                  //    Return whether `y` is negative

// Separated method to calculate `B`_log(`A`) for inputs `A,B`
double l(double...A){return M.log(A[0])/M.log(A[1]);}