cp's OEIS Frontend

A095076 Parity of 1-fibits in Zeckendorf expansion A014417(n).

%I A095076 #93 May 23 2025 01:09:10
%S A095076 0,1,1,1,0,1,0,0,1,0,0,0,1,1,0,0,0,1,0,1,1,1,0,0,0,1,0,1,1,0,1,1,1,0,
%T A095076 1,0,0,0,1,0,1,1,0,1,1,1,0,0,1,1,1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,1,1,0,
%U A095076 0,1,1,1,0,1,0,0,0,1,1,1,0,1,0,0,1,0,0,0,1,1,0,0,0,1,0,1,1,0,1,1,1,0
%N A095076 Parity of 1-fibits in Zeckendorf expansion A014417(n).
%C A095076 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
%C A095076 [base 2] 0.111010010001100... = 0.9105334708635617... - _Joerg Arndt_, May 13 2011
%C A095076 From _Michel Dekking_, Nov 28 2019: (Start)
%C A095076 This sequence is a morphic sequence.
%C A095076 Let the morphism sigma be given by
%C A095076       sigma(1) = 12, sigma(2) = 4, sigma(3) = 1, sigma(4) = 43,
%C A095076 and let the letter-to-letter map lambda be given by
%C A095076       lambda(1) = 0, lambda(2) = 1, lambda(3) = 0, lambda(4) = 1.
%C A095076 Then a(n) = lambda(x(n)), where x(0)x(1)... = 1244343... is the fixed point of sigma starting with 1.
%C A095076 See footnote number 4 in the paper by Emmanuel Ferrand. (End)
%C A095076 From _Michel Dekking_, Nov 29 2019: (Start)
%C A095076 Proof of Kimberling's conjecture, by virtue of the four symbol morphism sigma in the previous comment.
%C A095076 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,....
%C A095076 To see this, let alpha be the Fibonacci morphism on the alphabet {a,b}:
%C A095076       alpha(a) = ab, alpha(b) = a.
%C A095076 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.
%C A095076 Let pi be the projection from {1,2,3,4} to {a,b} given by
%C A095076       pi(1) = pi(4) = a,    pi(2) = pi(3) = b.
%C A095076 One easily checks that  (composition of morphisms)
%C A095076       pi sigma = alpha pi.
%C A095076 This implies the remarkable property stated above.
%C A095076 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...
%C A095076 These are the words occurring in x which start with 1 and have no other occurrences of 1 in them.
%C A095076 One easily finds that they are given by
%C A095076       A:=1, B:=12, C:=124, D:=143, E:=1243, F:=12443, G:=1244343.
%C A095076 These words partition x. Moreover, sigma induces a morphism rho on the alphabet {A,B,C,D,E,F,G} given by
%C A095076       rho(A) = B, rho(B) =C, rho(C) = F, rho(D) = EA,
%C A095076       rho(E) = FA, rho(F) = GA, rho(G) = GDA.
%C A095076 CLAIM 1: Let mu be the letter-to-letter map given by
%C A095076       mu(A)=mu(B) = 1, mu(C)=mu(D)=mu(E) = 2, mu(F) = 3,  mu(G) = 4,
%C A095076 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)).
%C A095076 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.
%C A095076 CLAIM 2: Let delta be the 'decoration' morphism given by
%C A095076     delta(A) = 1,  delta(B) = 2, delta(C) = 3,  delta(D) = 21,
%C A095076       delta(E) = 31, delta(F) = 41,  delta(G) = 421,
%C A095076 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....
%C A095076 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.
%C A095076 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.
%C A095076 The second half of the conjecture is obtained in a similar way. (End)
%C A095076 From _Michel Dekking_, Mar 10 2020: (Start)
%C A095076 The fact that this sequence is a morphic sequence can be easily deduced from the morphism tau given in A007895:
%C A095076       tau((j,0)) = (j,0) (j+1,1),
%C A095076       tau((j,1)) = (j,0).
%C A095076 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.
%C A095076 If we consider all the j's modulo 2, we obtain a morphism sigma' on 4 letters:
%C A095076       sigma'((0,0)) = (0,0) (1,1),
%C A095076       sigma'((0,1)) = (0,0),
%C A095076       sigma'((1,0)) = (1,0)(0,1),
%C A095076       sigma'((1,1)) = (1,0).
%C A095076 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.
%C A095076 (End)
%C A095076 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
%D A095076 Jean-Paul Allouche and Jeffrey Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, Examples 7.8.2 and 7.8.4.
%H A095076 Amiram Eldar, <a href="/A095076/b095076.txt">Table of n, a(n) for n = 0..10000</a>
%H A095076 Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, section 38.11.1, pp. 754-756
%H A095076 Emmanuel Ferrand, <a href="https://doi.org/10.37236/948">An analogue of the Thue-Morse sequence</a>, The Electronic Journal of Combinatorics, Volume 14 (2007), R30.
%H A095076 Pierre Popoli and Manon Stipulanti, <a href="https://arxiv.org/abs/2408.14059">On the pseudorandomness of Parry-Bertrand automatic sequences</a>, arXiv:2408.14059 [math.CO], 2024. See p. 6.
%H A095076 Leonard Rozendaal, <a href="https://hal.archives-ouvertes.fr/hal-01552281">Pisano word, tesselation, plane-filling fractal</a>, Preprint, hal-01552281, 2017.
%H A095076 Jeffrey Shallit, <a href="https://doi.org/10.1016/j.indag.2021.03.004">Subword complexity of the Fibonacci-Thue-Morse sequence: The proof of Dekking's conjecture</a>, Indagationes Mathematicae, Vol. 32, No. 3 (2021), pp. 729-735; <a href="https://arxiv.org/abs/2010.10956">arXiv preprint</a>, arXiv:2010.10956 [cs.DM], 2020.
%H A095076 Jeffrey Shallit, <a href="https://arxiv.org/abs/2203.10504">Note on a Fibonacci Parity Sequence</a>, arXiv:2203.10504 [cs.FL], 2022.
%H A095076 <a href="/index/Ch#char_fns">Index entries for characteristic functions</a>.
%F A095076 a(n) = A010060(A003714(n)).
%F A095076 a(n) = 1 - A095111(n).
%F A095076 a(n) = A007895(n) mod 2. - _Michel Dekking_, Mar 10 2020
%p A095076 A095076 := proc(n)
%p A095076     modp(A007895(n),2) ;
%p A095076 end proc:
%p A095076 seq(A095076(n),n=0..40) ; # _R. J. Mathar_, Sep 22 2020
%t A095076 r=(1+5^(1/2))/2; u[n_] := Floor[n*r];  (* A000201 *)
%t A095076 a[1] = 0; h = 128;
%t A095076 c = (u[#1] &) /@ Range[2h];
%t A095076 d = (Complement[Range[Max[#1]], #1] &)[c]; (* A001950 *)
%t A095076 Table[a[d[[n]]] = 1 - a[n], {n, 1, h - 1}];
%t A095076 Table[a[c[[n]]] = a[n], {n, 1, h}] (* A095076 conjectured *)
%t A095076 Flatten[Position[%, 0]]  (* A189034 *)
%t A095076 Flatten[Position[%%, 1]] (* A189035 *)
%t A095076 Mod[DigitCount[Select[Range[0, 540], BitAnd[#, 2 #] == 0 &], 2, 1], 2] (* _Amiram Eldar_, Feb 05 2023 *)
%o A095076 (Python)
%o A095076 def ok(n): return True if n==0 else n*(2*n & n == 0)
%o A095076 print([bin(n)[2:].count("1")%2 for n in range(1001) if ok(n)]) # _Indranil Ghosh_, Jun 08 2017
%Y A095076 Characteristic function of A020899.
%Y A095076 Run counts are given by A095276.
%Y A095076 Cf. A003714, A007895, A010060, A095111, A189034, A189035 (positions of 0 and 1 if the conjecture is valid).
%K A095076 nonn
%O A095076 0,1
%A A095076 _Antti Karttunen_, Jun 01 2004