Rote-Fibonacci seq.: like a Kolakoski seq. but based on XOR of terms

[Geoffrey Caveney]

I observe an interesting property of the Rote-Fibonacci sequence (A273129):

0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, ...

It appears that this sequence can be generated in the following way, akin to the Kolakoski sequence (A000002) but with the lengths of the runs based on performing the XOR operation on adjacent terms:

Set a(0) = 0, a(1) = 0, and then determine the lengths of the following runs of 1's and 0's based on these rules:

If a(n-1) = a(n-2), then the length of the n-th run is 1.

If a(n-1) != a(n-2), then the length of the n-th run is 2.

(This is like an XOR operation in that like values generate the smaller value, while different values generate the larger value. Of course "run length 0" makes no sense in a sequence like this, so the run length values must be 1 and 2, rather than 0 and 1 as in traditional binary XOR.)

Examples: The 1st run is a(0) = 0 and a(1) = 0.

a(1) = a(0), so the length of the 2nd run is 1, so a(2) = 1.

a(2) != a(1), so the length of the 3rd run is 2, so a(3) = 0 and a(4) = 0.

a(3) != a(2), so the length of the 4th run is 2, so a(5) = 1 and a(6) = 1.

a(4) = a(3), so the length of the 5th run is 1, so a(7) = 0.

etc.

Checking examples further in the sequence to confirm that this is not just a coincidental phenomenon of the first few terms:

a(18) = a(19), and the length of the 20th run is 1: a(31) = 1, but a(32) = 0.

a(52) = a(53), and the length of the 54th run is 1: a(86) = 1, but a(87) = 0.

a(86) != a(87), and the length of the 88th run is 2: a(141) = 1 and a(142) = 1.

(By the way, term a(142) is an example of the aperiodic nature of the Rote-Fibonacci sequence. It might appear that the sequence has period 55 based on the terms from a(0) to a(141), but this apparent periodicity is broken by a(142) != a(87).)

Geoffrey Caveney

[Jeffrey Shallit]

I think this should follow right away from one of the descriptions of the sequence given in my paper

https://doi.org/10.1016/j.tcs.2016.10.005

in Theorem 1a.  Basically it says that Rote-Fibonacci is given by taking the Fibonacci word 01001010..., changing each 0 to a 2, and then using this as the run lengths of a binary word.

--
You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/seqfan/d5a5c149-6e6e-436c-b470-c726068c1867n%40googlegroups.com.