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

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, 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, 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

Offset: 1

Author

Roger L. Bagula, Jun 03 2005

Keywords

• nonn

Comments

Old name was: A Fibonacci like substitution for three-symbol substitution with characteristic polynomial: x^3-2*x-1.

This sequence gives a three-symbol substitution for A095345.

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.

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.

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]).

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.

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)).

(End)

Real Salem Roots: {{x -> -1.}, {x -> -0.618034}, {x -> 1.61803}}.

From Michel Dekking, Dec 27 2017: (Start)

Let tau be the morphism squared: tau(1)=121, tau(2)=3, tau(3)=313.

Then tau(a)=a.

Claims:

(A) a(2n-1) = 1 for n = 1,2,....

(B) a(2n) = A282162(n-1) for n = 1,2,....

Proof of (A): Obviously 2 only occurs in 121, but this implies that also 3 only occurs in 131.

Proof of (B): Let R be the 'remove 1' operator, e.g., R(12131) = 23.

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.

We give the more complicated induction step of the two:

R(tau^(k+1)(2))2 = R(tau^k(3))2 =

R(tau^(k-1)(3))R(tau^(k-1)(1))R(tau^(k-1)(3))2 =

R(tau^k(2))2psi^(k-2)(3)3^(-1)R(tau^k(2))2 =

3psi^(k-2)(2)psi^(k-2)(3)psi^(k-1)(2) = 3psi^(k-2)(32332)=

3psi^k(2).

(End)

References

• 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.

Links

• Michel Dekking, Table of n, a(n) for n = 1..1200
• F. M. Dekking, On the structure of self-generating sequences, Seminar on Number Theory, 1980-1981 (Talence, 1980-1981), Exp. No. 31, 6 pp., Univ. Bordeaux I, Talence, 1981. Math. Rev. 83e:10075.
• F. M. Dekking, What Is the Long Range Order in the Kolakoski Sequence?, Report 95-100, Technische Universiteit Delft, 1995.

Crossrefs

Cf. A000045, A066983, A282162, A095345, A095346.

Programs

Mathematica

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]
Nest[Flatten[# /. {1 -> {3}, 2 -> {1}, 3 -> {1, 2, 1}}] &, {1}, 10] (* Robert G. Wilson v, Nov 05 2015 *)

Python

from math import isqrt
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

Formula

1->121, 2->3, 3->313.

Extensions

New name from Joerg Arndt, Jan 17 2013

New name from Robert G. Wilson v, Nov 05 2015

Name corrected by Michel Dekking, Dec 27 2017

Offset 1 from Michel Dekking, Jan 01 2020