[seqfan] Re: Rewriting squares

[jean-paul allouche]

Dear Benoît

You are right: taking squares does not seem to be special, in that
there is just a concatenation of words entering the picture. The whole
kind of stuff is part of "combinatorics on words". Keywords are "morphisms"
(or sometimes "substitutions"), with a snobbish variation: "morphism of the
free monoid".

best
jp

Le 17/05/2019 à 15:31, Benoît Jubin a écrit :
> It could be illuminating to look at what happens in smaller bases.  Modulo
> possible mistakes, it looks like the fixed points (which are finite or
> infinite sequences) that are reached by starting from one-digit numbers are:
> base 2: [1]
> base 3: [1], [1,1]
> base 4: [1], [0, 1], [1, 0, 1]
> base 5: [1], [1, 1, 1, ...]
> base 6: [1], [3, 1, 1, ...], [4, 2, 4, 4 ...], [1 prepended to the previous
> sequence]
> This only nontrivial sequence so far is better looked at as a sequence of
> symbols generated by the rules {A -> B, B -> BA}. It is Fibonacci-like, so
> it is aperiodic and the proportion of B's is (sqrt(5)-1)/2. This answers M.
> Hasler's questions in this simplest case.
> base 7: when starting from a one-digit number, no fixed point is reached
> (note that like in other bases, there are many fixed points, like any
> finite or infinite sequence consisting of only 0's and 1's; they are simply
> not reached starting from one-digit numbers).
> base 8: [1], [1, 1], [1, 1, 1], [0, 0, 0 ...], [1, 0, 0, ...]
> base 9: [1], [0, 1]
>
> Note that for bases 7 and 9, there are things like "attracting orbits" with
> two elements; for base 7: { [2, 2, 2 ...], [4, 4, 4 ...] } and for base 9:
> { [4, 5, 1, 4, 5, 4...], [7, 1, 7, 2, 1, 7... ] } and variants with 1
> prepended.
>
> I think there is nothing special about taking squares; it's only sequences
> generated by rules for symbol substitution/rewriting. There is probably a
> general theory for that (I know basically nothing about combinatorics),
> though I'm not sure what kind of general results can be obtained.
>
> Benoît
>
>
>
>
>
>
> On Thu, May 16, 2019 at 10:26 PM jean-paul allouche <
> jean-paul.allouche at imj-prg.fr> wrote:
>
>> Right!
>> Thanks for this point
>>
>> best
>> jean-paul
>>
>> Le 16/05/2019 à 21:35, Neil Sloane a écrit :
>>>> or with 6 (639181...). This last sequence might be worth adding.
>>> Me: I think it is enough just to have A308170 and -1
>>>
>>> Best regards
>>> Neil
>>>
>>> Neil J. A. Sloane, President, OEIS Foundation.
>>> 11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
>>> Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
>>> Phone: 732 828 6098; home page: http://NeilSloane.com
>>> Email: njasloane at gmail.com
>>>
>>>
>>>
>>> On Thu, May 16, 2019 at 1:54 PM jean-paul allouche <
>>> jean-paul.allouche at imj-prg.fr> wrote:
>>>
>>>> Dear Maximilian
>>>>
>>>> I think that the morphism in A308171
>>>> is not quite correct: the image of 9 should be 18
>>>> and the image of 8 should be 46. This is the same
>>>> morphism as for A308170. This morphism has
>>>> three infinite fixed points respectively beginning
>>>> with 1 (A308170), or with 5 (A308171) or with 6
>>>> (639181...). This last sequence might be worth adding.
>>>>
>>>> best wishes
>>>> jean-paul
>>>>
>>>>
>>>>
>>>> Le 16/05/2019 à 01:11, M. F. Hasler a écrit :
>>>>> On Sun, May 12, 2019 at 12:08 PM jean-paul allouche wrote:
>>>>>
>>>>>> By the definition itself, the infinite sequence is obtained by
>>>> iterating a
>>>>>> morphism
>>>>>> (in the usual sens in combinatorics on words). For example, starting
>>>> with 6
>>>>>> is exactly iterating the morphism
>>>>>> 6 --> 63
>>>>>> 3 --> 9
>>>>>> 9 --> 18
>>>>>> 8 --> 46
>>>>>> 1 --> 1
>>>>>> 4 --> 61
>>>>>> which gives 6 --> 63 --> 639 --> 63918 --> 63918146...
>>>>>>
>>>>> Indeed! In particular,
>>>>> the digit 7 (surprisingly chosen as initial value, rather than 3 or 9)
>>>> will
>>>>> never occur.
>>>>> Similarly, when starting with 5 (A308171), we have to amend the above
>>>> with
>>>>> 5 -> 52 ; 2 -> 4
>>>>> but the digits (5,2) = A308171(1..2) will never occur elsewhere again.
>>>>>
>>>>> Can it be proved or disproved that we can have A308170(n) =
>> A308171(n+k)
>>>>> for some k and all n sufficiently large?
>>>>> What can be said / proved about the respective densities and /or
>>>> positions
>>>>> - of the digits that occur infinitely often ?
>>>>> - where finite subsequence a(m..n), n>m>2, will occur again in the
>>>> sequence?
>>>>> The sequence clearly is not squarefree (we have the cube 1, 6, 3, 1, 6,
>>>> 3,
>>>>> 1, 6, 3 quite early)
>>>>> but can one make some other statement concerning squares, cubes... of
>>>> given
>>>>> / minimal length ?
>>>>>
>>>>> On 12/05/2019 à 14:22, Neil Sloane wrote:
>>>>>>> It is certainly interesting.  We should have the two limiting
>> sequences
>>>>>> in the OEIS:
>>>>>>
>> 6,3,9,1,8,1,4,6,1,6,1,6,3,1,6,3,1,6,3,9,1,6,3,9,1,6,3,9,1,8,1,6,3,9,1,8,1,6,
>>>>>>> 3,9,1,8,1,4,6,1,6,3,9,1,8,1,4,6,1,6,3,9,1,8, ... ===> now  A308170
>>>>>>> or in the case of 25,
>>>>>>>
>> 5,2,4,6,1,6,3,1,6,3,9,1,6,3,9,1,8,1,6,3,9,1,8,1,4,6,1,6,3,9,1,8,1,4,6,1,6,1,
>>>>>>> 6,3,1,6,3,9,1,8,1,4,6,1,6,1,6,3,1,6,3,1,6,3, ... ===> now A308171
>>>>>>> Also the number of steps to reach the limit cycle when starting from
>> n,
>>>>> It's unclear to me what could mean to "reach a limit cycle".
>>>>> Up to where the sequence(word) must coincide with the limit (which is
>>>> never
>>>>> reached, except for the fixed point "1") ?
>>>>> Just the initial character? (This wouldn't be much interesting IMHO.)
>>>>> --
>>>>> Maximilian
>>>>>
>>>>> --
>>>>> Seqfan Mailing list - http://list.seqfan.eu/
>>>> --
>>>> Seqfan Mailing list - http://list.seqfan.eu/
>>>>
>>> --
>>> Seqfan Mailing list - http://list.seqfan.eu/
>>
>> --
>> Seqfan Mailing list - http://list.seqfan.eu/
>>
> --
> Seqfan Mailing list - http://list.seqfan.eu/