Is there a simpler way to sum the first $n$ terms of the sequence of numbers starting at 2 and squaring to get the next?

64 Views Asked by At

I've got this summation:

$$ f(n)=\sum_{i=0}^{n-1}2^{2^i} $$

In effect, it's the sum of the sequence of numbers you get from starting at 2 and squaring the previous number in the sequence:

$$ \begin{aligned} a(0) &= 2 \\ a(n) &= a(n-1)^2 \\ \end{aligned} $$

(It's this sequence in OEIS I'm summing, or the $n$th term of this sequence I'm searching for, for context.)

Obviously, if it were just summing the powers of two, I could get rid of the summation pretty easily:

$$ f(n)=\sum_{i=0}^{n-1}2^i \\ f(n)=\frac{1-2^n}{1-2} \\ f(n)=-(1-2^n) \\ f(n)=2^n - 1 \\ $$

This is supposed to be for computing optimization, so most elementary operations are generally pretty fast. I just want to get rid of that giant sigma and be able to just do it in terms of elementary arithmetic and preferably without exponentiation with a base of anything other than a power of 2.

# My goal is to avoid this kind of code
def f(n):
    sum = 0
    for i in range(0, n - 1):
        sum += 2 ** (2 ** i)
    return sum