cp's OEIS Frontend

A108103 Fixed point of the square of the morphism: 1->3, 2->1, 3->121, starting with 1.

%I A108103 #60 Aug 11 2025 09:50:54
%S A108103 1,2,1,3,1,2,1,3,1,3,1,2,1,3,1,2,1,3,1,3,1,2,1,3,1,3,1,2,1,3,1,2,1,3,
%T A108103 1,3,1,2,1,3,1,2,1,3,1,3,1,2,1,3,1,3,1,2,1,3,1,2,1,3,1,3,1,2,1,3,1,3,
%U A108103 1,2,1,3,1,2,1,3,1,3,1,2,1,3,1,2,1,3,1,3,1,2,1,3,1,3,1,2,1,3,1,2,1,3,1,3,1
%N A108103 Fixed point of the square of the morphism: 1->3, 2->1, 3->121, starting with 1.
%C A108103 Old name was: A Fibonacci like substitution for three-symbol substitution with characteristic polynomial: x^3-2*x-1.
%C A108103 This sequence gives a three-symbol substitution for A095345.
%C A108103 From _Michel Dekking_, Jan 06 2018: (Start) What is probably meant by this statement is that A095345 is a morphic sequence, i.e., a letter-to-letter projection of a fixed point of the morphism tau given by tau(1)=121, tau(2)=3, tau(3)=313, followed by the morphism pi given by pi(1)=1, pi(2)=1, pi(3)=3.
%C A108103 This deserves a proof. In fact a proof can only be given if one formulates a joint statement about the sequences v:=A095345=1113111313... and w:=A095346=3131113...., because these two sequences are defined in a loop. Let D be the so-called differentiation operator which maps a word to the lengths of its runs, as studied in [Dekking, 1981]. For example D(1113111) = 313.
%C A108103 The words v and w by definition satisfy D(v)=w, D(w)=v. They are in fact points of period 2 for D (cf. [Dekking,1995]).
%C A108103 Claim: v=A095345 equals pi(x), where x is the fixed point of tau with x(1)=1, and w=A095346 equals pi(y), where y is the fixed point of tau with y(1)=3.
%C A108103 Proof: This is easily shown by induction on n=2,3,..., proving that tau^(n+1)(1) and tau^(n)(3) satisfy D(pi(tau^(n+1)(1)) = pi(tau^n(3)) & D(pi(tau^n(3)) = pi(tau^n(1)).
%C A108103 (End)
%C A108103 Real Salem Roots: {{x -> -1.}, {x -> -0.618034}, {x -> 1.61803}}.
%C A108103 From _Michel Dekking_, Dec 27 2017: (Start)
%C A108103 Let tau be the morphism squared: tau(1)=121, tau(2)=3, tau(3)=313.
%C A108103 Then tau(a)=a.
%C A108103 Claims:
%C A108103 (A) a(2n-1) = 1 for n = 1,2,....
%C A108103 (B) a(2n) = A282162(n-1) for n = 1,2,....
%C A108103 Proof of (A): Obviously 2 only occurs in 121, but this implies that also 3 only occurs in 131.
%C A108103 Proof of (B): Let R be the 'remove 1' operator, e.g.,  R(12131) = 23.
%C A108103 Let psi be the square of the Fibonacci morphism on the alphabet {3,2}: psi(3)=323, psi(2)=32. One proves by induction that R(tau^k(1))3 = 2psi^(k-1)(3) and R(tau^k(2))2 = 3psi^(k-1)(2) for k=1,2,.... This implies (B): see CROSSREFS in A282162.
%C A108103 We give the more complicated induction step of the two:
%C A108103        R(tau^(k+1)(2))2 = R(tau^k(3))2 =
%C A108103        R(tau^(k-1)(3))R(tau^(k-1)(1))R(tau^(k-1)(3))2 =
%C A108103        R(tau^k(2))2psi^(k-2)(3)3^(-1)R(tau^k(2))2 =
%C A108103        3psi^(k-2)(2)psi^(k-2)(3)psi^(k-1)(2) = 3psi^(k-2)(32332)=
%C A108103        3psi^k(2).
%C A108103 (End)
%D A108103 F. M. Dekking: "What is the long range order in the Kolakoski sequence?" in: The Mathematics of Long-Range Aperiodic Order, ed. R. V. Moody, Kluwer, Dordrecht (1997), pp. 115-125.
%H A108103 Michel Dekking, <a href="/A108103/b108103.txt">Table of n, a(n) for n = 1..1200</a>
%H A108103 F. M. Dekking, <a href="https://www.jstor.org/stable/44166389">On the structure of self-generating sequences</a>, Seminar on Number Theory, 1980-1981 (Talence, 1980-1981), Exp. No. 31, 6 pp., Univ. Bordeaux I, Talence, 1981. Math. Rev. 83e:10075.
%H A108103 F. M. Dekking, <a href="https://citeseerx.ist.psu.edu/pdf/7af40df61b38208d1eccca350f4869b6f1a6a18f">What Is the Long Range Order in the Kolakoski Sequence?</a>, Report 95-100, Technische Universiteit Delft, 1995.
%F A108103 1->121, 2->3, 3->313.
%t A108103 s[1] = {3}; s[2] = {1}; s[3] = {1, 2, 1}; t[a_] := Flatten[s /@ a]; p[0] = {1}; p[1] = t[p[0]]; p[n_] := t[p[n - 1]] a = p[12]
%t A108103 Nest[Flatten[# /. {1 -> {3}, 2 -> {1}, 3 -> {1, 2, 1}}] &, {1}, 10] (* _Robert G. Wilson v_, Nov 05 2015 *)
%o A108103 (Python)
%o A108103 from math import isqrt
%o A108103 def A108103(n): return 1 if n&1 else 1+((k:=n>>1)+isqrt(m:=5*k**2)>>1)-(k-1+isqrt(m-10*k+5)>>1) # _Chai Wah Wu_, May 05 2025
%Y A108103 Cf. A000045, A066983, A282162, A095345, A095346.
%K A108103 nonn
%O A108103 1,2
%A A108103 _Roger L. Bagula_, Jun 03 2005
%E A108103 New name from _Joerg Arndt_, Jan 17 2013
%E A108103 New name from _Robert G. Wilson v_, Nov 05 2015
%E A108103 Name corrected by _Michel Dekking_, Dec 27 2017
%E A108103 Offset 1 from _Michel Dekking_, Jan 01 2020