Squares on my immediate left


Hello Math freaks & friends,
I was reading yesterday the "Stringology" chapter in « Automatic Sequences » (the wonderful book by Allouche and Shallit, 2003) when I bumped into this quote (which made my day): « Note that the word square is squarefree while the word squarefree is not ».

... and I thought: what if a(n) describes the number of such squares immediately to its left? The models were those two sequences, already in the OEIS (merci à Maximilian F. Hasler !-)

https://oeis.org/A248034 
[a(n+1) gives the number of occurrences of the last digit of a(n) so far, up to and including a(n), with a(0)=0.]

and

https://oeis.org/A329447 
[Look left and tell the least frequent: after a(0) = 0, a(n) = 10c + d, where c > 0 is the number of times the least frequent digit d has appeared so far; smallest d in case of tie].
_______________
Ok, I'll have a try now — please be indulgent as this is a nightmare to compute with coffee, paper and pencil only. "Square" must be intended here as a "square word", not as a square number; the string 1212 shows one such square – the square formed by the two substrings "12";

S = 0, ...

Yes, we start with a(1) = 0 as this 0 means: "I don't see any square on my immediate left";

S = 0,0, ...

We extend S with a(2) = 0 as this 0 says the same as above: "I don't see any square on my immediate left". Note that no other integer would fit without contradiction [a(2) = 1, for instance, would say that there is one square on the immediate left of "1", which is not the case – a lonely symbol cannot form a square]. 
As we now see the square {00}, S is extended with a(3) = 1

S = 0,0,1, ...

No square in sight, we thus extend S with a(4) = 0 [the word "immediate" is important – we see why: "There is no square on the immediate left of a(4) = 0"];

S = 0,0,1,0, ...

No visible square again, so a(5) = 0;

S = 0,0,1,0,0, ...

We see here that a(6) must be 1, as this "1" is immediately preceeded by the single square {00}

S = 0,0,1,0,0,1, ...

And yes, a(7) = 1 hereunder, because a(7) sees 1 square on its immediate left, which is formed by {001,001};

S = 0,0,1,0,0,1,1, ...

Ah, ah, we see a third symbol entering S hereunder – this is"2"! The reason is that 2 sees two squares on its immediate left, the first one being {11} and the second one {00} (again, the remote square {oo} that opens S is not "immediately" to the left of 2, so we don't count it);

S = 0,0,1,0,0,1,1,2, ...

We go on like above now (the last square being in bold blue – and sometimes a portion of that square is underlined):
S = 0,0,1,0,0,1,1,2,0, ...
S = 0,0,1,0,0,1,1,2,0,0, ...
S = 0,0,1,0,0,1,1,2,0,0,1, ...
S = 0,0,1,0,0,1,1,2,0,0,1,0, ...
S = 0,0,1,0,0,1,1,2,0,0,1,0,0, ...
S = 0,0,1,0,0,1,1,2,0,0,1,0,0,1, ...
S = 0,0,1,0,0,1,1,2,0,0,1,0,0,1,1, ...
S = 0,0,1,0,0,1,1,2,0,0,1,0,0,1,1,2, ...
S = 0,0,1,0,0,1,1,2,0,0,1,0,0,1,1,2,1, ...
S = 0,0,1,0,0,1,1,2,0,0,1,0,0,1,1,2,1,0, ...
S = 0,0,1,0,0,1,1,2,0,0,1,0,0,1,1,2,1,0,0, ...
S = 0,0,1,0,0,1,1,2,0,0,1,0,0,1,1,2,1,0,0,1, ...
S = 0,0,1,0,0,1,1,2,0,0,1,0,0,1,1,2,1,0,0,1,0, ...
S = 0,0,1,0,0,1,1,2,0,0,1,0,0,1,1,2,1,0,0,1,0,0, ...
S = 0,0,1,0,0,1,1,2,0,0,1,0,0,1,1,2,1,0,0,1,0,0,2, ...
S = 0,0,1,0,0,1,1,2,0,0,1,0,0,1,1,2,1,0,0,1,0,0,2,0, ...
S = 0,0,1,0,0,1,1,2,0,0,1,0,0,1,1,2,1,0,0,1,0,0,2,0,0, ...
S = 0,0,1,0,0,1,1,2,0,0,1,0,0,1,1,2,1,0,0,1,0,0,2,0,0,1, ...

[...]
We jump now to the first symbol "3":
S = 0,0,1,0,0,1,1,2,0,0,1,0,0,1,1,2,1,0,0,1,0,0,2,0,0,1,0,0,1,1,2,0,0,1,0,0,1,1,3, ...
Etc.
Is this interesting for the OEIS? Would someone give it a try with a computer? I would be glad to add a graph...
Best,
É.
____________________
Update Nov 26th
My friend Jean-Marc Falcoz raises a few interesting questions:
1) What is the value of X if we encounter the segment 1,1,1,X?
ANSWER: X=0 because 1,1,1 is a cube – and we count only squares. We don't consider that we have a square inside the cube.
2) What is the value of X if we encounter the segment 1,0,1,0,1,0,1,0,X?
ANSWER: X = 0 because 1,0,1,0,1,0,1,0 is a power^4 – and we count only squaresWe don't consider that a power^4 can be split in two squares.

I've just received a 10,000-term b-file from Jean-Marc – witch I will use to submit the sequence to the OEIS soon. Here is the draft of my submission:

Name
a(n) counts the square-words immediately before a(n), with a(1) = 0.
Data
0,0,1,0,0,1,1,2,0,0,1,0,0,1,1,2,1,0,0,1,0,0,2,0,0,1,0,0,1,1,2,0,0,1,0,0,1,1,3,0,0,1,0,0,1,1,2,0,0,1,0,0,1,1,2,1,0,0,1,0,0,2,0,0,1,0,0,1,1,2,0,0,1,0,0,1,1,3,1,0,0,1,0,0,2,0,0,1,0,0,1,1,2,0,0,1,0,0,1,1,3,1,1,1,0,0,1,0,0,2,0,0,1,0,0,1,1,2,0,0,1,0,0,1,1,3,0,0,1,0,0,1,1,2,0,0,1,0,0,1,1,2,1,0,0,1,0,0,2,0,0,1,0,0,1,1,2,0,0,1,0,0,1,1,3,0,0,1,0,0,1,1,2,0,0,1,0,0,1,1,2,2,3,0,0,1,0,0,1,1,2,0,0,1,0,0,1,1,2,1,0,0,1,0,0,2,0,0,1,0,0,1,1,2,0,0,1,0,0,1,1,3,0,0,1,0,0,1,1,2,0,0,1,0,0,1,1,2,1,0,0,1,0,0,2,0,0,1,0,0,1,1,2,0,0,1,0,0,1,1,4,0,0,1,0,0,1,1,2,0,...
Comment
Every integer will appear in the sequence – but at a very slow pace: after 10000 terms, the biggest one is 5.
Only the square-words are counted, not the cubes or the higher powers. The segment 1,1,1 will thus be followed by 0, and the same 0 will follow the segment 0,1,0,1,0,1,0,1 (because the pattern 0,1 is present four times instead of the required two; we don’t accept to split 0,1,0,1,0,1,0,1 to form two 0,1,0,1 substrings).

Overlaps are admitted: a typical case is the start with a(1) = 1. This produces 1,0,0,1,0,0,2,… and a(7) = 2 because there are indeed two squares immediately to the left of a(7): the square {0,0} and the square {100,100}. 

The same idea will be developped for cubes and palindromes in the coming days.

P.-S. nov 28th 2019
The palindromes idea does not work, unfortunately. Cubes are  now in the OEIS here.

[Opening and closing images: Bridget Riley]


















Commentaires

Posts les plus consultés de ce blog

A square for three (chess)

Le tripalin se présente

Some strings au cinéma Galeries