2
$\begingroup$

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
$\endgroup$
  • $\begingroup$ I doubt there's a closed formula at all, much less one that's faster to compute than the code you included. $\endgroup$ – Greg Martin May 27 '19 at 7:11
  • $\begingroup$ The first element is $2$, not $1$. Without the typo, it is sequence A001146 in OEIS. $\endgroup$ – TonyK May 27 '19 at 7:25
  • $\begingroup$ $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. $\endgroup$ – user326210 May 27 '19 at 7:33
  • $\begingroup$ @TonyK Thanks! Updated. $\endgroup$ – Isiah Meadows May 27 '19 at 7:35
  • 1
    $\begingroup$ @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.... $\endgroup$ – achille hui May 27 '19 at 8:47

Your Answer

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

Browse other questions tagged or ask your own question.