OFFSET
0,1
COMMENTS
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
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)
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
LINKS
N. J. A. Sloane, Table of n, a(n) for n = 0..10000
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.
Bradley Klee, Missing Words Proof Certificate (Golang)
Bradley Klee, Turns Equivalence Proof Certificate (Golang)
Bradley Klee, Drawing of Fibonacci word fractal
Alexis Monnerot-Dumaine, The Fibonacci word fractal, Feb 2009.
Alexis Monnerot-Dumaine, The Fibonacci word fractal [Cached copy, with permission]
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 *)
PROG
(Go)
func b(n int) []int {
a := make([]int, n+1);
for i:=1; i < n+1; i++ {
a[i] = i-a[a[i-1]];
};
for i:=0; i < n+1; i++ {
a[i] %= 2;
};
return a
} // Bradley Klee, Dec 25 2024
CROSSREFS
KEYWORD
nonn
AUTHOR
Alexis Monnerot-Dumaine, Dec 12 2009
EXTENSIONS
Formula corrected and extended by Michel Dekking, May 03 2018
STATUS
approved