OFFSET
0,1
COMMENTS
The upper Wythoff sequence (A001950) mod 2 (see formula section). - Michel Dekking, Feb 01 2021
Interpreted as 0=turn right and 1=turn left, this sequence builds the diagonal variant of the Fibonacci word fractal. Base for the construction of the Fibonacci tile (Tiles the plane by translation in 2 ways).
From Michel Dekking, May 03 2018: (Start)
This is a morphic sequence, i.e., the letter to letter projection of a fixed point of a morphism. To see this, one uses the formula which generates (a(n)) from the Dense Fibonacci word A143667. Note that in the Dense Fibonacci word, which is the fixed point of the morphism
0->10221, 1->1022, 2->1021,
the letter 0 exclusively occurs preceded directly by the letter 1. This enables one to create a new letter 3, encoding the word 10, and a morphism
1->322, 2->321, 3->3223221,
which has the property that the letter to letter projection
1->0, 2->1, 3->0
of its fixed point 3,2,2,3,2,2,1,3,2,1,... is equal to (a(n)).
(End)
LINKS
A. Blondin-Massé, S. Brlek, A. Garon, S. Labbé, Christoffel and Fibonacci Tiles, DGCI 2009. Lecture Notes in Computer Science, vol 5810.
A. Blondin-Massé, S. Brlek, A. Garon, S. Labbé, Christoffel and Fibonacci tiles, Sept 2009.
A. Blondin-Massé, S. Brlek, A. Garon, S. Labbé, Christoffel and Fibonacci tiles presentation, Sept 2009.
A. Monnerot-Dumaine, The Fibonacci word fractal, Feb 2009.
FORMULA
This sequence is defined by Blondin-Massé et al. as a limit of recursively defined words q[n]. Here q[0] is the empty word, and q[1]=0.
The recursion is given by
q[n]=q[n-1]q[n-2] if n=2 mod 3, and
q[n]=q[n-1]bar{q[n-2]} if n=0 or 1 mod 3,
where bar exchanges 0 and 1.
Also application of the mapping 1->0, 2->1, 0->empty word to the Dense Fibonacci word A143667.
Conjecture: A171587=(A001950 mod 2), as suggested for n=1,2,...,500 by Mathematica program below. - Clark Kimberling, May 31 2011
From Michel Dekking, May 03 2018: (Start)
Proof of Kimberling's 2011 conjecture, i.e., this sequence is the parity sequence of the Upper Wythoff sequence A001950.
The first difference sequence 3, 2, 3, 3, 2, 3, 2, 3, ... of the Upper Wythoff sequence is equal to the unique fixed point of the morphism
beta: 2 -> 3, 3 -> 32 (cf. A282162).
We define the first difference operator D on finite words w by
D(w(1)...w(m)) = (w(2)-w(1))...(w(m)-w(m-1)).
Note that the length of D(w) is one less than the length of w, and note
LEMMA 1: D(vw) = D(v)|w(1)-v(l)|D(w), if v = v(1)...v(l), and w = w(1)...w(m). Here |w(1)-v(l)| is modulo 2.
We also need (easily proved by induction)
LEMMA 2: The last letter of the word q[n] equals 0 if and only if n = 0,1,2 modulo 6.
Almost trivial is
LEMMA 3: The last letter e(n) of beta^n(2) equals 2 if and only if n = 0 modulo 2.
The following proposition implies the conjecture.
PROPOSITION: The difference sequence of q[n] satisfies D(q[n]) = beta^{n-1}(2) e(n-1)^{-1} modulo 2 for n>3.
Note that, by definition, beta^n(2) e(n)^{-1} is just the word beta^n(2), with the last letter removed.
PROOF: By induction. Combine Lemma 1, 2 and 3 in the recursion for the q[n], for n = 0,...,5 modulo 6, using the following table:
n modulo 6 | 0 | 1 | 2 | 3 | 4 | 5 |
last letter of q[n-1] | 1 | 0 | 0 | 0 | 1 | 1 |
first letter of q[n-2]* | 1 | 1 | 0 | 1 | 1 | 0 |
Here q[n-2]* denotes either q[n-2] (if n == 2 (mod 3)), or bar{q[n-2]} (if n == 0,1 (mod 3)).
For example, where all equalities are modulo 2,
D(q[8]) = D(q[7]) 0 D(q[6]) = beta^6(2) f(6) 0 beta^5(2) f(5) = beta^6(2) beta^5(2) f(5) = beta^5(32) f(5) = beta^7(2) f(7),
where f(n):=(e(n) mod 2)^{-1}.
(End)
EXAMPLE
q[2] = q[1]q[0] = 0, q[3] = q[2]bar{q[1]} = 01,
q[4] = q[3]bar{q[2]} = 011, q[5] = q[4]q[3] = 01101.
MATHEMATICA
t = Nest[Flatten[# /. {1 -> {1, 0, 2, 2}, 0 -> {1, 0, 2, 2, 1}, 2 -> {1, 0, 2, 1}}] &, {1}, 5]
w = DeleteCases[t, 0] /. {1 -> 0, 2 -> 1}
u = Table[n + Floor[n*GoldenRatio], {n, 1, 500}]; v = Mod[u, 2]
Table[w[[n]] - v[[n]], {n, 1, 500}] (* supports conjecture for n=1, 2, ..., 500 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Alexis Monnerot-Dumaine (alexis.monnerotdumaine(AT)gmail.com), Dec 12 2009
EXTENSIONS
Formula corrected and extended by Michel Dekking, May 03 2018
STATUS
approved