Google Code Jam Google String problem: a sequence resulting from bit flips and reversals
Instead of trying to actually calculate Sgoogol, let's try to figure out some properties of the general case Sn and see if that can help. 

\$S_n\$ has an odd number of digits

It is obviously of the form \$2k+1\$

\$S_n\$ has length \$2^n - 1\$

This is easily proved with recursion

\$S_n[\frac{2^n}{2} + 1] = S_n[2^{n-1} + 1] = 0\$

From the definition. I'm assuming 0-based indexing. 

If \$k &gt; 2^{n-1} + 1\$, then \$S_n[k] = switch(S_n[(2^n - 1) - 1 - k])\$

From the definition. This allows us to convert between halves of the string.

This suggests a simpler algorithm.

def find_value(index, n):
    if n == 2:
        return [True, True, False][index] 
    if k == 2 ** (n-1) + 1:
        return True
    if k &gt; 2 ** (n-1) + 1:
        return not find_value((2^n - 1) - 1 - k, n-1)
    return find_value(k, n-1)


And you can convert to 0 or 1 afterwards. (This may blow the stack, so you may have to rewrite iteratively)