cp's OEIS Frontend

Let u = A000201 = (lower Wythoff sequence) and v = A001950 = (upper Wythoff sequence). Conjecture: This sequence is the sequence p given by p(1) = 0 and p(u(k)) = p(k); p(v(k)) = 1-p(k). - Clark Kimberling, Apr 15 2011

[base 2] 0.111010010001100... = 0.9105334708635617... - Joerg Arndt, May 13 2011

From Michel Dekking, Nov 28 2019: (Start)

This sequence is a morphic sequence.

Let the morphism sigma be given by

sigma(1) = 12, sigma(2) = 4, sigma(3) = 1, sigma(4) = 43,

and let the letter-to-letter map lambda be given by

lambda(1) = 0, lambda(2) = 1, lambda(3) = 0, lambda(4) = 1.

Then a(n) = lambda(x(n)), where x(0)x(1)... = 1244343... is the fixed point of sigma starting with 1.

See footnote number 4 in the paper by Emmanuel Ferrand. (End)

From Michel Dekking, Nov 29 2019: (Start)

Proof of Kimberling's conjecture, by virtue of the four symbol morphism sigma in the previous comment.

We first show that the fixed point x = 1244343143112... of sigma has the remarkable property that the letters 1 and 4 exclusively occur at positions u(k), k=1,2,..., and the letters 2 and 3 exclusively occur at positions v(k) k=1,2,....

To see this, let alpha be the Fibonacci morphism on the alphabet {a,b}:

alpha(a) = ab, alpha(b) = a.

It is well known that the lower Wythoff sequence u gives the positions of a in the fixed point abaababaab... of alpha, and that the upper Wythoff sequence v gives the positions of b in this infinite Fibonacci word.

Let pi be the projection from {1,2,3,4} to {a,b} given by

pi(1) = pi(4) = a, pi(2) = pi(3) = b.

One easily checks that (composition of morphisms)

pi sigma = alpha pi.

This implies the remarkable property stated above.

What remains to be proved is that lambda(x(u(k)) = a(k) and lambda(x(v(k)) = a(k), where lambda is the letter-to-letter map in the previous comment. We tackle this problem by an extensive analysis of the return words of the letter 1 in the sequence x= 1244343143112...

These are the words occurring in x which start with 1 and have no other occurrences of 1 in them.

One easily finds that they are given by

A:=1, B:=12, C:=124, D:=143, E:=1243, F:=12443, G:=1244343.

These words partition x. Moreover, sigma induces a morphism rho on the alphabet {A,B,C,D,E,F,G} given by

rho(A) = B, rho(B) =C, rho(C) = F, rho(D) = EA,

rho(E) = FA, rho(F) = GA, rho(G) = GDA.

CLAIM 1: Let mu be the letter-to-letter map given by

mu(A)=mu(B) = 1, mu(C)=mu(D)=mu(E) = 2, mu(F) = 3, mu(G) = 4,

then mu(R) = (s(n+1)-s(n)), where R = GDAEABFAB... is the unique fixed point of rho and s = 1,5,7,8,10,... is the sequence of positions of 1 in (x(u(k)).

Proof of CLAIM 1: The 1's in x occur exclusively at positions u(k), so if we want the differences s(n+1)-s(n), we can strip the 2's and 3's from the return words of 1, and record how long it takes to the next 1. This is the length of the stripped words A~=1, B~=1, C~=14, ... which is given by mu.

CLAIM 2: Let delta be the 'decoration' morphism given by

delta(A) = 1, delta(B) = 2, delta(C) = 3, delta(D) = 21,

delta(E) = 31, delta(F) = 41, delta(G) = 421,

then delta(R) = (t(n+1-t(n)), where rho(R) = R, and t is the sequence of positions of 1 or 3 in the sequence x = 1244343143112....

Proof of CLAIM 2: We have to record the differences in the occurrences of 1 and 3 in the return words of 1. These are given by delta. For example: F = 12443, where 1 and 3 occur at position 1 and 5; and the next 1 will occur at the beginning of any of the seven words A,...,G.

If we combine CLAIM 1 and CLAIM 2 with lambda(1) = lambda(3) = 0, we obtain the first half of Kimberling's conjecture, simply because delta = mu rho, and rho(R) = R.

The second half of the conjecture is obtained in a similar way. (End)

From Michel Dekking, Mar 10 2020: (Start)

The fact that this sequence is a morphic sequence can be easily deduced from the morphism tau given in A007895:

tau((j,0)) = (j,0) (j+1,1),

tau((j,1)) = (j,0).

The sum of digits of a number n in Zeckendorf expansion is given by projecting the n-th letter in the fixed point of tau starting with (0,0) on its first coordinate: (j,i)->j for i=0,1.

If we consider all the j's modulo 2, we obtain a morphism sigma' on 4 letters:

sigma'((0,0)) = (0,0) (1,1),

sigma'((0,1)) = (0,0),

sigma'((1,0)) = (1,0)(0,1),

sigma'((1,1)) = (1,0).

The change of alphabet (0,0)->1, (0,1)->3, (1,0)->4, (1,1)->2, turns sigma' into sigma given in my Nov 28, 2019 comment. The projection map turns into the map 1->0, 2->1, 3->0, 4->1, as in my Nov 28 2019 comment.

(End)

Another proof that this sequence is a morphic sequence has been given in the monograph by Allouche and Shallit. They demonstrate on page 239 that (a(n)) is a letter to letter projection of a fixed point of a morphism on an alphabet of six letters. However, it can be seen easily that two pairs of letters can be merged, yielding a morphism on an alphabet of four letters, which after a change of alphabet equals the morphism from my previous comments. - Michel Dekking, Jun 25 2020

From Michel Dekking, Oct 09 2020: (Start)

Let s_Z = A095076 be the parity of the sum of digits function of the Zeckendorf representation. Shutov's main result is that the number of times that s_Z(k) mod 2 = 0 AND s_Z(k+1) mod 2 = 0 in [0,n] divided by n tends to sqrt(5)/10.

It is possible to derive this result in a few lines by using the representation of s_Z as a morphic sequence, as given in the Comments of A095076.

To this end one considers the 2-block substitution sigma^[2] of the Zeckendorf morphism

sigma: 1->12, 2->4, 3->1, 4->43.

There are 10 words of length 2 occurring in the fixed points of this morphism. These are 11, 12, 14, 21, 24, 31, 34, 41, 43 and 44. Since the sigma^[2]-images of both 12 and 14 are 12,24, and this is also the case for the pair 41 and 43, one can reduce the number of letters to 8.

Coding the words of length 2 in lexicographic order this gives sigma^[2] on the alphabet {1,2,...,7,8} as

sigma^[2]: 1->23, 2->24, 3->7, 4->8, 5->1, 6->2, 7->75, 8->76.

The letter-to-letter map lambda mapping the fixed point of sigma^[2] to the sequence s_Z = A095076 is given by lambda(1)=0, lambda(2)=1, lambda(3)=0, lambda(4)=1 (see A095076).

We see that lambda(11) = lambda(31) = 00, and these are the only words of length 2 mapping to 00. It follows that the frequency of 00 in s_Z is equal to the sum of the frequencies of 1 and 5 in the fixed point starting with 2 of the morphism sigma^[2]. It is well known that these frequencies are given by the normalized eigenvector corresponding to the Perron-Frobenius eigenvalue of the incidence matrix of the morphism sigma^[2].

An eigenvalue calculation then gives the value sqrt(5)/10 from above.

Final remark: the same result has been derived for the base-phi expansion of the natural numbers, and the limit is the same.

(End)