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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A268411 Parity of number of runs of 1's in binary representation of n. 15
0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1 (list; graph; refs; listen; history; text; internal format)
OFFSET

0

COMMENTS

Let A_k denote the first 2^k terms; then A_1 = {0,1} and for k >= 1, A_{k+1} = A_k B_k, where B_k is obtained from A_k by complementing the first 2^(k-1) 0's and 1's and leaving the rest unchanged. So, for example, A_2=0111, B_2=1011, A_3 = A_2B_2 = 01111011.

The "balanced binary" representation of n is obtained from the binary representation of n by replacing every 2^j by 2^(j+1)-2^j and appending a final "-1".

For example, 3=2+1 = (4-2)+(2-1) = 4-1 ={1,0,-1}_b, so 1,0,-1 are the digits in the balanced number system.

Also 7 = 4+2+1 =(8-4)+(4-2)+(2-1) = 8-1 =(1,0,0,-1)_b.

Properties of the "balanced binary" system:

a) the first digit is 1;

b) the digital sum is always 0;

c) deleting 0's, we obtain alternative sequence of 1,-1 for every n;

d) representation of every n>=0 is unique;

e) number of 1's (or the same number of (-1)'s) equals the number of blocks of 1's in binary.

The sequence lists parity of number of 1's (or, equally, of -1's) in the balanced binary representation of n.

From Vladimir Shevelev, May 18 2017 (Start)

Theorem. The sequence is quint-free, that is contains no subsequence of the form XXXXX.

For a proof, see [Shevelev] link, Section 8.

Theorem on the distribution of repetitions of equal terms.

1) 4 consecutive equal terms (the maximal number) start from every position of the form 16*k+1, k>=0.

2) Exactly 3 consecutive equal terms start from every position of the form 16*k+9 or of the form 8*k+6 satisfying a(2*k+1)=a(2*k+2).

3) Exactly 2 consecutive equal terms start from every position of the form 8*k+6 satisfying the condition a(2*k+1)=1-a(2*k+2).

4) Isolated terms occur in every position of the form either 8*k+5 or 8*k+4, if k is odd, or 8*k+8, if a(2*k+1)=1-a(2*k+2).

Proof. We use the formulas below proved in the [Shevelev] link.

1) Let n=2*m, m even. Then a(4*n+1)=1-a(n)=1-a(m); a(4*n+2)= a(2*n+1)= a(4*m+1)=1-a(m); a(4*n+3)=a(2*n+1)=1-a(m); a(4*n+4)=a(n+1)=1-a(m). But a(4*n)=a(n)=a(m) and a(4*n+5)=1-a(n+1)=1-a(2*m+1)=a(m). Thus in this case we have exactly 4 consecutive equal terms.

In this case m=2*k, n=4*k and 4*n+1=16*k+1.

2a) Let n=2*m, m odd. Then a(4*n+1)=1-a(n)=1-a(m); a(4*n+2)= a(2*n+1)= a(4*m+1)=1-a(m); a(4*n+3)=a(2*n+1)=1-a(m), but a(4*n+4)=a(n+1)= a(2*m+1)= a(m) and a(4*n)=a(n)=a(m). So in this case we have exactly 3 consecutive equal terms.

Here m=2*k+1, n=4*k+2 and 4*n+1=16*k+9.

2b) Let n be odd, a(n)=a(n+1). Then a(4*n+2)=a(2*n+1)=a(n); a(4*n+3)= a(2*n+1)=a(n); a(4*n+4)=a(n+1)=a(n). But a(4*n+5)=1-a(n+1)=1-a(n) and a(4*n+1)=1-a(n). So here we have exactly 3 consecutive equal terms.

Here n=2*k+1, 4*n+2=8*k+6 such that a(2*k+1)=a(2*k+2).

3) Let n be odd, but a(n)=1-a(n+1). Then a(4*n+2)=a(2*n+1)=a(n); a(4*n+3)= a(2*n+1)=a(n); but a(4*n+4)=a(n+1)=1-a(n). So here we have exactly 2 consecutive equal terms.

Here n=2*k+1, so 4*n+2=8*k+6,such that a(2*k+1)=1-a(2*k+2).

(Note that, if n is as in 2b), then a(4*n+3)=a(2*n+1)=a(n)=a(4*n+2) and the case reduces to 2b). Analogously, if n is as in 3), then a(4*n+3)=a(4*n+2) and the case reduces to 3).)

4a) Let n be odd. Then a(4*n+1)=1-a(n); a(4*n+2)=a(2*n+1)=a(n)

  and a(4*n)=a(n). Here we have an isolated 0 or 1 in the position 4*n+1. Here n=2*k+1, then 4*n+1=8*k+5.

4b) Let n be even and a(n)=a(n+1). Then a(4*n+4)=a(n+1), while a(4*n+5)=1-a(n+1) and a(4*n+3)=a(2*n+1)=1-a(n)=1-a(n+1). Here we have an isolated 0 or 1 in the position 4*n+4.

Here n=2*k and 4*n+4=8*k+4 such that a(2*k)=a(2*k+1) which holds if and only if k is odd.

(Let n be even and a(n) differs from a(n+1). Then a(4*n+4)=a(n+1), while a(4*n+5)=1-a(n+1) but a(4*n+3)=a(2*n+1)=1-a(n)=a(n+1) and a(4n+2)=a(n+1), a(4*n+1)=1-a(n)=a(n+1), a(4*n)=a(n)=1-a(n+1), i.e. the case reduces to 1b).

4c) Let n be odd, a(n)=1-a(n+1). Then a(4*n+4)=a(n+1)=1-a(n) while a(4*n+5)=1-a(n+1)=a(n) and a(4*n+3)=a(2*n+1)=a(n). So in this case we have an isolated 0 or 1 in the position 4*n+4.

Here n=2*k+1, then 4*n+4=8*k+8, such that a(2*k+1)=1-a(2*k+2)

QED (End)

Consider the constant R=0.0111101110..._2 which is obtained by the concatenated terms {a(n)} and interpreted as a binary real number R. Theorem. R is transcendental number. A proof can be found in [shevelev] link, Section 9. - Vladimir Shevelev, May 24 2017

LINKS

Peter J. C. Moses (terms 0..999) & Antti Karttunen, Table of n, a(n) for n = 0..1024

Vladimir Shevelev, Two analogs of Thue-Morse sequence, arXiv:1603.04434 [math.NT], 2016.

Index entries for sequences related to binary expansion of n

Index entries for characteristic functions

FORMULA

a(0)=0, a(2*n)=a(n); for odd n, a(2*n+1)=a(n); for even n, a(2*n+1)=1-a(n) or a(4*n)=a(n), a(4*n+1)=1-a(n), a(4*n+2)=a(4*n+3)=a(2*n+1);

also a(n+2^k)=1-a(n) for 0<=n<=2^(k-1)-1;

a(n+2^k) = a(n) for 2^(k-1)<=n<=2^k-1.

a(n) = A000035(A069010(n)). - Antti Karttunen, Feb 05 2016, after the alternative interpretation given by the author.

a(n) = A092248(A005940(1+n)). - Antti Karttunen, May 30 2017

EXAMPLE

In binary balanced system we have the representations:

   1 = {1,-1}

   2 = {1,-1,0}

   3 = {1,0,-1}

   4 = {1,-1,0,0}

   5 = {1,-1,1,-1}

   6 = {1,0,-1,0}

   7 = {1,0,0,-1}

   8 = {1,-1,0,0,0}

   9 = {1,-1,0,1,-1}

  10 = {1,-1,1,-1,0}

MATHEMATICA

balancedBinary:=Join[#, {0}]-Join[{0}, #]&[IntegerDigits[#, 2]]&;

Map[Mod[Count[balancedBinary[#], 1], 2]&, Range[0, 100]]

(*or using the formula*)

a[0]=0;

a[n_]:=a[n]=If[EvenQ[n], a[n/2], If[OddQ[(n-1)/2], a[(n-1)/2], 1-a[(n-1)/2]]];

Map[a, Range[0, 100]] (* Peter J. C. Moses, Feb 04 2016 *)

PROG

(Scheme) (define (A268411 n) (A000035 (A069010 n))) ;; Antti Karttunen, Feb 05 2016

(PARI) a(n) = ((1 + (hammingweight(bitxor(n, n>>1)))) >> 1)%2 \\ Charles R Greathouse IV, May 09 2016

(Python)

from sympy import prime, primefactors, log, floor

def a092248(n): return 0 if n==1 else 1*(len(primefactors(n))%2==1)

def A(n): return n - 2**int(floor(log(n, 2)))

def b(n): return n + 1 if n<2 else prime(1 + (len(bin(n)[2:]) - bin(n)[2:].count("1"))) * b(A(n))

def a(n): return a092248(b(n)) # Indranil Ghosh, Jun 01 2017

(Python)

def a(n): return sum(1 for d in bin(n)[2:].split('0') if len(d))%2 # Indranil Ghosh, Jun 01 2017, after Chai Wah Wu

CROSSREFS

Cf. A000035, A010060, A069010, A092248.

Cf. A268382 (partial sums).

Cf. A268412 (positions of zeros), A268415 (of ones).

Sequence in context: A296084 A302777 A189727 * A284944 A284674 A225181

Adjacent sequences:  A268408 A268409 A268410 * A268412 A268413 A268414

KEYWORD

nonn,base

AUTHOR

Vladimir Shevelev, Feb 04 2016

EXTENSIONS

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

Edited by N. J. A. Sloane, Feb 07 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 17 22:48 EDT 2018. Contains 316297 sequences. (Running on oeis4.)