Getting a specific element of a non-recursive sequence I have a sequence, starting with $1$. You store the current sequence as a list, then duplicate it. In this copy, you invert it, turning $1$s into $0$s, and $0$s into $1$s. Then, you join it on to the first sequence.* So it goes:
$$1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1...$$
Using this, how do you get a function taking the input $n$, and outputting the $n$-th element of this sequence, without calculating every element up to that one?
I've used the recursive program for generating a square grid of these, as white and black squares, but want to use my line-based fractal generator instead. But for my purposes, I need a function that can calculate any element without knowing the ones before it.
*The function actually scans through the existing list, adding elements, to be more efficient, but this explanation's more intuitive.
 A: As mentioned in comments, this is inverted Thue–Morse sequence, see also https://oeis.org/A010060. There is a formula already mentioned in this question:  A nice formula for the Thue–Morse sequence, which after slight modification yields (to match the inverted version)
$$
t_n = \left(1+n-\sum_{k=1}^{n}(-1)^{\binom{n}{k}}\right) \bmod 3.
$$ 
However this formula requires $O(n)$ calculations (not including calculation of binomial coefficients, although that is only required $\bmod 2$). So you might consider using modified version of recursive formula instead (mentioned also in the wiki pages), which really relies only on one previous sequence element, specifically
\begin{align}t_0&=1\\ t_{2n}&=t_{n}\\ t_{2n+1}&=1-t_n.\end{align}
This way you can compute the $t_n$ in $O(\ln n)$ steps. It is also quite simple to implement this recurrence without using recursive functions, since per your profile you are getting into Python, here is a Python 3 code snippet:
def t(n):
    r = 1
    while n > 0:
        if n & 1 == 1:
            r ^= 1
        n >>= 1
    return r

(try https://trinket.io/python/9ffdde598d). It is clear that $t_n$ is really just parity of number of $1$s in a binary representation of $n$...
