Can the elements of this recursive sequence be calculated individually?

Question

Is there a way to calculate each element of these sequences individually without having to calculate the previous element or sequence?

Sequence 1: [2]
Sequence 2: [4,  2,  6]
Sequence 3: [8,  4,  12, 2, 10,  6, 14]
Sequence 4: [16, 8,  24, 4, 20, 12, 28, 2, 18, 10, 26,  6, 22, 14, 30]
Sequence 5: [32, 16, 48, 8, 40, 24, 56, 4, 36, 20, 52, 12, 44, 28, 60, 2, 34, 18, 50, 10, 42, 26, 58, 6, 38, 22, 54, 14, 46, 30, 62]
etc.

I know how to generate them recursively, as the first half of the next sequence is just prev_sequence[i] * 2 and the second half is prev_sequence[i] * 2 + 2 (when you prefix 0 to the sequence).

There seems to be an internal pattern. Looking at e.g. the sequence 3, it starts with 8, the next two numbers are 8-4 = 4 and 8+4 = 12. The next four numbers are the last two interleaved, where the first half is number-2 and the second half is number+2. The sequence 4 starts the internal pattern with -8 and +8 then continues to half if for the next "levels".

I feel that this is more of a math question than a programming one, hence the question is here. I'm sorry for not phrasing my question in a more mathematical way.

Thanks to everyone in advance.

Answer 1

All numbers in these sequences are even, so let's divide them by $2$. Here's how you get $\frac12\cdot$ sequence $k$: List the numbers $1,\ldots,2^k-1$ in binary as a $k$-digit number (with leading zeros) and read them backwards, again as binary numbers. For example, for $k=3$, the first seven natural numbers are $$001,010,011,100,101,110,111.$$ Read backwards, we get $$100_2=4_{10},010_2=2_{10},110_2=6_{10},001_2=1_{10},101_2=5_{10},011_2=3_{10},111_2=7_{10},$$ and if you double those you get exactly your sequence 3.

---

Let $a_{k,n}$ be the $n$-th entry of $\frac12$(sequence $k$). We prove the above claim by induction on $k$. In the following, everything is written in binary, $\overline x$ means the number you get from reversing the digits of $x$, and $x|y$ means concatination of the digits in $x$ and $y$, i.e. $10|11=1011$.

For $0<n<2^k$, we have $$a_{k+1,n}=2a_{k,n}=2\cdot\overline n=\overline n|0=\overline{0|n},$$ as expected. Similarly, $$a_{k+1,2^k+n}=2a_{k,n}+1=\overline n|1=\overline{1|n}.$$ This finishes the induction.

---

This conceptual description is far more useful than any formula, but if you insist on one, here it is: $$a_{k,n}=\sum_{i=0}^{k-1}2^{k-1-i}\left(\left\lfloor\frac n{2^i}\right\rfloor\bmod 2\right)$$ This just relies on the part in parentheses computing the $i$-th bit, and multiplying with the correct power of $2$ to get that bit in the correct position. To get back to your sequences, you of course just have to multiply everything by $2$.

---

Another neat way to formulate this is via convolutions: We have $$a_{k,n}=((\text{the binary digits of $n$ as a string of length }k)\ast(1,2,4,8,\ldots))(k-1).$$

Answer 2

Your sequences may be 'extracted' from the sequence OEIS A030109 :

The trick for the sequence $m$ is to reverse the bits of $2^m-1$ consecutive numbers (subract $1$ and divide by $2$) starting at $2^{m+1}+1$ :

pari/gp script :

g(n)= fromdigits(Vecrev(binary(n)),2)
s(m)=vector(2^m-1,n,(g(2^(m+1)+n)-1)/2)

> s(1)
%3 = [2]
> s(2)
%4 = [4, 2, 6]
> s(3)
%5 = [8, 4, 12, 2, 10, 6, 14]
> s(4)
%6 = [16, 8, 24, 4, 20, 12, 28, 2, 18, 10, 26, 6, 22, 14, 30]