binary sequence
Jonathan Rowe
The following sequence has been causing some interest (and a few headaches) in
my department. The elements are from the set {0, 1} and the sequence is
infinitely long. The first few elements are:
0 0 1 0 0 1 1 0 0 1 0 0 1 1 0 0 0 1 0 0 1 1 0 0 1 0 0 1 1 0 1 0 0 1 0 0 1 1 0
0 1 0 0 1 1 0 0 0 1 0 0 1 1 0 0 1 0 0 1 1 0 1 0 ....
Any ideas as to the rule behind this sequence?
E-mail any "answers" to j...@uk.ac.exeter.cs
Thanks in advance,
Jon Rowe.
Dan Gordon
>
>The following sequence has been causing some interest (and a few headaches) in
>my department. The elements are from the set {0, 1} and the sequence is
>infinitely long. The first few elements are:
>
>0 0 1 0 0 1 1 0 0 1 0 0 1 1 0 0 0 1 0 0 1 1 0 0 1 0 0 1 1 0 1 0 0 1 0 0 1 1 0
>0 1 0 0 1 1 0 0 0 1 0 0 1 1 0 0 1 0 0 1 1 0 1 0 ....
>
>Any ideas as to the rule behind this sequence?
>
Here's a possible answer. Call the sequence a_1, a_2,...
Start with a_1 = 0.
If you have generated a_1 to a_n, repeat it (i.e., a_n+1 = a_1,...
a_2n = a_n) and then add a_2n+1 = (0 or 1).
The first 0 is repeated, and 1 added. Then 001 is repeated, and 1
added. Then 0010011 is repeated and 0 added, etc. My problem is
that I don't know how the extra 0 or 1 is determined. The most
logical rule for them to follow is that they are simply the complements
of the beginning of the sequence, that is, they should follow the
pattern 1101100... They actually start out that way, but the very last
0 spoils this rule. So either the last 0 is an error, or there's some
other mysterious rule for the extra bits.
weiqi gao
> Jon Rowe.
--------------------------< o >--------------------------
Would it be:
0 0 1 0 0 1 1 0 0 1 0 0 1 1 0
0 0 1 0 0 1 1 0 0 1 0 0 1 1 0 1
0 0 1 0 0 1 1 0 0 1 0 0 1 1 0
0 0 1 0 0 1 1 0 0 1 0 0 1 1 0 1
0 ....
Weiqi Gao
g...@ucrmath.ucr.edu
Lambert Meertens
) >0 0 1 0 0 1 1 0 0 1 0 0 1 1 0 0 0 1 0 0 1 1 0 0 1 0 0 1 1 0 1 0 0 1 0 0 1 1 0
) >0 1 0 0 1 1 0 0 0 1 0 0 1 1 0 0 1 0 0 1 1 0 1 0 ....
) >
) >Any ideas as to the rule behind this sequence?
)
) Here's a possible answer. Call the sequence a_1, a_2,...
)
) Start with a_1 = 0.
)
) If you have generated a_1 to a_n, repeat it (i.e., a_n+1 = a_1,...
) a_2n = a_n) and then add a_2n+1 = (0 or 1).
Another way of describing this is that you have a sequence of sequences,
each obtained from and extending the previous one. If the sequence at some
generation is A, the next is A^A^(0 or 1). Now you can start with A = the
empty sequence.
We have as subsequent generations:
^^0
0^0^1
001^001^1
0010011^0010011^0
001001100100110^001001100100110^1
0010011001001100010011001001101^0010011001001100010011001001101^0
The "spine" formed by the final bits of each next generation starts with
011010. It might be the Thue-Morse sequence 0110100110010110... (think of
the parity of the binary representations of the natural numbers).
Whatever the spine actually is, the limit sequence can be described as
0^01^0^011^0^01^0^0110^0^01^0^011^0^01^0^01101^... =
(take 1 spine)^(take 2 spine)^(take 1 spine)^(take 3 spine)^...
in which the sequence 1 2 1 3 1 2 1 4 ... is another well-known sequence
(the number of 2s dividing 2n).
--
--Lambert Meertens, CWI, Amsterdam; lam...@cwi.nl
Sir Six
Hmm. Also notice that 0 0 1 0 0 1 1 0 0 1 0 0 1 1 0 is:
0 0 1 0 0 1 1
0 0 1 0 0 1 1 0
and that 0 0 1 0 0 1 1 is:
0 0 1
0 0 1 1
and that 0 0 1 is:
0
0 1
for whatever the heck that's worth.