A143667 -id:A143667 - cp's OEIS frontend

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

Alexis Monnerot-Dumaine, Dec 12 2009

nonn

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

			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.

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]

Cf. A143667, A003849. Cf. A379184, A379274, A379275.

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

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

(* 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 *)

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)

Formula corrected and extended by Michel Dekking, May 03 2018

A123564 The infinite Fibonacci word reencoded by writing successive non-overlapping pairs of bits as decimal numbers.

Original entry on oeis.org

2, 3, 1, 1, 2, 3, 1, 1, 2, 2, 3, 1, 2, 2, 3, 1, 2, 2, 3, 1, 1, 2, 3, 1, 1, 2, 2, 3, 1, 2, 2, 3, 1, 2, 2, 3, 1, 1, 2, 3, 1, 1, 2, 3, 1, 1, 2, 2, 3, 1, 2, 2, 3, 1, 1, 2, 3, 1, 1, 2, 3, 1, 1, 2, 2, 3, 1, 2, 2, 3, 1, 1, 2, 3, 1, 1, 2, 3, 1, 1, 2, 2, 3, 1, 2, 2, 3, 1

Offset: 1

Alexandre Losev, Nov 12 2006

The algorithm used here suggests multiple variations such as using more than 2 bits, allowing overlap of successive subwords, using other numbers for the encoding of subwords or using other binary sequences. (E.g. overlapping: a(n) = 2*A005614(n) + A005614(n+1) )

Essentially equal to A143667. - Michel Dekking, Sep 26 2017

			a(1) = 2*1+0 = 2;
a(2) = 2*1+1 = 3;
a(3) = 2*0+1 = 1.

G. C. Greubel, Table of n, a(n) for n = 1..5000
Michel Dekking and Mike Keane, Two-block substitutions and morphic words, arXiv:2202.13548 [math.CO], 2022.

Cf. A005614, A143667

f := 1/GoldenRatio; T[n_] := Floor[2*n*f] - 2*Floor[(2*n - 1)*f] + Floor[(2*n + 1)*f]; Table[T[n], {n, 100}] (* G. C. Greubel, Oct 16 2017 *)

f=(sqrt(5)-1)/2; a(n)= my(m=2*n); floor(m*f)-2*floor((m-1)*f)+floor((m+1)*f); \\ Michel Marcus, Sep 26 2017

f = (sqrt(5)-1)/2; m = 2*n; a(n) = floor(m*f) - 2*floor((m-1)*f) + floor((m+1)*f);

a(n) = 2*A005614(2n-1) + A005614(2n), using the infinite Fibonacci word A005614.

A156596 Infinite Fibonacci word fractal sequence.

Original entry on oeis.org

1, 0, 1, 2, 0, 2, 0, 2, 1, 0, 1, 2, 0, 2, 0, 2, 1, 0, 1, 0, 1, 2, 0, 2, 1, 0, 1, 0, 1, 2, 0, 2, 1, 0, 1, 0, 1, 2, 0, 2, 0, 2, 1, 0, 1, 2, 0, 2, 0, 2, 1, 0, 1, 0, 1, 2, 0, 2, 1, 0, 1, 0, 1, 2, 0, 2, 1, 0, 1, 0, 1, 2, 0, 2, 0, 2, 1, 0, 1, 2, 0, 2, 0, 2, 1, 0, 1, 2, 0, 2, 0, 2, 1, 0, 1, 0, 1, 2, 0, 2, 1, 0, 1, 0, 1

Offset: 1

Alexis Monnerot-Dumaine, Feb 10 2009

Apply to A143667 the map : 0 -> 12, 1 -> 10, 2 -> 02. or apply to A003849 (the Fibonacci word), after grouping the terms 2 by 2, the map : "00" -> "12", "01"->"10, "10"->"02". Draws the Fibonacci word fractal curve when applying the following drawing rule: if "0" then draw a segment forward, if "1" then draw a segment forward and turn 90A degs right, if "2" the draw segment and turn 90A degs left.

M. Lothaire, Combinatorics on words, Cambridge University Press.

Reinhard Zumkeller, Table of n, a(n) for n = 1..1000
A. Monnerot-Dumaine, Fibonacci word fractal
Alexis Monnerot-Dumaine, The Fibonacci word fractal [Cached copy, with permission]

Cf. A003849, A143667.

a143667 n = a143667_list !! (n-1)
a143667_list = f a003849_list where
   f (0:0:ws) = 0 : f ws; f (0:1:ws) = 1 : f ws; f (1:0:ws) = 2 : f ws
-- Reinhard Zumkeller, Jul 29 2014

Partition[Nest[Flatten[# /. {0 -> {0, 1}, 1 -> {0}}]&, {0}, 10], 2] /. {{0, 0} -> {1, 2}, {0, 1} -> {1, 0}, {1, 0} -> {0, 2}} // Flatten (* Jean-François Alcover, Jul 16 2015 *)

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Go

Mathematica

Formula

Extensions

A123564 The infinite Fibonacci word reencoded by writing successive non-overlapping pairs of bits as decimal numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A156596 Infinite Fibonacci word fractal sequence.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Mathematica