# How do I use a known pattern to get a closed formula for a sequence?

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