

A269027


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


8



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, 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, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0


COMMENTS

An analog of ThueMorse 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^(k1)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)=1a(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), 1a(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+s1)(4*k+s,...,4*k+2*s1)(4*k+2*s,...,4*k+3*s1). 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)=1a(k+m+1). So a(k+m+1)= 1a(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)=1a(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)=1a(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) = 1a(k), a(4*k+4*m+3) = a(k+m+1);
a(4*k+2) = 1a(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) = 1a(k+m+2);
a(4*k+6) = 1a(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 ThueMorse sequence (cf. [Offner] link). 1) In the [Shevelev] link we show that a(2*n)=1a(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)) = 10W(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 ThueMorse sequence.
Vladimir Shevelev, Two analogs of ThueMorse 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^(k1)1), a(m+2^k)=a(m);
while if 2^k  (2/3)*(2^(k1)1) <=m < 2^k,
a(m+2^k)=1a(m); for even k>=2 and 2^(k1) <= m < 2^k, a(m+2^k) = 1a(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/(1x+x^2x^3)(1xx^2+x^3)*g(x^4)/x^2. (End)
a(n) = A268643(A039724(n)) mod 2 = A000035(A268643(A039724(n))).  Robert Israel, Feb 28 2016


MAPLE

f:= proc(n) option remember; local r;
r:= round(n/4);
if (n4*r) mod 3 = 1 then 1procname(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

Cf. A000035, A010060, A039724, A268411(quintfree sequence), A268643, A268865, A268866, A269003.
Sequence in context: A291291 A324681 A285249 * A089809 A165211 A188027
Adjacent sequences: A269024 A269025 A269026 * A269028 A269029 A269030


KEYWORD

nonn,base


AUTHOR

Vladimir Shevelev, Feb 18 2016


EXTENSIONS

More terms from Peter J. C. Moses, Feb 18 2016


STATUS

approved



