

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^(k1) 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 = (42)+(21) = 41 ={1,0,1}_b, so 1,0,1 are the digits in the balanced number system.
Also 7 = 4+2+1 =(84)+(42)+(21) = 81 =(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 quintfree, 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)=1a(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)=1a(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)=1a(n)=1a(m); a(4*n+2)= a(2*n+1)= a(4*m+1)=1a(m); a(4*n+3)=a(2*n+1)=1a(m); a(4*n+4)=a(n+1)=1a(m). But a(4*n)=a(n)=a(m) and a(4*n+5)=1a(n+1)=1a(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)=1a(n)=1a(m); a(4*n+2)= a(2*n+1)= a(4*m+1)=1a(m); a(4*n+3)=a(2*n+1)=1a(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)=1a(n+1)=1a(n) and a(4*n+1)=1a(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)=1a(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)=1a(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)=1a(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)=1a(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)=1a(n+1) and a(4*n+3)=a(2*n+1)=1a(n)=1a(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)=1a(n+1) but a(4*n+3)=a(2*n+1)=1a(n)=a(n+1) and a(4n+2)=a(n+1), a(4*n+1)=1a(n)=a(n+1), a(4*n)=a(n)=1a(n+1), i.e. the case reduces to 1b).
4c) Let n be odd, a(n)=1a(n+1). Then a(4*n+4)=a(n+1)=1a(n) while a(4*n+5)=1a(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)=1a(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 ThueMorse 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)=1a(n) or a(4*n)=a(n), a(4*n+1)=1a(n), a(4*n+2)=a(4*n+3)=a(2*n+1);
also a(n+2^k)=1a(n) for 0<=n<=2^(k1)1;
a(n+2^k) = a(n) for 2^(k1)<=n<=2^k1.
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[(n1)/2], a[(n1)/2], 1a[(n1)/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



