OFFSET
0
COMMENTS
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).
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.
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}.
Theorem. Conjecture is true. - Vladimir Shevelev, Feb 20 2016
From Vladimir Shevelev, Feb 18 2016: (Start)
Theorem: The sequence is cubefree.
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.
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).
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).
A contradiction. (End)
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
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:
a(4*k+1) = 1-a(k), a(4*k+4*m+3) = a(k+m+1);
a(4*k+2) = 1-a(k+1), a(4*k+4*m+4) = a(k+m+1);
a(4*k+4) = a(k+1), a(4*k+4*m+6) = 1-a(k+m+2);
a(4*k+6) = 1-a(k+2), a(4*k+4*m+8) = a(k+m+2).
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
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
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
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
LINKS
Peter J. C. Moses, Table of n, a(n) for n = 0..2047
C. D. Offner, Repetitions of Words and the Thue-Morse sequence.
Jeffrey Shallit, Sonja Linghui Shan, and Kai Hsiang Yang, Automatic Sequences in Negative Bases and Proofs of Some Conjectures of Shevelev, arXiv:2208.06025 [cs.FL], 2022.
Vladimir Shevelev, Two analogs of Thue-Morse sequence, arXiv:1603.04434 [math.NT], 2016.
Eric Weisstein, Negabinary (MathWorld)
FORMULA
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);
while if 2^k - (2/3)*(2^(k-1)-1) <=m < 2^k,
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).
From Robert Israel, Feb 24 2016: (Start)
a(4k) = a(k).
a(4k+1) = 1 - a(k).
a(4k+2) = 1 - a(k+1).
a(4k+3) = a(k+1).
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)
MAPLE
f:= proc(n) option remember; local r;
r:= round(n/4);
if (n-4*r) mod 3 = 1 then 1-procname(r) else procname(r) fi
end proc:
f(0):= 0:
seq(f(i), i=0..100); # Robert Israel, Feb 24 2016
MATHEMATICA
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 *)
CROSSREFS
KEYWORD
nonn,base
AUTHOR
Vladimir Shevelev, Feb 18 2016
EXTENSIONS
More terms from Peter J. C. Moses, Feb 18 2016
STATUS
approved