A003842 -id:A003842 - cp's OEIS frontend

A213975 List of subwords of A003842 arranged in lexicographic order.

1, 2, 11, 12, 21, 112, 121, 211, 212, 1121, 1211, 1212, 2112, 2121, 11211, 11212, 12112, 12121, 21121, 21211, 112112, 112121, 121121, 121211, 211211, 211212, 212112, 1121121, 1121211, 1211211, 1211212, 1212112, 2112112, 2112121, 2121121, 11211212, 11212112

Offset: 1

N. J. A. Sloane, Jul 03 2012, Jul 10 2012

nonn

The Fibonacci word A003842 is a Sturmian word, which means that there are exactly n+1 different factors (or subwords) of length n for all n.

For another version of this sequence see the Noe link at A003849 (and included below).

			A003842 begins 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, ... and we can see factors 1, 2, 11, 12, 21, but not 22.

Alois P. Heinz, Table of n, a(n) for n = 1..10010
Wai-Fong Chuan and Hui-Ling Ho, Locating factors of the infinite Fibonacci word, Theoret. Comput. Sci. 349 (2005), no. 3, 429--442. MR2183167 (2007c:68115)
James D. Currie and Kalle Saari, Least Periods of Factors of Infinite Words, RAIRO - Theoretical Informatics and Applications, January 2009, 43, pp. 165-178.
M. Lothaire, Algebraic Combinatorics on Words, Cambridge, 2002; see Chap. 2.
F. Mignosi, A. Restivo, M. Sciortino, Words and forbidden factors, WORDS (Rouen, 1999). Theoret. Comput. Sci. 273 (2002), no. 1-2, 99--117. MR1872445 (2002m:68096).
T. D. Noe, The first 1652 subwords of A003849, including leading zeros.
Kalle Saari, Periods of factors of the Fibonacci word, Department of Mathematics and Turku Centre for Computer Science, University of Turku, 2001 4 Turku, Finland.
Kalle Saari, Periods of factors of the Fibonacci word, in Proceedings of the Sixth International Conference on Words (WORDS’07). Institut de Mathématiques de Luminy (2007) 273-279.
Zhi-Xiong Wen and Zhi-Ying Wen, Some properties of the singular words of the Fibonacci word, European J. Combin. 15 (1994), 587-598.

Cf. A003842, A214207, A214208, A214209, A214216, A214217.

S:= proc(n) option remember;
      `if`(n<2, [2-n], [S(n-1)[], S(n-2)[]])
    end:
T:= proc(n) local k, l, m, s;
      for k while nops(S(k))Alois P. Heinz, Jul 04 2012

nmax = 10;
seq[steps_] := seq[steps] = (S = SubstitutionSystem[{1 -> {1, 2}, 2 -> {1}}, {1}, steps] // Last; T[n_] := FromDigits /@ Union[Partition[S, n, 1]]; Table[T[n], {n, 1, nmax}] // Flatten);
seq[s = 1];
While[seq[s] != seq[s-1], s++];
seq[s] (* Jean-François Alcover, Apr 28 2020 *)

The list S(n), say, of words of length n in this sequence can be constructed recursively as follows.
There are two words of length 1, namely S(1)={1,2}.
The n+2 words in S(n+1) are obtained from the n+1 words in S(n) thus:
if u in S(n) is the reverse of a prefix of the Fibonacci word A003842 then both u0 and u1 are in S(n+1), otherwise u in S(n) has a unique extension ux in S(n+1), where x is determined by the requirement that no right factor of ux is one of the forbidden words listed in A214216.
For example, A214216 contains both 22 and 111. So if u ends with 2 then (since 22 is forbidden), x=1 and u1 is in S(n+1), while if u ends with 11 then (since 111 is forbidden) x=2 and u2 is in S(n+1).
On the other hand, consider for example u=21121 in S(5), which is the reverse of the first 5 digits of A003842. Now both u1 and u2 are in S(6).

A378397 Rectangular array read by descending antidiagonals: (row 1) = u, and for n >= 2, (row n) = u-inverse runlength sequence of u, where u = A003842 (an infinite Fibonacci word). See Comments.

Original entry on oeis.org

1, 2, 2, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 2, 1, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 1

Offset: 1

Clark Kimberling, Dec 21 2024

If u and v are sequences, both consisting of 1's and 2's, we call v an inverse runlength sequence of u if u is the runlength sequence of v. Each u has two inverse runlength sequences, one with first term 1 and the other with first term 2. Consequently, an inverse runlength array, in which each row after the first is an inverse runlength sequence of the preceding row, is determined by its first column. Generally, if the first column is periodic with fundamental period p, then the array has p distinct limiting sequences; otherwise, there is no limiting sequence; however, if a segment, of any length, occurs in a row, then it also occurs in a subsequent row. See A378282 for details and related sequences.

			The corner of the array begins:
   1  2  1  1  2  1  2  1  1  2  1  1  2  1  2  1  1  2  1  2  1
   2  1  1  2  1  2  2  1  2  2  1  2  1  1  2  1  2  2  1  2  2
   1  1  2  1  2  2  1  2  2  1  1  2  1  1  2  2  1  2  2  1  2
   1  2  1  1  2  1  1  2  2  1  2  2  1  1  2  1  2  2  1  2  1
   2  1  1  2  1  2  2  1  2  1  1  2  2  1  2  2  1  1  2  1  2
   1  1  2  1  2  2  1  2  2  1  1  2  1  1  2  1  2  2  1  1  2
   2  1  2  2  1  2  2  1  1  2  1  1  2  2  1  2  1  1  2  1  2
   1  1  2  1  1  2  2  1  2  2  1  1  2  1  2  2  1  2  1  1  2
   1  2  1  1  2  1  2  2  1  1  2  1  1  2  2  1  2  1  1  2  1
   2  1  1  2  1  2  2  1  2  2  1  1  2  1  2  2  1  2  1  1  2
   1  1  2  1  2  2  1  2  2  1  1  2  1  1  2  2  1  2  1  1  2
   1  2  1  1  2  1  1  2  2  1  2  2  1  1  2  1  2  2  1  2  1

Cf. A003842, A378282, A378396, A378398, A378399, A378401.

invRE[seq_, k_] := Flatten[Map[ConstantArray[#[[2]], #[[1]]] &,
    Partition[Riffle[seq, {k, 2 - Mod[k + 1, 2]}, {2, -1, 2}], 2]]];
row1 = SubstitutionSystem[{1 -> {1, 2}, 2 -> {1}}, {1}, {7}][[1]] (* A003842 *);
rows = {row1}; col = Take[row1, 12];
Do[AppendTo[rows, Take[invRE[Last[rows], col[[n]]], Length[row1]]], {n, 2, Length[col]}]
rows // ColumnForm  (* array *)
w[n_, k_] := rows[[n]][[k]]; Table[w[n - k + 1, k], {n, 12}, {k, n, 1, -1}] // Flatten (* sequence *)
(* Peter J. C. Moses, Nov 20 2024 *)

A214317 a(n) = length-n prefix of the Fibonacci word A003842.

Original entry on oeis.org

1, 12, 121, 1211, 12112, 121121, 1211212, 12112121, 121121211, 1211212112, 12112121121, 121121211211, 1211212112112, 12112121121121, 121121211211212, 1211212112112121, 12112121121121211, 121121211211212112, 1211212112112121121, 12112121121121211212

Offset: 1

N. J. A. Sloane, Jul 12 2012

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..300

Cf. A003842, A214318.

S:= proc(n) option remember;
      `if`(n<2, [2-n], [S(n-1)[], S(n-2)[]])
    end:
a:= proc(n) local k;
      for k while nops(S(k))Alois P. Heinz, Jul 19 2012

S = SubstitutionSystem[{1 -> {1, 2}, 2 -> {1}}, {1}, 20];
FromDigits[Take[#[[1]], #[[2]]]]& /@ Transpose[{S, Range[Length[S]]}] (* Jean-François Alcover, Nov 07 2020 *)

A113533 Ascending descending base exponent transform of the infinite Fibonacci word (A003842).

Original entry on oeis.org

1, 3, 6, 5, 7, 12, 10, 15, 14, 14, 23, 16, 20, 27, 21, 30, 27, 25, 40, 28, 37, 38, 32, 49, 36, 40, 53, 39, 54, 49, 43, 68, 45, 55, 66, 50, 71, 60, 56, 83, 57, 74, 75, 61, 92, 67, 73, 94, 68, 93, 84, 72, 113, 75, 94, 101, 79, 116, 89, 91, 122, 86, 115, 108, 90

Offset: 1

Jonathan Vos Post, Jan 13 2006

The infinite Fibonacci word b(n) is the fixed point of the morphism 1->12, 2->1, starting from b(1) = 2. This transform a(n) of that sequence b(n) satisfies n <= a(n) <= 4*n, but that is not a tight bound.

			a(1) = A003842(1)^A003842(1) = 1^1 = 1.
a(2) = A003842(1)^A003842(2) + A003842(2)^A003842(1) = 1^2 + 2^1 = 3.
a(3) = 1^1 + 2^2 + 1^1 = 6.
a(4) = 1^1 + 2^1 + 1^2 + 1^1 = 5.
a(5) = 1^2 + 2^1 + 1^1 + 1^2 + 2^1 = 7.
a(6) = 1^1 + 2^2 + 1^1 + 1^1 + 2^2 + 1^1 = 12.
a(7) = 1^2 + 2^1 + 1^2 + 1^1 + 2^1 + 1^2 + 2^1 = 10.
a(8) = 1^1 + 2^2 + 1^1 + 1^2 + 2^1 + 1^1 + 2^2 + 1^1 = 15.
a(9) = 1^1 + 2^1 + 1^2 + 1^1 + 2^2 + 1^1 + 2^1 + 1^2 + 1^1 = 14.
a(10) = 1^2 + 2^1 + 1^1 + 1^2 + 2^1 + 1^2 + 2^1 + 1^1 + 1^2 + 2^1 = 14.

G. C. Greubel, Table of n, a(n) for n = 1..1000

Cf. A003842, A005408, A087316, A113122, A113153, A113154, A113208, A113231, A113257, A113258, A113271, A113320, A113336, A113498.

A003842[n_] := n + 1 - Floor[((1 + Sqrt[5])/2)*Floor[2*(n + 1)/(1 + Sqrt[5])]]; Table[Sum[A003842[k]^(A003842[n - k + 1]), {k, 1, n}], {n, 1, 50}] (* G. C. Greubel, May 18 2017 *)

a(n) = Sum_{k=1..n} A003842(k)^(A003842(n-k+1)). - G. C. Greubel, May 18 2017

Corrected and extended by Giovanni Resta, Jun 13 2016

A214217 List of singular subwords (or factors) of the Fibonacci word A003842.

Original entry on oeis.org

2, 11, 212, 11211, 21211212, 1121121211211, 212112121121121211212, 1121121211211212112121121121211211, 2121121211211212112121121121211211212112121121121211212, 11211212112112121121211211212112112121121211211212112121121121211211212112121121121211211

Offset: 1

N. J. A. Sloane, Jul 10 2012

nonn

Complementing the first and last digits of each term gives (essentially) A214216.

Kalle Saari, Periods of factors of the Fibonacci word, Department of Mathematics and Turku Centre for Computer Science, University of Turku, 2001 4 Turku, Finland.
Kalle Saari, Periods of factors of the Fibonacci word, in Proceedings of the Sixth International Conference on Words (WORDS’07). Institut de Mathématiques de Luminy (2007) 273-279.
Zhi-Xiong Wen and Zhi-Ying Wen, Some properties of the singular words of the Fibonacci word, European J. Combin. 15 (1994), 587-598.

Cf. A003842, A214216.

nxt[{a_,b_,c_}]:={b,c,FromDigits[Join[Flatten[IntegerDigits/@{b,a,b}]]]}; NestList[nxt,{2,11,212},10][[All,1]] (* Harvey P. Dale, May 24 2018 *)

a(0)=2, a(1)=11, a(2)=212; thereafter a(n)=the concatenation of a(n-2), a(n-3), and a(n-2). [clarified by Harvey P. Dale, May 24 2018]

A342959 Number of 1's within a sample word of length 10^n of the infinite Fibonacci word A003842 where n is the sequence index.

Original entry on oeis.org

1, 6, 62, 618, 6180, 61804, 618034, 6180340, 61803399, 618033989, 6180339888, 61803398875, 618033988750, 6180339887499, 61803398874990, 618033988749895, 6180339887498949, 61803398874989485, 618033988749894848, 6180339887498948482, 61803398874989484821

Offset: 0

Frank M Jackson, Mar 31 2021

nonn

The proportion of 1's within the sample word length tends to 1/phi = 0.6180339887... (A094214) as the sample size increases to infinity.

			a(1) = 6 because the first sample of the infinite Fibonacci word has a word length of 10. The word sample is (1, 2, 1, 1, 2, 1, 2, 1, 1, 2) and #1's = 6.

Rémy Sigrist, Table of n, a(n) for n = 0..1000
Rémy Sigrist, PARI program for A342959

Cf. A003842, A094214, A005614, A005206.

set=Nest[Flatten[# /. {1 -> {1, 2}, 2 -> {1}}] &, {1}, 40]; Table[First@Counts@set[[1;;10^n]], {n, 1, 8}]

PARI
```
See Links section.
```

my(s=quadgen(5)-1); a(n) = floor((10^n+1)*s); \\ Kevin Ryde, Apr 09 2021

from math import isqrt
def A342959(n): return ((m:=10**n+1)+isqrt(5*m**2)>>1)-m # Chai Wah Wu, Aug 09 2022

a(n) = A005206(10^n). - Rémy Sigrist, Apr 05 2021

a(0) = 1 prepended and more terms from Rémy Sigrist, Apr 05 2021

A074983 Successive factors of the Fibonacci word A003842.

Original entry on oeis.org

12, 11212, 1121121211212, 1121121211211212112121121121211212, 11211212112112121121211211212112112121121211211212112121121121211211212112121121121211212

Offset: 1

N. J. A. Sloane, Mar 28 2003

a(6) is 233 digits long. - Sean A. Irvine, Oct 31 2011

G. Melançon, Lyndon factorization of infinite words, STACS 96 (Grenoble, 1996), 147-154, Lecture Notes in Comput. Sci., 1046, Springer, Berlin, 1996. Math. Rev. 98h:68188.

Let b(1)=112, b(2)=12, a(1)=12. If a(n)=c(1)c(2)...c(m), then a(n+1)=b(c(1))b(c(2))...b(c(m)), where c(i) is the i-th digit of a(n). - Sean A. Irvine, Oct 31 2011

More terms from Sean A. Irvine, Oct 30 2011

A108282 a(n) = k*a(n-1) + a(n-2) where k = A003842(a); a(0) = 1.

Original entry on oeis.org

1, 2, 3, 5, 13, 18, 49, 67, 116, 299, 415, 714, 1843, 2557, 6957, 9514, 16471, 42456, 58927, 160310, 219237, 379547, 978331, 1357878, 2336209, 6030296, 8366505, 22763306, 31129811, 53893117, 138916045, 192809162, 331725207, 856259576

Offset: 0

Gary W. Adamson, May 30 2005

nonn

Aperiodic recursive rabbit sequence.

The recursive Fibonacci-like multiplier k is derived from the rabbit sequence (1 0 1 1 0 1 0 1...) in which the 0's are replaced by 2's, getting the rabbit sequence of A003842: (1 2 1 1 2 1 2 1...).

			a(6) = 49 = 2*18 + 13; where 2 = A003842(6)

Cf. A003842.

Corrected and extended by T. D. Noe, Nov 02 2006

A214211 Doubled Fibonacci word: the A003842 sequence replacing 1 with 1,1 and 2 with 2,2.

Original entry on oeis.org

1, 1, 2, 2, 1, 1, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 1, 1, 2, 2, 1, 1, 2

Offset: 0

N. J. A. Sloane, Jul 10 2012

nonn

Suggested by reading Mignosi et al. (2002).

F. Mignosi, A. Restivo, M. Sciortino, Words and forbidden factors, WORDS (Rouen, 1999). Theoret. Comput. Sci. 273 (2002), no. 1-2, 99--117. MR1872445 (2002m:68096).

Cf. A003842, A095190.

A264119 Look and say for Fibonacci word A003842.

Original entry on oeis.org

1, 1, 1, 2, 2, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 2, 1

Offset: 0

Michel Marcus, Apr 03 2016

nonn

Define strings S(0)=2, S(1)=1, S(n)=S(n-1)S(n-2); iterate.
A003842 is S(infinity) and begins 1, 2, 1, 1, 2, 1, 2.
We see one 1, one 2, two 1, one 2, one 1, one 2.
So this sequences begins 1,1, 1,2, 2,1, 1,2, 1,1, 1,2.

Patrice Séébold, Look and Say Fibonacci, RAIRO-Theor. Inf. Appl. 42 (2008) 729-746.

Cf. A003842.

lns(v) = {vls = []; nb = 0; old = -1; for (k=1, #v, if (v[k] == old, nb++, if (old != -1, vls = concat(vls, nb); vls = concat(vls, old);); nb = 1;); old = v[k];); vls = concat(vls, nb); vls = concat(vls, old); vls;}
lista(nn=11) = {v = [2]; w = [1]; for (k=1, nn, nw = concat(w, v); v = w; w = nw;); lns(w);}

cp's OEIS Frontend

A213975 List of subwords of A003842 arranged in lexicographic order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A378397 Rectangular array read by descending antidiagonals: (row 1) = u, and for n >= 2, (row n) = u-inverse runlength sequence of u, where u = A003842 (an infinite Fibonacci word). See Comments.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A214317 a(n) = length-n prefix of the Fibonacci word A003842.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

A113533 Ascending descending base exponent transform of the infinite Fibonacci word (A003842).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A214217 List of singular subwords (or factors) of the Fibonacci word A003842.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A342959 Number of 1's within a sample word of length 10^n of the infinite Fibonacci word A003842 where n is the sequence index.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Python

Formula

Extensions

A074983 Successive factors of the Fibonacci word A003842.

Views

Author

Keywords

Comments

References

Formula

Extensions

A108282 a(n) = k*a(n-1) + a(n-2) where k = A003842(a); a(0) = 1.

Views

Author

Keywords