# Can the elements of this recursive sequence be calculated individually?

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.

• The first number is always zero, the second one is a power of $2$, the third one if one lesser power of $2$, then you get six-folds of powers of $2$, ... what did you find out? Commented Jul 18 at 14:47
• @Dominique I'm sorry, I'm not sure if i understood your comment. You think the pattern has more complex relationship and it cannot be simply calculated for individual elements of the sequence? Commented Jul 18 at 15:19
• He is looking at the data you have displayed and trying to find patterns. Which is what you can be doing too. Commented Jul 19 at 21:18
• Ahh... I really misunderstood what he meant. I considered my findings irrelevant. At one point I came up with a formula that worked for at most 8 elements of the sequence, but then it fell apart. I was mostly looking at smaller pieces of the sequence from which I could later derive a formula for the whole sequence, but I had no luck. Commented Jul 20 at 12:18

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

• The description is definitely more useful than the formula itself. I am very grateful for the write-up and solving my problem. Commented Jul 20 at 12:15

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]

• The sequence I am looking for is indeed OEIS A030109. I completely forgot about the online encyclopedia of integer sequences. I should have checked there before I asked here. In any case, many thanks. Commented Jul 20 at 12:16