|
|
A010059
|
|
Another version of the Thue-Morse sequence: let A_k denote the first 2^k terms; then A_0 = 1 and for k >= 0, A_{k+1} = A_k B_k, where B_k is obtained from A_k by interchanging 0's and 1's.
|
|
53
|
|
|
1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,1
|
|
COMMENTS
|
Two conjectures: If n is even, the ratio of 1's to 0's = 1:1.
There are no three adjacent terms of the same parity. (End)
Conjecture (verified for the first 280000 entries): this is the characteristic function of A001969. - R. J. Mathar, Sep 05 2008
Proof of these three conjectures: the first two follow directly from the third, because the sequence A010059 is the binary complement of the Thue-Morse sequence A010060.
For the third conjecture: the odious and evil numbers occur as quadruples EOOE and OEEO, simply by their definition. To obtain the mod 2 version of the interleave of the odious and evil numbers we therefore have to apply a transformation
EOOE -> OEOE, OEEO -> OEOE to these quadruples.
But this changes the parities from the corresponding 4n, 4n+1, 4n+2, 4n+3 quadruples from 0101 to 1001 in the first case, and from 0101 to 0110 in the second case. Since the quadruples EOOE and OEEO occur in a Thue Morse pattern, then also the quadruples 1001 and 0110 occur in a Thue Morse pattern, finishing the proof.
(End)
|
|
REFERENCES
|
W. H. Gottschalk and G. A. Hedlund, Topological Dynamics. American Mathematical Society, Colloquium Publications, Vol. 36, Providence, RI, 1955, p. 105.
M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading, MA, 1983, p. 23.
A. Salomaa, Jewels of Formal Language Theory. Computer Science Press, Rockville, MD, 1981, p. 6.
|
|
LINKS
|
J.-P. Allouche and Jeffrey Shallit, The Ubiquitous Prouhet-Thue-Morse Sequence, in C. Ding. T. Helleseth and H. Niederreiter, eds., Sequences and Their Applications: Proceedings of SETA '98, Springer-Verlag, 1999, pp. 1-16.
|
|
FORMULA
|
G.f.: (1/2) * (1/(1-x) + Product_{k>=0} (1 - x^2^k)). - Ralf Stephan, Jun 20 2003
If A(n)=(a(0),a(2),...,a(2^n-1)), then A(n+1)=(A(n),1-A(n)). - Arie Bos, Jul 27 2022
|
|
EXAMPLE
|
The evolution starting at 1 is:
.1
.1, 0
.1, 0, 0, 1,
.1, 0, 0, 1, 0, 1, 1, 0
.1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1
.1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0
...........
|
|
MAPLE
|
map(t->49-t, convert(StringTools[ThueMorse](1000), bytes)); # Robert Israel, Feb 02 2016
# second Maple program:
a := n -> ifelse(type(add(convert(n, base, 2)), even), 1, 0):
|
|
MATHEMATICA
|
Mod[ CoefficientList[Series[(1 + Sqrt[(1 - 3x)/(1 + x)])/(2(1 + x)), {x, 0, 111}], x], 2] (* Stephan Wolfram *)
CoefficientList[ Series[1/(1 - x) + Product[1 - x^2^k, {k, 0, 10}], {x, 0, 111}]/2, x] (* Robert G. Wilson v, Jul 16 2004 *)
Nest[ Flatten[ # /. {0 -> {0, 1}, 1 -> {1, 0}}] &, {1}, 7] (* Robert G. Wilson v Sep 26 2006 *)
od = Select[ Range[0, 129], OddQ@ DigitCount[ #, 2, 1] &]; ev = Select[ Range[0, 129], EvenQ@ DigitCount[ #, 2, 1] &]; Mod[ Flatten@ Transpose[{od, ev}], 2] (* Robert G. Wilson v, Apr 14 2009 *)
{{1}}~Join~SubstitutionSystem[{0 -> {0, 1}, 1 -> {1, 0}}, {0}, 6] // Flatten (* Michael De Vlieger, Aug 15 2016, Version 10.2 *)
|
|
PROG
|
(R)
maxrow <- 8 # by choice
b01 <- 0
for(m in 0:maxrow) for(k in 0:(2^m-1)){
b01[2^(m+1)+ k] <- b01[2^m+k]
b01[2^(m+1)+2^m+k] <- 1-b01[2^m+k]
}
(b01 <- c(1, b01))
(Python)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|