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
Paul Barry, Conjectures and results on some generalized Rueppel sequences, arXiv:2107.00442 [math.CO], 2021.
Jeffrey Shallit, Sonja Linghui Shan, and Kai Hsiang Yang, Automatic Sequences in Negative Bases and Proofs of Some Conjectures of Shevelev, arXiv:2208.06025 [cs.FL], 2022.
Vladimir Shevelev, Two analogs of Thue-Morse sequence, arXiv:1603.04434 [math.NT], 2016.
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.
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
(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
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