# 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?

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

• I doubt there's a closed formula at all, much less one that's faster to compute than the code you included. – Greg Martin May 27 '19 at 7:11
• The first element is $2$, not $1$. Without the typo, it is sequence A001146 in OEIS. – TonyK May 27 '19 at 7:25
• $f(n)$ has a pretty regular form in binary. It's not a closed form, but bitwise arithmetic (e.g. bitshift) might be somewhat fast. – user326210 May 27 '19 at 7:33
• @TonyK Thanks! Updated. – Isiah Meadows May 27 '19 at 7:35
• @IsiahMeadows the loop will not be a issue, the size of the number will be. Let's say $n = 10$, you are only summing 10 numbers but the last number has over $150$ digits When $n = 20$, you are only summing 20 numbers but the last number has over $1.5\times 10^5$ digits.... – achille hui May 27 '19 at 8:47