Generating binary array

Question

Programming side (C++)

I have this task where I need to get 5 numbers in binary array, but i cant think of way to generate it. The building process is:

Starts Width 10 then adds same number but 1 and 0 are switched places like this

10

10 + 01

1001 + 0110

10010110 + 01101001

1001011001101001 + 0110100110010110

...

I can't figure out mathematical way to generate it

I need to get digits in positions n, n+1, n+2, n+3, n+4 where n <= 10^9

REMEMBER THIS ISN'T SCHOOL TASK it's task from old Olympiad witch I'm doing to understand tasks concept and learning for next one

Symbol array 1001011001101001... makes so - first is written 1 then last part of array writes at the end of existing one only changing 1 to 0 and 0 to 1 like this 1 → 10 → 1001 → 10010110 → ...

Task: Write programm, that any given integer n in this array finds n, n+1, n+2, n+3 and n+ 4 symbol!

Answer 1

This is the complement of the Thue-Morse sequence. To get the digit in position $n$, express $n-1$ (assuming you count from $1$) in binary and count the number of $1$ bits. If the number of $1$'s is odd, your entry is zero, while if the number of $1$'s is even the entry is $1$.

Answer 2

There's nothing wrong with the method you're using. That is a mathematical way to do it.

If you want to speed it up, notice that the 0s and 1s "complete" each others, so the sums will be 11, 1111, 11111111 etc. in binary.

Answer 3

• scrutinizing positions of '1's :

  $(1,4)$, $4+(2,3)$, $8+(2,3)$, $12+(1,4)$, ...

$$\begin{array} {|r r r|r r r|r} \hline A&1 &2+(2)&B&16+(2)&18+(1)&.. \\ &4+(2) &6+(1)&&20+(1)&22+(2)&.. \\ B&8+(2) &10+(1)&A&24+(1)&26+(2)&.. \\ &12+(1) &14+(2)&&28+(2)&30+(1)&.. \\ \hline \end{array}$$

• When factoring $n$ in guise of $8+8*(\sum_{k=0}{2^k})+\delta$ where $\delta<8+8*(\sum_k{2^k})$

-Getting the variant $k$ to maximum means we are actually at the level of a subcolumn of this table starting by $(8+8*(\sum_k{2^k})+(2),(8+8*(\sum_k{2^k})+2)+(1))$, where $k$ is maximazed and $\delta$ is the offset to look up for.

-To find the offset $\delta$ we should formulate the expression recurrently until $\delta$ is smaller than 16. the expression can be written $U_n=8+8*(\sum_{k}{2^{k}})+U_{n-1}$ and $U_0=\delta<16$, with $k$ maximized.

-Noted that for $U_0$ and $n$ is even the order of the table is (A,B), the column to the right, otherwise, the order is (B,A).

-Developping the recurrent series contuniously, leads to a number between x+(2), (x+2)+(1) or the way round ,x+(1), (x+2)+(2), which means the digit is $0$, in the other hand, where the number matches one of bounds of this interval, it is $1$.

• Developping the sequence ...

$U_n=\begin{cases} 8+8(\sum_{k_0} 2^{k_0})&+ \\ 8+8(\sum_{k_1}2^{k_1})&+ \\ ...\\ \delta \end{cases}=\begin{cases} 8+8(2^{k_0+1}-1)&+ \\ 8+8(2^{k_1+1}-1)&+ \\ ...\\ \delta \end{cases}=8*\begin{cases} {1..0..1...0..}_{binary} \\ \frac{\delta}{8} \end{cases}$

-Dividing $n$ by $8$ gives a real number, the absolute floored integer is formatted in binary then taken the position of the subcolumn regarding the pairwise of '1's in the binary number, thus the order of (A,B). $\delta$ gives the offset.

-examples ...

n=9

floor(n/8)=1, expressed in binary "1", number of '1's is odd means the order is (B,A)

n-8*(floor(n/8))=1, hence the offset is the first element which is not included in the the first row [2 3], means the digit is 0

---

n=16

floor(n/8)=2, n-floor(n/8)=0, the offset cant be nil so we subtract $1$ from the binary value.

floor(n/8)-1=1,expressed in binary "1", number of '1's is odd means the order is (B,A).

n-8*(floor(n/8)-1)=8 is the last element which is included in the the second row [5 8], means the digit is 1

---

n=25

floor(n/8)=3, expressed in binary "11", number of '1's is even means the order is (A,B)

n-8*(floor(n/8))=1, hence the offset is the first element which is included in the the first row [1 4], means the digit is 1

---