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

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, 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, 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

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

Table of n, a(n) for n=0..104.

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

(* This program supports the conjecture that A171587=(A001950 mod 2). *)
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 *)
(* t=A143667, w=A171587, u=A001950, conjecture: v=w *)

Crossrefs

Cf. A143667, A003849;

Cf. A001950 (upper Wythoff sequence), A085002 (lower Wythoff sequence mod 2), A085002.

Sequence in context: A080886 A217207 A083924 * A284627 A322829 A286400

Adjacent sequences: A171584 A171585 A171586 * A171588 A171589 A171590

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