|
%I #41 Jan 13 2024 04:55:27
%S 0,1,1,0,1,1,0,0,1,0,0,1,0,0,1,1,0,1,1,0,0,1,0,0,1,0,0,1,1,0,1,1,0,1,
%T 1,0,0,1,0,0,1,1,0,1,1,0,1,1,0,0,1,0,0,1,1,0,1,1,0,1,1,0,0,1,0,0,1,0,
%U 0,1,1,0,1,1,0,0,1,0,0,1,0,0,1,1,0,1,1,0,1,1,0,0,1,0,0,1,1,0,1,1,0,1,1,0,0
%N Sequence of the diagonal variant of the Fibonacci word fractal. Sequence of the Fibonacci tile.
%C The upper Wythoff sequence (A001950) mod 2 (see formula section). - _Michel Dekking_, Feb 01 2021
%C 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).
%C From _Michel Dekking_, May 03 2018: (Start)
%C 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
%C 0->10221, 1->1022, 2->1021,
%C 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
%C 1->322, 2->321, 3->3223221,
%C which has the property that the letter to letter projection
%C 1->0, 2->1, 3->0
%C of its fixed point 3,2,2,3,2,2,1,3,2,1,... is equal to (a(n)).
%C (End)
%H A. Blondin-Massé, S. Brlek, A. Garon, S. Labbé, <a href="https://doi.org/10.1007/978-3-642-04397-0_7">Christoffel and Fibonacci Tiles</a>, DGCI 2009. Lecture Notes in Computer Science, vol 5810.
%H A. Blondin-Massé, S. Brlek, A. Garon, S. Labbé, <a href="http://www.slabbe.org/Publications/2009-dgci.pdf">Christoffel and Fibonacci tiles</a>, Sept 2009.
%H A. Blondin-Massé, S. Brlek, A. Garon, S. Labbé, <a href="http://www.slabbe.org/Communications/2009-dgci-slides.pdf">Christoffel and Fibonacci tiles presentation</a>, Sept 2009.
%H A. Monnerot-Dumaine, <a href="http://hal.archives-ouvertes.fr/hal-00367972/">The Fibonacci word fractal</a>, Feb 2009.
%F 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.
%F The recursion is given by
%F q[n]=q[n-1]q[n-2] if n=2 mod 3, and
%F q[n]=q[n-1]bar{q[n-2]} if n=0 or 1 mod 3,
%F where bar exchanges 0 and 1.
%F Also application of the mapping 1->0, 2->1, 0->empty word to the Dense Fibonacci word A143667.
%F Conjecture: A171587=(A001950 mod 2), as suggested for n=1,2,...,500 by Mathematica program below. - _Clark Kimberling_, May 31 2011
%F From _Michel Dekking_, May 03 2018: (Start)
%F Proof of Kimberling's 2011 conjecture, i.e., this sequence is the parity sequence of the Upper Wythoff sequence A001950.
%F 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
%F beta: 2 -> 3, 3 -> 32 (cf. A282162).
%F We define the first difference operator D on finite words w by
%F D(w(1)...w(m)) = (w(2)-w(1))...(w(m)-w(m-1)).
%F Note that the length of D(w) is one less than the length of w, and note
%F 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.
%F We also need (easily proved by induction)
%F LEMMA 2: The last letter of the word q[n] equals 0 if and only if n = 0,1,2 modulo 6.
%F Almost trivial is
%F LEMMA 3: The last letter e(n) of beta^n(2) equals 2 if and only if n = 0 modulo 2.
%F The following proposition implies the conjecture.
%F PROPOSITION: The difference sequence of q[n] satisfies D(q[n]) = beta^{n-1}(2) e(n-1)^{-1} modulo 2 for n>3.
%F Note that, by definition, beta^n(2) e(n)^{-1} is just the word beta^n(2), with the last letter removed.
%F 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:
%F n modulo 6 | 0 | 1 | 2 | 3 | 4 | 5 |
%F last letter of q[n-1] | 1 | 0 | 0 | 0 | 1 | 1 |
%F first letter of q[n-2]* | 1 | 1 | 0 | 1 | 1 | 0 |
%F 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)).
%F For example, where all equalities are modulo 2,
%F 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),
%F where f(n):=(e(n) mod 2)^{-1}.
%F (End)
%e q[2] = q[1]q[0] = 0, q[3] = q[2]bar{q[1]} = 01,
%e q[4] = q[3]bar{q[2]} = 011, q[5] = q[4]q[3] = 01101.
%t (* This program supports the conjecture that A171587=(A001950 mod 2). *)
%t t = Nest[Flatten[# /. {1 -> {1, 0, 2, 2}, 0 -> {1, 0, 2, 2, 1}, 2 -> {1, 0, 2, 1}}] &, {1}, 5]
%t w = DeleteCases[t, 0] /. {1 -> 0, 2 -> 1}
%t u = Table[n + Floor[n*GoldenRatio], {n, 1, 500}]; v = Mod[u, 2]
%t Table[w[[n]] - v[[n]], {n, 1, 500}] (* supports conjecture for n=1,2,...,500 *)
%t (* t=A143667, w=A171587, u=A001950, conjecture: v=w *)
%Y Cf. A143667, A003849;
%Y Cf. A001950 (upper Wythoff sequence), A085002 (lower Wythoff sequence mod 2), A085002.
%K nonn
%O 0,1
%A Alexis Monnerot-Dumaine (alexis.monnerotdumaine(AT)gmail.com), Dec 12 2009
%E Formula corrected and extended by _Michel Dekking_, May 03 2018
|
