login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 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

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.

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)

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 (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

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

Sequence in context: A295891 A291291 A285249 * A188027 A193496 A284533

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 22 14:51 EDT 2018. Contains 316489 sequences. (Running on oeis4.)