Power towers solution

A long, long time ago I have mentioned an ICPC practice session problem: given two power towers, which one evaluates to a larger value? A power tower is an expression like 2²³², which is evaluated right-to-left like 2^(2^(3^2)). Each number in both power towers is an integer between 1 and 100, and the height of the tower is also between 1 and 100.

I have also mentioned that we have came up with a working approach together with Roman Elizarov and Evgeny Kapun, but never got around to actually describing this approach. For some reason, quite a few people asked me to come back to this problem recently, so here we are :)

First, we can notice that we can remove any one and everything that comes after it, so let's concentrate on the case where all numbers are between 2 and 100.

Let's compare our power towers from top to bottom, aligning them in such a way that the bottom numbers are next to each other. In other words, we will follow this process: we start either with two ones, or with a one and some power tower, then we repeatedly add a number (between 2 and 100) to the bottom of each of the towers.

The first observation is that there exists such number k that if the first tower is at least k times bigger, it will keep being at least k times bigger even if we add 2 to it and 100 to the other tower. Effectively it means that as soon as one of the towers is at least k times bigger in our top-down process, we can skip going through the remaining numbers and declare that tower as the winner.

To prove it, let's write down some formulas. We have x>=k*y, and we need to prove that 2^x>=k*100^y. But 2^x>=2^k*y=100^y*(2^k/100)^y. Since y>=1, we just need 2^k/100>=k, which is true for k=10 for example.

Intuitively it seems that most likely one of the towers will become at least 10 times bigger pretty quickly, and we won't need to go very deep. In order to check if this is the case, let's define an expand operation: given a set of numbers S, the set expand(S) is built in the following way: first, we build a set T which is obtained by uniting S with all numbers obtained by adding one more power at the bottom: T=S+{2^x for x in S}+{3^x for x in S}+...+{100^x for x in S}. Then, we sort all numbers in T, collapse equal numbers into one, and then remove all numbers which are at least 10 times bigger than the previous number, and at least 10 times smaller than the next number. The resulting set is called expand(S). The motivation behind such definition is: if we have two numbers that are in S during our power tower comparison process, then after adding two more powers to the bottom we will either get a decision (one is at least 10 times bigger than the other), two equal numbers, or two numbers from expand(S).

Now let's start with the set S={1,2,..,100}, and repeatedly compute expand(S), expand(expand(S)), .... It turns out that the process stops very quickly, and already expand(expand(S))=expand(expand(expand(S))), and this set has just 17709 elements!

It means that if we compare two power towers from top to bottom, then we only need to handle the numbers from expand(expand(S)). If at some point one number is 10 times bigger than the other, we k now the result of the comparison. If at some point the numbers are equal, and are at least 300, then we just need to look at the next differing number going from top to bottom, since (100/99)³⁰⁰>10.

Now, how do we actually work with the numbers from expand(expand(S)), for example how do we actually find out that it stops growing at 17709 elements? The numbers in that set are still huge. The only way I see to approach this is to experiment, trying out different ideas until one works. In this case, two ideas were necessary:

First, we will store the logarithms of elements of our set instead of the elements themselves. It turns out that their logarithms all fit in the double floating-point type (the largest is about 3 million). However, during the expansion step we need to temporarily work with numbers as high as 100^x for x from our set, and those don't fit into double.

Therefore, when expanding the set, we will work with logarithms of logarithms of numbers. For example, if we have y=log(x), then we will compare numbers of form log(log(b^x))=log(x*log(b))=log(x)+log(log(b))=y+log(log(b)).

We need to be able to check two things: whether two numbers of this form are equal, and whether one is at least 10 times bigger than the other. For the equality test, we will simply check if the difference is smaller than some constant eps. When running the expansion process, we can print out the biggest difference smaller than eps, and the smallest difference bigger than eps that we encounter. For eps=1e-13, the former is 3e-15, and the latter is 4e-13. Given the more than 100 times difference between the two, it seems plausible that the former is just floating-point rounding error and the two numbers are equal, and the latter is real difference. This is not a proof, of course, but it gives enough confidence (I suspect this leap of faith could be the main reason this problem was only used for ICPC practice session, and not for the real contest).

Now we need to check if x/y>=10 when we know p=log(log(x)) and q=log(log(y)). x/y>=10 is the same as log(x)-log(y)>=log(10), which is the same as exp(p)-exp(q)>=log(10), which is the same as (exp(p-q)-1)*exp(q)>=log(10), which is the same as log(exp(p-q)-1)+q>=log(log(10)). To avoid overflow when computing exp(p-q) in this formula, we will simply check if p-q>=5 first, since in that case the inequality is definitely true.

Here is the code that we used to come up with and verify all above hypotheses:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class PowerChains {
   static final int MAXN = 100;
    
    static class Number implements Comparable {
        double what;
        int[] origin;
        
        public Number(Number parent, double value, int extra) {
            if (extra < 0) {
                origin = parent.origin;
                what = value;
                return;
            }
            if (parent != null) {
                origin = new int[parent.origin.length + 1];
                System.arraycopy(parent.origin, 0, origin, 1, parent.origin.length);
            } else {
                origin = new int[1];
            }
            origin[0] = extra;
            what = value;
        }

        public int compareTo(Number number) {
            return Double.compare(what, number.what);
        }
        
        public String toString() {
            StringBuilder b = new StringBuilder();
            b.append(what);
            for (int x : origin) b.append(" " + x);
            return b.toString();
        }
    }

   public static void main(String[] args) {
      Number[] interesting = new Number[MAXN];
      for (int i = 0; i < MAXN; ++i) {
         interesting[i] = new Number(null, Math.log(i + 1), i + 1);
      }
      while (true) {
         Number[] pows = new Number[MAXN * interesting.length];
         for (int i = 1; i < interesting.length; ++i) {
            pows[i] = new Number(interesting[i], Math.log(interesting[i].what), -1);
         }
         pows[0] = pows[1];
         for (int b = 2; b <= MAXN; ++b) {
            double logb = Math.log(Math.log(b));
            for (int i = 0; i < interesting.length; ++i) {
               pows[(b - 1) * interesting.length + i] =
                     new Number(interesting[i], interesting[i].what + logb, b);
            }
         }
         Arrays.sort(pows);
         double maxDiff = 0.0;
         double minDiff = 1e100;
         double maxBase = 0.0;
         double needDiff = Math.log(10);
         List newInteresting = new ArrayList();
         newInteresting.add(new Number(null, 0.0, 1));
         boolean wasBig = true;
         for (int i = 0; i + 1 < pows.length; ++i) {
            double diff = (pows[i + 1].what - pows[i].what) / (pows[i + 1].what);
            if (Math.abs(diff) < 1e-13) {
                    if (diff > maxDiff) {
                        maxDiff = diff;
                    }
            } else {
                    if (diff < minDiff) {
                        minDiff = diff;
                    }
               double a = pows[i].what;
               double b = pows[i + 1].what;
               boolean big;
               if (b - a > 5)
                  big = true;
               else {
                  double by = Math.exp(b - a) - 1;
                  big = a + Math.log(by) > Math.log(needDiff);
               }
               if (!big) {
                  if (wasBig)
                     newInteresting.add(new Number(pows[i], Math.exp(pows[i].what), -1));
                  newInteresting.add(new Number(pows[i + 1], Math.exp(pows[i + 1].what), -1));
                  maxBase = Math.max(maxBase, pows[i + 1].what);
                  wasBig = false;
               } else {
                  wasBig = true;
               }
            }
         }
         System.out.println(newInteresting.size() + " " + maxDiff + " " + Math.exp(maxBase) + " " + minDiff);
         if (newInteresting.size() == interesting.length) break;
         interesting = new Number[newInteresting.size()];
         for (int i = 0; i < interesting.length; ++i) {
            interesting[i] = newInteresting.get(i);
         }
      }
   }
}

Thanks for reading, and check back for more!