A275925 Trajectory of 3 under repeated application of the morphism sigma: 3 -> 3656, 5 -> 365656, 6 -> 3656656.

3, 6, 5, 6, 3, 6, 5, 6, 6, 5, 6, 3, 6, 5, 6, 5, 6, 3, 6, 5, 6, 6, 5, 6, 3, 6, 5, 6, 3, 6, 5, 6, 6, 5, 6, 3, 6, 5, 6, 5, 6, 3, 6, 5, 6, 6, 5, 6, 3, 6, 5, 6, 6, 5, 6, 3, 6, 5, 6, 5, 6, 3, 6, 5, 6, 6, 5, 6, 3, 6, 5, 6, 3, 6, 5, 6, 6, 5, 6, 3, 6, 5, 6, 5, 6, 3, 6, 5, 6, 6, 5, 6, 3, 6, 5, 6, 5, 6, 3, 6

Offset: 1

Author

N. J. A. Sloane, Aug 29 2016

Keywords

• nonn

Comments

Versions of this sequence arises in so many different ways in the analysis of the Lonely Queens problem described in A140100-A140103 that it is convenient to define THETA(a,b,c) to be the result of replacing {6,5,3} here by {a,b,c} respectively. - N. J. A. Sloane, Mar 19 2019

Conjecture 1: This sequence is a compressed version of A140101 (see that entry for details). [This was formerly stated as a theorem, but I am no longer sure I have a proof. - N. J. A. Sloane, Sep 29 2018. It is true: see the Dekking et al. paper. - N. J. A. Sloane, Jul 22 2019]

From Michel Dekking, Dec 12 2018: (Start)

Let tau be the tribonacci morphism from A092782, but on the alphabet {6,5,3}, i.e., tau(3)=6, tau(5)=63, tau(6)=65. Then tau^3 is given by

3 -> 6563, 5 -> 656365, 6 -> 6563656.

Let sigma be the morphism generating (a(n)). Then sigma is conjugate to tau^3 with conjugating word u = 656:

(656)^{-1} tau^3(3) 656 = 3656 = sigma(3)

(656)^{-1} tau^3(5) 656 = 365656 = sigma(5)

(656)^{-1} tau^3(6) 656 = 3656656 = sigma(6).

It follows that tau and sigma generate the same language, in particular the frequencies of corresponding letters are equal.

Added Mar 03 2019: Since tau and sigma are irreducible morphisms (which means that their incidence matrices are irreducible), all of their fixed points have the same collection of subwords, this is what is called the language of tau, respectively sigma. See Lemma 3 of Allouche et al. (2003) for background.

(End)

From N. J. A. Sloane, Mar 03 2019: (Start)

The tribonacci word A092782 is the limit S_oo where f is the morphism 1 -> 12, 2 -> 13, 3 -> 1; S_0 = 1, and S_n = f(S_{n-1}).

The present sequence is the limit T_oo where

sigma: 3 -> 3656, 5 -> 365656, 6 -> 3656656; T_0 = 3, and T_n = sigma(T_{n-1}).

Conjecture 2: For all k=0,1,2,..., the following two finite words are identical:

S_{3k+2} with 1,2 mapped to 6,5 respectively, and 3 fixed,

T_{k+1} with its initial 3 moved to the end.

Example for k=1:

S_5 = 1, 2, 1, 3, 1, 2, 1, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 1, 2, 1, 3,

T_2 = 3, 6, 5, 6, 3, 6, 5, 6, 6, 5, 6, 3, 6, 5, 6, 5, 6, 3, 6, 5, 6, 6, 5, 6,

Note that S_{3k+2} has length A000073(3k+5) and always ends with a 3.

The conjecture would imply that if we omit the initial 3 here, and change 6 to 1, 5 to 2, and leave 3 fixed, we get A092782. Alternatively, if we omit the initial 3 here, and change 6 to 0, 5 to 1, and 3 to 2, we get A080843.

(End)

From Michel Dekking, Mar 11 2019: (Start)

Proof of Conjecture 2.

It is convenient to apply the letter to letter map 1->6, 2->5, 3->3 from the start, which changes f^3 to tau^3. Let alpha := tau^3.

We prove by induction that 3 alpha^n(3) = sigma^n(3) 3.

This is true for n=1: 3 alpha(3) = 3 6563 = sigma(3) 3.

The conjugation observation in my comment from December 12 implies that for all words w from the language of tau:

alpha(w) 656 = 656 sigma(w).

Applying this with the word w = alpha^n(3) yields

3 alpha^{n+1}(3) 656 = 3 656 sigma(alpha^n(3)) =

sigma(3 alpha^n(3)) = sigma(sigma^n(3) 3) =

sigma^{n+1}(3) 3656,

where we used the induction hypothesis in the second line. Removing the 656's at the end completes the induction step.

(End)

Lengths of runs of 2's in A276788. - John Keith, May 15 2022

Examples

			The first few generations of the iteration are:
3
3656
365636566563656563656656
3656365665636565636566563656365665636565636566563656656365656365665636563656656\
   3656563656656365656365665636563656656365656365665636566563656563656656
...
		

Links

• N. J. A. Sloane, Table of n, a(n) for n = 1..35890
• J.-P. Allouche, M. Baake, J. Cassaigns, and D. Damanik, Palindrome complexity, arXiv:math/0106121 [math.CO], 2001; Theoretical Computer Science, 292 (2003), 9-31.
• F. Michel Dekking, Jeffrey Shallit, and N. J. A. Sloane, Queens in exile: non-attacking queens on infinite chess boards, Electronic J. Combin., 27:1 (2020), #P1.52.
• Index entries for sequences that are fixed points of mappings

Crossrefs

Cf. A140100, A140101, A273059, A000073.

See A276790 and A277745 for other versions. See also A276788 and A080843, A092782.

For partial sums see A305373, also A276796, A276797, A276798.

Programs

Mathematica

SubstitutionSystem[{3 -> {3, 6, 5, 6}, 5 -> {3, 6, 5, 6, 5, 6}, 6 -> {3, 6, 5, 6, 6, 5, 6}}, {3}, 3] // Last (* Jean-François Alcover, Jan 21 2018 *)

Formula

Theorem: The partial sums of the generalized version THETA(r,s,t) (see Comments) are given by the following formula: Sum_{i=1..n} THETA(r,s,t)(i) = r*A276796(n-1) + s*A276797(n-1) + t*A276798(n-1). - N. J. A. Sloane, Mar 23 2019