The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A008352 a(n) is formed by concatenating a(n-2) and a(n-1), with a(0) = 1, a(1) = 2; 8
1, 2, 12, 212, 12212, 21212212, 1221221212212, 212122121221221212212, 1221221212212212122121221221212212, 2121221212212212122121221221212212212122121221221212212 (list; graph; refs; listen; history; text; internal format)



A "non-commutative Fibonacci" (or "reverse Fibonacci") sequence. Often written as: a, b, ab, bab, abbab, bababbab, abbabbababbab, bababbababbabbababbab, abbabbababbabbababbababbabbababbab, bababbababbabbababbababbabbababbabbababbababbabbababbab, ...

Converges in the appropriate topology. - Dylan Thurston, Jan 28 2005

Do a web search on bababbababbabbababbab to get further links.

Comments from A. N. W. Hone, Jan 28 2005: (Start)

Write the recurrence symbolically as g_{n+1} = g_{n-1}g_n. Then the determinant d_n = det g_n is given by d_n = d_0^{f_{n-2}} d_1^{f_{n-1}} where f_{n+1} = f_n+f_{n-1}, f_0 = f_1 = 1 are the Fibonacci numbers.

To avoid getting involved with the Baker-Campbell-Hausdorff identity, I now restrict to SL(2), or to make life easier make it SU(2) (which is isomorphic over C). Then we can explicitly write g as an exponential of Lie algebra elements:

g_n = exp (i theta_n v_n cdot sigma ), where theta_n is an angle, v_n is a unit vector and sigma = ( sigma_1, sigma_2, sigma_3)^T is a vector of Pauli spin matrices.

Moreover the adjoint action on su(2) (viewing the coordinates in su(2) as giving points in 3D space) means that g_n gives a rotation through - theta_n /2 about the v_n axis.

So from the double cover of SO(3) by SU(2), we can view the g_n as a sequence of "Fibonacci rotations."

Furthermore, in SU(2) we can write explicitly g_n = cos theta_n + i sin theta_n v_n cdot sigma so the recurrence can be decoupled as

cos theta_{n+1} = cos theta_n + cos theta_{n-1} - sin theta_{n-1} sin theta_n (v_{n-1} cdot v_n),

sin theta_{n+1} v_{n+1} = cos theta_{n-1} sin theta_n v_n + cos theta_n sin theta_{n-1} v_{n-1} - sin theta_{n-1} sin theta_n ( v_{n-1} wedge v_n )


Changing the offset to 1, the sum of the digits of a(n) is 2*Fib(n-1)+Fib(n-2), where Fib(n) means A000045(n), the n-th Fibonacci number. - Stefan Steinerberger, Feb 05 2006

Let beta be the reversed, mirrored Fibonacci morphism on the alphabet {1,2} given by beta(1)=2, beta(2)=12. Then a(n) = beta^n(1), since from the formula beta^2(1)= 12 = 1 beta(1), one sees directly that the iterates of the letter 1 under beta satisfy the defining recursion a(n) = a(n-2)a(n-1). It follows that the a(2n) converge to A189479 with 1,2 replaced by 0 and 1, and the a(2n+1) converge to A287523 with 1,2 replaced by 0 and 1. - Michel Dekking, Sep 30 2019


D. E. Knuth, "The Art of Programming", Volume 1, "Fundamental Algorithms", third edition, problem 36 on page 86.


N. J. A. Sloane, Table of n, a(n) for n = 0..15

Jean Berstel, Fibonacci words—a survey, In The book of L, pp. 13-27. Springer Berlin Heidelberg, 1986.

S. Brlek, E. Duchi, E. Pergola and S. Rinaldi, On the equivalence problem for succession rules, Discr. Math., 298 (2005), 142-154.

C. Delorme, Sequence of maximal distance codes in graphs or other metric spaces, Electronic Journal of Graph Theory and Applications 1 (2) (2013), 118-124.

K. B. Stolarsky, Beatty sequences, continued fractions, and certain shift operators, Canadian Math. Bull. 19 (1976) pp. 473-482.

A. Vieru, Lindenmayer systems and primes, arXiv:math.NT/0803.0852 [math.NT], 2008.

Wikipedia, Lindenmayer system


With offset set to 1, a(1)=1 and a(2)=2, then a(n) = a(n-1)+10^A000045(n)*a(n-2). - Benoit Cloitre, Nov 24 2001

a(n) = beta^n(1), where beta is the morphism 1->2, 2->12. - Michel Dekking, Sep 30 2019


f:=proc(n) option remember; if n = 0 then return(`1`); fi; if n = 1 then return(`2`); fi; cat(f(n-2), f(n-1) ); end;


nxt[{a_, b_}]:={b, FromDigits[Join[IntegerDigits[a], IntegerDigits[b]]]}; NestList[ nxt, {1, 2}, 10][[All, 1]] (* Harvey P. Dale, Jul 16 2017 *)


See A008351 and A003849 for other versions. Cf. A000045, A133235.

Sequence in context: A012598 A156489 A129893 * A082491 A292812 A153302

Adjacent sequences:  A008349 A008350 A008351 * A008353 A008354 A008355




N. J. A. Sloane and J. H. Conway



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 30 12:22 EDT 2020. Contains 338079 sequences. (Running on oeis4.)