A269027 - OEIS

%I #103 Aug 15 2022 08:35:39

%S 0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,

%T 0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,1,0,1,0,

%U 0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1

%N Parity of the number of 1's in A039724(n).

%C An analog of Thue-Morse sequence in base -2: a(n) is the parity of number of 1's in the extension of n in negabinary (A039724).

%C Conjecture. Let A_k denote the first 2^k terms; then A_0={0} and for even k>=0, A_(k+1)= A_kB_k, where B_k is obtained from A_k by complementing its 0's and 1's; for odd k>=1, A_(k+1)= A_kC_k, where C_k is obtained from A_k by complementing its last (2/3)*(2^(k-1)-1) 0's and 1's.

%C For example,A_2={0,1,0,1}. Then B_2={1,0,1,0} and A_3={0,1,0,1,1,0,1,0}; further, C_3 is obtained from A_3 complementing its last 2 0's and 1's. So, A_4={0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1}.

%C Theorem. Conjecture is true. - _Vladimir Shevelev_, Feb 20 2016

%C From _Vladimir Shevelev_, Feb 18 2016: (Start)

%C Theorem: The sequence is cubefree.

%C Proof: First note that there are no three consecutive equal terms - this follows from the formula suggested by _Robert Israel_ (see below) which was proved in the Shevelev link.

%C The sequence is cubefree if it does not contain a subsequence of the form XXX. Here we consider only one of several cases (the others are handled in a similar way). Let n==0 (mod 4), s==2 or 3 (mod 4). For example, if s=2, consider XXX with positions (4*k,4*k+1)(4*k+2,4*k+3)(4*k+4,4*k+5).

%C Suppose a(4*k)=a(4*k+2)=a(4*k+4), then a(k)=1-a(k+1)=a(k+1), a contradiction; if s=3, consider XXX with positions (4*k,4*k+1,4*k+2) (4*k+3,4*k+4,4*k+5) (4*k+6,4*k+7,4*k+8). Then a(4*k)=a(4*k+3)=a(4*k+6), a(k)=a(k+1), and a(4*k+1)=a(4*k+4)=a(4*k+7), 1-a(k)=a(k+1)=a(k).

%C   A contradiction. (End)

%C In general for odd s>3, n=4*k, let first s=4*m+1, m>=1, s>=5. Let XXX have positions (4*k,...,4*k+s-1)(4*k+s,...,4*k+2*s-1)(4*k+2*s,...,4*k+3*s-1). Consider in the first X a(4*k+3) and in the second X a(4*k+3+s). Then we should have a(4*k+3)=a(4*k+3+s)=a(4*k+4*m+4) or a(k+1)=a(k+m+1). Now in the first X we consider a(4k+4) and in the second X a(4*k+4+s). Then we should have a(4*k+4)=a(4*k+4+4*m+1) or a(k+1)=1-a(k+m+1). So a(k+m+1)= 1-a(k+m+1), a contradiction. Further, if s=4*m+3, m>=1, s>=7, in the same way we obtain a contradiction, choosing in the first X a(4*k)=a(k) and a(4*k+1)=1-a(k), then comparing with a(4*k+4*m+3)=a(k+m+1) and a(4*k+4*m +4)=a(k+m+1) in the second X we obtain a(k+m+1)=a(k) and a(k+m+1)=1-a(k). A contradiction. - _Vladimir Shevelev_, May 08 2017

%C Finally consider the general case of even s, also demonstrating it for n=4*k. Let first s=4*m+2, m>=1. Then we have the following 4 pairs of equations:

%C   a(4*k+1) = 1-a(k), a(4*k+4*m+3) = a(k+m+1);

%C   a(4*k+2) = 1-a(k+1), a(4*k+4*m+4) = a(k+m+1);

%C   a(4*k+4) = a(k+1), a(4*k+4*m+6) = 1-a(k+m+2);

%C   a(4*k+6) = 1-a(k+2), a(4*k+4*m+8) = a(k+m+2).

%C From the first two pairs we find a(k)=a(k+1). From the last two pars we find a(k+1)=a(k+2). So a(k)=a(k+1)=a(k+2), a contradiction. Analogously we prove the considered cases of s when n==1,2,3 (mod 4). The case s = 4*m now is proved easily by a simple induction (in more detail see in [shevelev] link, Section 7, - _Vladimir Shevelev_, May 11 2017

%C Note that the sequence has two additional common properties with the Thue-Morse sequence (cf. [Offner] link). 1) In the [Shevelev] link we show that a(2*n)=1-a(2*n+1). Thus if a(n)= a(n+1), then n should be odd. 2) Show also that in any 5 consecutive terms there must be 2 consecutive equal terms. Indeed, in other cases we should have either consecutive terms 10101 or 01010. Consider the case that the first term has position 4*k (other cases can be dealt with in the same way). Then in the first case we should have a(4*k) =a(k)=1, ... , a(4*k+3)=a(k+1)=0, a(4*k+4)= a(k+1)=1, a contradiction (and the same contradiction for the second case). - _Vladimir Shevelev_, May 14 2017

%C Consider the constant G=0.0101101001011..._2 which is obtained by the concatenated terms {a(n)} and interpreted as a binary real number G. Theorem. G is transcendental number. A proof one is given in the [shevelev] link, Section 9. - _Vladimir Shevelev_, May 24 2017

%C If W(n) is the infinite word formed from the terms {a(n)} and M is the morphism {0 -> 1001, 1 -> 0110} then M(W(n)) = 10|W(n). - _Charlie Neder_, Jun 10 2019

%H Peter J. C. Moses, <a href="/A269027/b269027.txt">Table of n, a(n) for n = 0..2047</a>

%H C. D. Offner, <a href="http://www.rw.cdl.uni-saarland.de/~joba/Info3/material/quadratfrei.pdf">Repetitions of Words and the Thue-Morse sequence</a>.

%H Jeffrey Shallit, Sonja Linghui Shan, and Kai Hsiang Yang, <a href="https://arxiv.org/abs/2208.06025">Automatic Sequences in Negative Bases and Proofs of Some Conjectures of Shevelev</a>, arXiv:2208.06025 [cs.FL], 2022.

%H Vladimir Shevelev, <a href="http://arxiv.org/abs/1603.04434">Two analogs of Thue-Morse sequence</a>, arXiv:1603.04434 [math.NT], 2016.

%H Eric Weisstein, <a href="http://mathworld.wolfram.com/Negabinary.html">Negabinary</a> (MathWorld)

%F The conjecture in the comment is equivalent to the following formula: for odd k>=1 and 0 <= m < 2^k - (2/3)*(2^(k-1)-1), a(m+2^k)=a(m);

%F while if 2^k - (2/3)*(2^(k-1)-1) <=m < 2^k,

%F a(m+2^k)=1-a(m); for even k>=2 and 2^(k-1) <= m < 2^k, a(m+2^k) = 1-a(m).

%F From _Robert Israel_, Feb 24 2016: (Start)

%F a(4k) = a(k).

%F a(4k+1) = 1 - a(k).

%F a(4k+2) = 1 - a(k+1).

%F a(4k+3) = a(k+1).

%F G.f. g(x) satisfies g(x) = x/(1-x+x^2-x^3)-(1-x-x^2+x^3)*g(x^4)/x^2. (End)

%F a(n) = A268643(A039724(n)) mod 2 = A000035(A268643(A039724(n))). - _Robert Israel_, Feb 28 2016

%p f:= proc(n) option remember; local r;

%p r:= round(n/4);

%p if (n-4*r) mod 3 = 1 then 1-procname(r) else procname(r) fi

%p end proc:

%p f(0):= 0:

%p seq(f(i),i=0..100); # _Robert Israel_, Feb 24 2016

%t With[{b = 2}, Table[Boole@ OddQ@ # &@ Count[Rest@ Reverse@ Mod[#, b] &@ NestWhileList[(# - Mod[#, b])/-b &, n, # != 0 &], 1], {n, 0, 106}]] (* _Michael De Vlieger_, May 08 2017 *)

%Y Cf. A000035, A010060, A039724, A268411(quint-free sequence), A268643, A268865, A268866, A269003.

%Y Cf. A268272 (positions of 0s), A268273 (positions of 1s).

%K nonn,base

%O 0

%A _Vladimir Shevelev_, Feb 18 2016

%E More terms from _Peter J. C. Moses_, Feb 18 2016