cp's OEIS Frontend

A171587 Sequence of the diagonal variant of the Fibonacci word fractal. Sequence of the Fibonacci tile.

%I A171587 #70 Dec 27 2024 02:57:14
%S A171587 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 A171587 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 A171587 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 A171587 Sequence of the diagonal variant of the Fibonacci word fractal. Sequence of the Fibonacci tile.
%C A171587 This is the upper Wythoff sequence (A001950) read mod 2 (for proof see formula section). So a(n) = floor((n+1)*phi^2) mod 2 where phi = (1+sqrt(5))/2. - _Michel Dekking_, Feb 01 2021
%C A171587 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 A171587 From _Michel Dekking_, May 03 2018: (Start)
%C A171587 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 A171587     0->10221, 1->1022, 2->1021,
%C A171587 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 A171587     1->322, 2->321, 3->3223221,
%C A171587 which has the property that the letter to letter projection
%C A171587     1->0, 2->1, 3->0
%C A171587 of its fixed point 3,2,2,3,2,2,1,3,2,1,... is equal to (a(n)).
%C A171587 (End)
%C A171587 Also Hofstadter G-sequence (A005206) mod 2. Another morphism can be written in octonary notation as: 0->4, 1->7, 2->5, 3->6, 4->60, 5->53, 6->71, 7->42, where the high bit gives A005614 and the low bit (i.e. "mod 2") gives this A171587 for n>0. The "Missing Words Proof Certificate" found under Links uses this representation to compute missing words of length L = 3, 4, 6, 9, 14, 22. Is there another missing word of length L = 35 as A001611 suggests? - _Bradley Klee_, Dec 24 2024
%H A171587 N. J. A. Sloane, <a href="/A171587/b171587.txt">Table of n, a(n) for n = 0..10000</a>
%H A171587 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 A171587 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 A171587 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 A171587 Bradley Klee, <a href="/A171587/a171587.go.txt">Missing Words Proof Certificate (Golang)</a>
%H A171587 Bradley Klee, <a href="/A171587/a171587_1.go.txt">Turns Equivalence Proof Certificate (Golang)</a>
%H A171587 Bradley Klee, <a href="/A171587/a171587.png">Drawing of Fibonacci word fractal</a>
%H A171587 Alexis Monnerot-Dumaine, <a href="http://hal.archives-ouvertes.fr/hal-00367972/">The Fibonacci word fractal</a>, Feb 2009.
%H A171587 Alexis Monnerot-Dumaine, <a href="/A171587/a171587.pdf">The Fibonacci word fractal</a> [Cached copy, with permission]
%F A171587 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 A171587 The recursion is given by
%F A171587     q[n]=q[n-1]q[n-2] if n=2 mod 3, and
%F A171587     q[n]=q[n-1]bar{q[n-2]} if n=0 or 1 mod 3,
%F A171587 where bar exchanges 0 and 1.
%F A171587 Also application of the mapping 1->0, 2->1, 0->empty word to the Dense Fibonacci word A143667.
%F A171587 Conjecture: A171587=(A001950 mod 2), as suggested for n=1,2,...,500 by Mathematica program below. - _Clark Kimberling_, May 31 2011
%F A171587 From _Michel Dekking_, May 03 2018: (Start)
%F A171587 Proof of Kimberling's 2011 conjecture, i.e., this sequence is the parity sequence of the Upper Wythoff sequence A001950.
%F A171587 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 A171587   beta:  2 -> 3, 3 -> 32 (cf. A282162).
%F A171587 We define the first difference operator D on finite words w by
%F A171587     D(w(1)...w(m)) = (w(2)-w(1))...(w(m)-w(m-1)).
%F A171587 Note that the length of D(w) is one less than the length of w, and note
%F A171587 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 A171587 We also need (easily proved by induction)
%F A171587 LEMMA 2: The last letter of the word q[n] equals 0 if and only if n = 0,1,2 modulo 6.
%F A171587 Almost trivial is
%F A171587 LEMMA 3: The last letter e(n) of beta^n(2) equals 2 if and only if n = 0 modulo 2.
%F A171587 The following proposition implies the conjecture.
%F A171587 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 A171587 Note that, by definition, beta^n(2) e(n)^{-1} is just the word beta^n(2), with the last letter removed.
%F A171587 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 A171587 n modulo 6               | 0 | 1 | 2 | 3 | 4 | 5 |
%F A171587 last letter of q[n-1]    | 1 | 0 | 0 | 0 | 1 | 1 |
%F A171587 first letter of q[n-2]*  | 1 | 1 | 0 | 1 | 1 | 0 |
%F A171587 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 A171587 For example, where all equalities are modulo 2,
%F A171587     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 A171587 where f(n):=(e(n) mod 2)^{-1}.
%F A171587 (End)
%e A171587 q[2] = q[1]q[0] = 0,        q[3] = q[2]bar{q[1]} = 01,
%e A171587 q[4] = q[3]bar{q[2]} = 011, q[5] = q[4]q[3] = 01101.
%t A171587 (* This program supports the conjecture that A171587=(A001950 mod 2). *)
%t A171587 t = Nest[Flatten[# /. {1 -> {1, 0, 2, 2}, 0 -> {1, 0, 2, 2, 1}, 2 -> {1, 0, 2, 1}}] &, {1}, 5]
%t A171587 w = DeleteCases[t, 0] /. {1 -> 0, 2 -> 1}
%t A171587 u = Table[n + Floor[n*GoldenRatio], {n, 1, 500}]; v = Mod[u, 2]
%t A171587 Table[w[[n]] - v[[n]], {n, 1, 500}] (* supports conjecture for n=1,2,...,500 *)
%t A171587 (* t=A143667, w=A171587, u=A001950, conjecture: v=w *)
%o A171587 (Go)
%o A171587 func b(n int) []int {
%o A171587     a := make([]int, n+1);
%o A171587     for i:=1; i < n+1; i++ {
%o A171587         a[i] = i-a[a[i-1]];
%o A171587     };
%o A171587     for i:=0; i < n+1; i++ {
%o A171587         a[i] %= 2;
%o A171587     };
%o A171587     return a
%o A171587 } // _Bradley Klee_, Dec 25 2024
%Y A171587 Cf. A143667, A003849. Cf. A379184, A379274, A379275.
%Y A171587 Cf. A001950 (upper Wythoff sequence), A085002 (lower Wythoff sequence mod 2).
%K A171587 nonn
%O A171587 0,1
%A A171587 _Alexis Monnerot-Dumaine_, Dec 12 2009
%E A171587 Formula corrected and extended by _Michel Dekking_, May 03 2018