|
%I #39 Sep 30 2019 21:59:34
%S 1,2,12,212,12212,21212212,1221221212212,212122121221221212212,
%T 1221221212212212122121221221212212,
%U 2121221212212212122121221221212212212122121221221212212
%N a(n) is formed by concatenating a(n-2) and a(n-1), with a(0) = 1, a(1) = 2;
%C A "non-commutative Fibonacci" (or "reverse Fibonacci") sequence. Often written as: a, b, ab, bab, abbab, bababbab, abbabbababbab, bababbababbabbababbab, abbabbababbabbababbababbabbababbab, bababbababbabbababbababbabbababbabbababbababbabbababbab, ...
%C Converges in the appropriate topology. - _Dylan Thurston_, Jan 28 2005
%C Do a web search on bababbababbabbababbab to get further links.
%C Comments from A. N. W. Hone, Jan 28 2005: (Start)
%C 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.
%C 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:
%C 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.
%C 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.
%C So from the double cover of SO(3) by SU(2), we can view the g_n as a sequence of "Fibonacci rotations."
%C 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
%C cos theta_{n+1} = cos theta_n + cos theta_{n-1} - sin theta_{n-1} sin theta_n (v_{n-1} cdot v_n),
%C 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 )
%C (End)
%C 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
%C 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 D. E. Knuth, "The Art of Programming", Volume 1, "Fundamental Algorithms", third edition, problem 36 on page 86.
%H N. J. A. Sloane, <a href="/A008352/b008352.txt">Table of n, a(n) for n = 0..15</a>
%H Jean Berstel, <a href="http://www-igm.univ-mlv.fr/~berstel/Articles/1985BookOfL.pdf">Fibonacci words—a survey</a>, In The book of L, pp. 13-27. Springer Berlin Heidelberg, 1986.
%H S. Brlek, E. Duchi, E. Pergola and S. Rinaldi, <a href="http://dx.doi.org/10.1016/j.disc.2004.07.019">On the equivalence problem for succession rules</a>, Discr. Math., 298 (2005), 142-154.
%H C. Delorme, <a href="http://dx.doi.org/10.5614/ejgta.2013.1.2.5">Sequence of maximal distance codes in graphs or other metric spaces</a>, Electronic Journal of Graph Theory and Applications 1 (2) (2013), 118-124.
%H K. B. Stolarsky, <a href="http://dx.doi.org/10.4153/CMB-1976-071-6">Beatty sequences, continued fractions, and certain shift operators</a>, Canadian Math. Bull. 19 (1976) pp. 473-482.
%H A. Vieru, <a href="http://arXiv.org/abs/0803.0852">Lindenmayer systems and primes</a>, arXiv:math.NT/0803.0852 [math.NT], 2008.
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Lindenmayer_system">Lindenmayer system</a>
%F 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
%F a(n) = beta^n(1), where beta is the morphism 1->2, 2->12. - _Michel Dekking_, Sep 30 2019
%p 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;
%t nxt[{a_,b_}]:={b,FromDigits[Join[IntegerDigits[a],IntegerDigits[b]]]}; NestList[ nxt,{1,2},10][[All,1]] (* _Harvey P. Dale_, Jul 16 2017 *)
%Y See A008351 and A003849 for other versions. Cf. A000045, A133235.
%K nonn,base
%O 0,2
%A _N. J. A. Sloane_ and _J. H. Conway_
| 