I have a sequence with a very predictable pattern. It goes like this:
$$2,1,4,2,1,1,8,2,1,4,2,1,1,1,16,2,1,4,2,1,1,8,2,1,4,2,1,1,1,1,32,2,1,4,2,1,1,8,2,1,4,2,1,1,1,16,2,1,4,2,1,1,8,2,1,4,2,1,1,1,1,1,64, 2, 1, 4, 2, 1, 1, 8, 2, 1, 4, 2, 1,1 ,1 , 16, 2, 1, 4, 2, 1, 1, 8 \dots$$
Every term is some power of $2$, and $2^n$ will show up for the first time at the $\left(2^n-1\right)^\text{th}$ term in the sequence, and it will be preceded by $n-1$ ones.
I can write more terms, for as far as I wanted to. The problem is, I want to be able to know something like $4000^\text{th}$ term, without having to write the sequence all the way up to $4000$. How do I go from the known pattern to the closed formula for the $n^\text{th}$ term? Or maybe recurrence formula?
I don't know how to go from the pattern to a formula. Thanks for help.
Note that the terms preceding $16$, for example, are always the same. There are $14$ of them. The pattern starts after any higher power of $2$. You should be able to justify that this is true for any given power of $2$. You can approach any given term by successive powers of $2$. Taking term $4000$ for example, the $2047^{th}$ term is $4096$. The $4000^{th}$ term will be the same as the $4000-2047=1953^{rd}$ The next power below $1953$ is $2048$, which occurs in the $1023^{rd}$ term. Term $1953$ is the same as term $1953-1023=930$. Keep going. This gives a recursive algorithm. Given a term number $n$ it will take about $\log_2(n)$ steps