A105083 Trajectory of 1 under the morphism 1 -> 12, 2 -> 3, 3 -> 1.

1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 2, 3, 1, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 2, 3, 1, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 2, 3, 1, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 2, 3, 1, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 2

Offset: 0

Author

Roger L. Bagula, Apr 06 2005

Keywords

• nonn

Links

• Aresh Pourkavoos, Table of n, a(n) for n = 0..10000
• P. Arnoux and E. Harriss, What is a Rauzy Fractal?, Notices Amer. Math. Soc., 61 (No. 7, 2014), 768-770, also p. 704 and front cover.
• Marcy Barge and Jaroslaw Kwapisz, Geometric theory of unimodular Pisot substitutions, Amer. J. Math. 128 (2006), no. 5, 1219--1282. MR2262174 (2007m:37039). - _N. J. A. Sloane_, Aug 06 2014
• Jeffrey Shallit, The Narayana Morphism and Related Words, arXiv:2503.01026 [math.CO], 2025.
• Victor F. Sirvent and Yang Wang, Self-Affine Tiling via Substitution Dynamical Systems and Rauzy Fractals, Pac. J. Math., 206 (2002), 465-485. See Example 2.2 and Figure 2 pp. 474-475.
• Index entries for sequences that are fixed points of mappings

Crossrefs

Cf. A005374, A073058, A092782, A202340, A245553, A245554, A000930.

Programs

Mathematica

Nest[ Function[ l, {Flatten[(l /. {1 -> {1, 2}, 2 -> {3}, 3 -> {1}})] }], {1}, 12]

Python

N_TERMS=10000
def a():
  # Index of the current term
  n = 0
  # Stores the place values of the greedy representation of n,
  # minus two since A000930 begins with duplicate ones.
  places = []
  # Edge case: a(0)=1.
  yield 0, 1
  while True:
    n += 1
    # Add A000930(2+0)=1 to the representation of n
    places.append(0)
    # Apply carryover rule for as long as necessary:
    # if places contains n+2 and n,
    # both terms are replaced by n+3.
    while len(places) > 1 and places[-2] <= places[-1]+2:
      places.pop()
      places[-1] += 1
    # Look at the smallest term to decide a(n)
    an = 1 if places[-1] > 1 else places[-1]+2
    yield n, an
# Asymptotic behavior is O(log(n)*log(log(n))) memory
# and O(n) time to generate the first n terms,
# although a term may take as long as O(log(n)).
for n, an in a():
  print(n, an)
  if (n >= N_TERMS):
    break
# Aresh Pourkavoos, Jan 26 2021

Formula

From Aresh Pourkavoos, Jan 26 2021: (Start)

Limit S(infinity) of the following strings: S(0) = 2, S(1) = 1, S(2) = 0, S(n+3) = S(n+2)S(n). S(n) has length A000930(n).

Individual terms of a(n) may also be found by greedily writing n as a sum of entries of A000930. a(n) is 2 if the smallest term is 1, 3 if the smallest term is 2, and 1 otherwise.

(End)

a(n) = A005374(n+1) - A005374(n) - 2*(A202340(n+1) - 2). - Alan Michael Gómez Calderón, Jul 19 2025

Extensions

Edited by N. J. A. Sloane, Oct 10 2007 and Aug 03 2014