[seqfan] Re: Rewriting squares

[Benoît Jubin]

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