Getting a specific element of a non-recursive sequence

Question

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.

Answer 1

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$...