cp's OEIS Frontend

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

%I A275925 #106 May 16 2022 02:42:28
%S A275925 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,
%T A275925 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,
%U A275925 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
%N A275925 Trajectory of 3 under repeated application of the morphism sigma: 3 -> 3656, 5 -> 365656, 6 -> 3656656.
%C A275925 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
%C A275925 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]
%C A275925 From _Michel Dekking_, Dec 12 2018: (Start)
%C A275925 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
%C A275925       3 -> 6563, 5 -> 656365, 6 -> 6563656.
%C A275925 Let sigma be the morphism generating (a(n)). Then sigma is conjugate to tau^3 with conjugating word u = 656:
%C A275925     (656)^{-1} tau^3(3) 656 = 3656 = sigma(3)
%C A275925     (656)^{-1} tau^3(5) 656 = 365656 = sigma(5)
%C A275925     (656)^{-1} tau^3(6) 656 = 3656656 = sigma(6).
%C A275925 It follows that tau and sigma generate the same language, in particular the frequencies of corresponding letters are equal.
%C A275925 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.
%C A275925 (End)
%C A275925 From _N. J. A. Sloane_, Mar 03 2019: (Start)
%C A275925 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}).
%C A275925 The present sequence is the limit T_oo where
%C A275925 sigma: 3 -> 3656, 5 -> 365656, 6 -> 3656656; T_0 = 3, and T_n = sigma(T_{n-1}).
%C A275925 Conjecture 2: For all k=0,1,2,..., the following two finite words are identical:
%C A275925 S_{3k+2} with 1,2 mapped to 6,5 respectively, and 3 fixed,
%C A275925 T_{k+1} with its initial 3 moved to the end.
%C A275925 Example for k=1:
%C A275925 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,
%C A275925 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,
%C A275925 Note that S_{3k+2} has length A000073(3k+5) and always ends with a 3.
%C A275925 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.
%C A275925 (End)
%C A275925 From _Michel Dekking_, Mar 11 2019: (Start)
%C A275925 Proof of Conjecture 2.
%C A275925 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.
%C A275925 We prove by induction that 3 alpha^n(3) = sigma^n(3) 3.
%C A275925 This is true for n=1: 3 alpha(3) = 3 6563 = sigma(3) 3.
%C A275925 The conjugation observation in my comment from December 12 implies that for all words w from the language of tau:
%C A275925    alpha(w) 656 = 656 sigma(w).
%C A275925 Applying this with the word w = alpha^n(3) yields
%C A275925       3 alpha^{n+1}(3) 656 = 3 656 sigma(alpha^n(3)) =
%C A275925       sigma(3 alpha^n(3)) = sigma(sigma^n(3) 3) =
%C A275925       sigma^{n+1}(3) 3656,
%C A275925 where we used the induction hypothesis in the second line.  Removing the 656's at the end completes the induction step.
%C A275925 (End)
%C A275925 Lengths of runs of 2's in A276788. - _John Keith_, May 15 2022
%H A275925 N. J. A. Sloane, <a href="/A275925/b275925.txt">Table of n, a(n) for n = 1..35890</a>
%H A275925 J.-P. Allouche, M. Baake, J. Cassaigns, and D. Damanik, <a href="http://arxiv.org/abs/math/0106121">Palindrome complexity</a>, arXiv:math/0106121 [math.CO], 2001; <a href="http://dx.doi.org/10.1016/S0304-3975(01)00212-2">Theoretical Computer Science</a>, 292 (2003), 9-31.
%H A275925 F. Michel Dekking, Jeffrey Shallit, and N. J. A. Sloane, <a href="https://www.combinatorics.org/ojs/index.php/eljc/article/view/v27i1p52/8039">Queens in exile: non-attacking queens on infinite chess boards</a>, Electronic J. Combin., 27:1 (2020), #P1.52.
%H A275925 <a href="/index/Fi#FIXEDPOINTS">Index entries for sequences that are fixed points of mappings</a>
%F A275925 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
%e A275925 The first few generations of the iteration are:
%e A275925 3
%e A275925 3656
%e A275925 365636566563656563656656
%e A275925 3656365665636565636566563656365665636565636566563656656365656365665636563656656\
%e A275925    3656563656656365656365665636563656656365656365665636566563656563656656
%e A275925 ...
%t A275925 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 *)
%Y A275925 Cf. A140100, A140101, A273059, A000073.
%Y A275925 See A276790 and A277745 for other versions. See also A276788 and A080843, A092782.
%Y A275925 For partial sums see A305373, also A276796, A276797, A276798.
%K A275925 nonn
%O A275925 1,1
%A A275925 _N. J. A. Sloane_, Aug 29 2016