|
%I #96 Aug 15 2022 08:37:18
%S 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,
%T 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,
%U 0,1,0,0,0,1,1,1,0,1,0,0,0,1,1,1,1,0,1
%N Parity of number of runs of 1's in binary representation of n.
%C 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.
%C 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".
%C 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.
%C Also 7 = 4+2+1 =(8-4)+(4-2)+(2-1) = 8-1 =(1,0,0,-1)_b.
%C Properties of the "balanced binary" system:
%C a) the first digit is 1;
%C b) the digital sum is always 0;
%C c) deleting 0's, we obtain alternative sequence of 1,-1 for every n;
%C d) representation of every n>=0 is unique;
%C e) number of 1's (or the same number of (-1)'s) equals the number of blocks of 1's in binary.
%C The sequence lists parity of number of 1's (or, equally, of -1's) in the balanced binary representation of n.
%C From _Vladimir Shevelev_, May 18 2017 (Start)
%C Theorem. The sequence is quint-free, that is contains no subsequence of the form XXXXX.
%C For a proof, see [Shevelev] link, Section 8.
%C Theorem on the distribution of repetitions of equal terms.
%C 1) 4 consecutive equal terms (the maximal number) start from every position of the form 16*k+1, k>=0.
%C 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).
%C 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).
%C 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).
%C Proof. We use the formulas below proved in the [Shevelev] link.
%C 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.
%C In this case m=2*k, n=4*k and 4*n+1=16*k+1.
%C 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.
%C Here m=2*k+1, n=4*k+2 and 4*n+1=16*k+9.
%C 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.
%C Here n=2*k+1, 4*n+2=8*k+6 such that a(2*k+1)=a(2*k+2).
%C 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.
%C Here n=2*k+1, so 4*n+2=8*k+6,such that a(2*k+1)=1-a(2*k+2).
%C (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).)
%C 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.
%C 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.
%C 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.
%C (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).
%C 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.
%C Here n=2*k+1, then 4*n+4=8*k+8, such that a(2*k+1)=1-a(2*k+2)
%C QED (End)
%C 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
%H Peter J. C. Moses (terms 0..999) & Antti Karttunen, <a href="/A268411/b268411.txt">Table of n, a(n) for n = 0..1024</a>
%H Paul Barry, <a href="https://arxiv.org/abs/2107.00442">Conjectures and results on some generalized Rueppel sequences</a>, arXiv:2107.00442 [math.CO], 2021.
%H Jeffrey Shallit, Sonja Linghui Shan, and Kai Hsiang Yang, <a href="https://arxiv.org/abs/2208.06025">Automatic Sequences in Negative Bases and Proofs of Some Conjectures of Shevelev</a>, arXiv:2208.06025 [cs.FL], 2022.
%H Vladimir Shevelev, <a href="http://arxiv.org/abs/1603.04434">Two analogs of Thue-Morse sequence</a>, arXiv:1603.04434 [math.NT], 2016.
%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%H <a href="/index/Ch#char_fns">Index entries for characteristic functions</a>
%F 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);
%F also a(n+2^k)=1-a(n) for 0<=n<=2^(k-1)-1;
%F a(n+2^k) = a(n) for 2^(k-1)<=n<=2^k-1.
%F a(n) = A000035(A069010(n)). - _Antti Karttunen_, Feb 05 2016, after the alternative interpretation given by the author.
%F a(n) = A092248(A005940(1+n)). - _Antti Karttunen_, May 30 2017
%e In binary balanced system we have the representations:
%e 1 = {1,-1}
%e 2 = {1,-1,0}
%e 3 = {1,0,-1}
%e 4 = {1,-1,0,0}
%e 5 = {1,-1,1,-1}
%e 6 = {1,0,-1,0}
%e 7 = {1,0,0,-1}
%e 8 = {1,-1,0,0,0}
%e 9 = {1,-1,0,1,-1}
%e 10 = {1,-1,1,-1,0}
%t balancedBinary:=Join[#,{0}]-Join[{0},#]&[IntegerDigits[#,2]]&;
%t Map[Mod[Count[balancedBinary[#],1],2]&,Range[0,100]]
%t (*or using the formula*)
%t a[0]=0;
%t a[n_]:=a[n]=If[EvenQ[n],a[n/2],If[OddQ[(n-1)/2],a[(n-1)/2],1-a[(n-1)/2]]];
%t Map[a,Range[0,100]] (* _Peter J. C. Moses_, Feb 04 2016 *)
%o (Scheme) (define (A268411 n) (A000035 (A069010 n))) ;; _Antti Karttunen_, Feb 05 2016
%o (PARI) a(n) = ((1 + (hammingweight(bitxor(n, n>>1)))) >> 1)%2 \\ _Charles R Greathouse IV_, May 09 2016
%o (Python)
%o from sympy import prime, primefactors, log, floor
%o def a092248(n): return 0 if n==1 else 1*(len(primefactors(n))%2==1)
%o def A(n): return n - 2**int(floor(log(n, 2)))
%o def b(n): return n + 1 if n<2 else prime(1 + (len(bin(n)[2:]) - bin(n)[2:].count("1"))) * b(A(n))
%o def a(n): return a092248(b(n)) # _Indranil Ghosh_, Jun 01 2017
%o (Python)
%o 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_
%Y Cf. A000035, A010060, A069010, A092248.
%Y Cf. A268382 (partial sums).
%Y Cf. A268412 (positions of zeros), A268415 (of ones).
%K nonn,base
%O 0
%A _Vladimir Shevelev_, Feb 04 2016
%E More terms from _Peter J. C. Moses_, Feb 04 2016
%E Edited by _N. J. A. Sloane_, Feb 07 2016
|
