-1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Does the symbol + means addition or array concatenation? $\endgroup$ – Nicky C Dec 18 '15 at 10:16
  • $\begingroup$ I meant simply adding to end of array $\endgroup$ – Puupuls Dec 18 '15 at 10:20
  • $\begingroup$ do you mean digits rather than numbers ? $\endgroup$ – Abr001am Dec 18 '15 at 11:12
  • $\begingroup$ Yes sorry digits - Edited question $\endgroup$ – Puupuls Dec 18 '15 at 11:22
  • $\begingroup$ By binary array do you mean that the base type of the array is actually just a bit? Or is an int or bool or char? $\endgroup$ – G-man Dec 18 '15 at 11:29
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$
  • 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


$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Problem is that i need to be able to generate it automatic using programming so I need algorithm for it. $\endgroup$ – Puupuls Dec 18 '15 at 10:38
  • $\begingroup$ @Puupuls Ok, I answered a little cryptically, since I thought this was school work. The 0s and 1s complete each others, so each of the numbers are just 1s in binary: 11, 1111, 11111111,... The length of the n:th number is $2^n$, so it's value is $2^{n+1} -1$. So the first numbers in decimal would be $2^2 -1 = 3$, $2^3 -1 = 7$, $2^4 -1 = 15$ etc. EDIT: I just understood that by + you may need concatenation instead of actual adding. In this case, you could use bitshift operations and maybe utilize the 1's complement: en.wikipedia.org/wiki/Ones'_complement $\endgroup$ – user3010768 Dec 18 '15 at 12:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.