# Binary Expansion Counting Sequence

I found another sequence not yet in the OEIS

The binary expansion sequence is defines as follows, assuming 0 indexing:

• The even numbers of the sequence are how often 0 has appeared in the binary expansion of all previous items in the sequence
• The odd elements are the same, but for 1s.

If you choose to 1-index, reverse "even" and "odd" in the description above to get the same sequence.

Leave at least one digit in the binary expansion.

Thus the first terms are:

• 0, because this is even, we count the numbers of 0s. There are none
• 0, because this is odd, we count the 1s. There are none
• 2, because this is even, we count the 0s, there has been 2 zeros
• 1 next, the number 2 had 1 1
• 3, two zeros from the first 2 terms, 1 from 2
• 4, 1 from 2, 1 from 1, 2 from 3

First 200 terms:

0
0
2
1
3
4
5
7
6
12
9
16
15
21
17
26
22
32
29
37
33
42
40
47
45
56
50
62
54
71
59
80
65
84
74
90
81
97
89
104
96
109
103
119
106
129
115
136
123
144
130
148
141
155
148
163
157
172
164
179
172
188
179
198
186
207
191
220
195
229
202
238
208
247
214
259
223
269
229
278
237
288
246
296
254
306
260
312
272
318
282
328
293
335
301
346
309
356
318
366
324
375
332
386
343
395
350
406
357
416
367
426
373
437
379
450
386
457
396
466
405
476
412
487
418
498
426
509
431
524
440
532
451
540
461
550
470
560
480
567
489
579
498
589
506
601
513
608
528
613
541
623
549
634
559
646
569
655
578
664
591
674
601
683
610
693
620
704
632
712
643
720
655
730
663
742
671
755
677
767
683
782
692
792
703
804
711
814
719
827
725
840
735
852
742
863
748
877
755
891


Sequence rules apply, you may either:

• Given n, output the nth element of the sequence
• Given n, output the first N terms
• Output the sequence infinity

Either 0 or 1 based indexing is acceptable.

• Such sequence would totally change for 1-index, if you allow both you should also provide that version
– l4m2
Commented Jan 19 at 21:37
• @l4m2 I hope that's now sufficiently clarified Commented Jan 19 at 22:41
• With decimal digits - A307153 Commented Jan 19 at 22:51
• "Given n, output the first n terms" can I assume that if n=0, no terms are output, even if I use 0-indexing? Commented Jan 26 at 21:01
• @Joao-3 Either option is fine Commented Jan 26 at 21:44

# JavaScript (ES6), 62 bytes

Returns the $$\n\$$-th term, 0-indexed.

f=(n,g=k=>k&&(k+n&1)+g(k>>1))=>n>2?g(f(--n))+g(p=f(n-1))+p:n&2


Try it online!

### Formula

Let $$\c_0\$$ and $$\c_1\$$ be functions counting the number of $$\0\$$'s and $$\1\$$'s respectively in the binary expansion.

Then:

$$a(0)=0,\:a(1)=0$$

and for $$\n\ge2\$$:

$$a(n)=c_{n\bmod2}(a(n-1))+c_{n\bmod2}(a(n-2))+a(n-2)$$

### Implementation

In the JS implementation, we use the same helper function $$\g\$$ for both $$\c_0\$$ and $$\c_1\$$. However, this function considers that there is no $$\0\$$ in the binary expansion of $$\0\$$. So we have to handle $$\a(2)=2\$$ as a special edge case.

# Vyxal 3, 8 bytes

Ṇ¤b∥fLḃC


Try it Online!

Finally a use for the generator structure!

## Explained

relation<         ## A relation based on
¤ to-binary !!:  ## Converting all previously generated values to binary and
flatten        ##   flattening that
length         ##   as well as getting the length of that
parity count     ## get the count of the bit parity of the length in the flattened binary.


# Wolfram Language (Mathematica), 47 bytes

a@n_:=a@n=Tr@DigitCount[Array[a,n,0],2,n~Mod~2]


Try it online!

-13 bytes from @Greg Martin
Also, we can remove memoization a@n= to save 4 bytes, but I'll keep it.
-15 bytes from @att

• I think you can get rid of the a@n= to save 4 bytes (at the cost of huge performance issues, I know). I think you can also replace If[OddQ@n,Tr@s,s~Count~0] by s~Count~Mod[n,2]. And then s is referenced only once, so you can golf even further by not defining it explicitly. Commented Jan 21 at 20:18
• DigitCount
– att
Commented Feb 2 at 23:11
• @att I get 62 bytes again Commented Feb 3 at 9:05
• Use the 3-argument form
– att
Commented Feb 3 at 9:14
• finally, got it Commented Feb 3 at 9:54

# Jelly, 10 bytes

LḂ=BFSṄṭ⁸ß


A full program that takes no arguments and prints indefinitely.

Try it online! (You can click the run button again to kill it after a couple of seconds and see what was output if you don't want to hang around for sixty seconds!)

### How?

LḂ=BFSṄṭ⁸ß - Main Link: no arguments
L          - length {X=sequence so far}
N.B. the first X is implicitly zero, which has length one
later X's will be the sequence so far (a list of integers)
Ḃ         - {that length} mod two -> P = 1 or 0
B       - convert {X} to binary -> BinaryExpansions(X)
=        - {P} equals {BinaryExpansions(X)} (vectorises)
-> list of lists of 1s (correct parity) and 0s (incorrect parity)
F      - flatten
S     - sum -> next number in the sequence
Ṅ    - print and yield it
ṭ⁸  - tack it to the end of X
ß - call this Link again with that


=index(decimal(reduce(0,sequence(A1),lambda(a,n,{a;base(len(substitute(join(,a),1-isodd(n),)),2)})),2))


Put $$\n\$$ in cell A1 and the formula in cell B1. The formula outputs the first $$\n + 1\$$ terms.

# JavaScript (Node.js), 61 bytes

f=(n,g=k=>k&&(k+n&1)+g(k>>1))=>n-->2?g(f(n))+f(n,g):-~n*!g(1)


Try it online!

Modified from Arnauld's

Pass g to use n of parent f than n inside

# JavaScript (Node.js), 68 bytes, 0-index

for(i=1,s='';;s+=a.toString(2))console.log(a=s.split(i^=1).length-1)


Try it online!

# JavaScript (Node.js), 66 bytes, 1-index

for(i=s='';;s+=a.toString(2))console.log(a=s.split(i^=1).length-1)


Try it online!

# Ruby, 42 bytes

a="";0.step{a+=p(a.count"#{_1%2}").to_s 2}


Attempt This Online!

Prints the sequence indefinitely.

# 05AB1E, 8 bytes

0λλbJNÉ¢


Outputs the infinite sequence.

Try it online.

Explanation:

 λ        # Start a recursive environment
# to output the lazy infinite sequence
# (which is output at the end implicitly)
0         # Starting with a(0)=0
# And where every following a(n) is calculated as:
λ       #  Push the sequence thus far: [a(0),a(1),...,a(n-1)]
b      #  Convert each integer to a binary string
J     #  Join those strings together
N    #  Push the current n
É   #  Check whether it's odd (1 if n is odd; 0 if n is even)
¢  #  Count how many 1s/0s there are in the joined binary string


# Charcoal, 16 bytes

ＦＮ⊞υ№⭆υ⍘κ²Ｉ﹪ι²Ｉυ


Try it online! Link is to verbose version of code. Outputs the first n terms. Explanation:

ＦＮ


Repeat n times.

⊞υ№⭆υ⍘κ²Ｉ﹪ι²


Convert all of the terms of the list so far to binary, then count either 0s or 1s depending on whether the current index is even or odd, and push that to the predefined empty list.

Ｉυ


Output the resulting list.

# Zsh, 46 bytes

for ((c=1;;c=!c))s+=$[[##2]n=${#s//$c}]&&<<<$n


Attempt This Online!

Output is in binary due to Zsh overzealously detecting what base I want. This can be prevented for +2 bytes.

Explanation:

                                                (implicitly set $s = "") c=1 initialise$c
for ((   ;;    ))                               loop forever:
${ s//$c}           remove $c characters from$s
${# } count the length of what's left n= save to$n
$[[##2] ] convert to binary s+= append to$s
&&<<<$n then print$n
c=!c                                  invert $c  # Haskell, 82 bytes f=h<$>[0..]
n#b=[1|mod n 2==b]++[x|n>1,x<-div n 2#b]
h n=sum$(#mod n 2)=<<take n f  Try it online! f generates the infinite sequence # Perl 5-p, 57 bytes map{$t=$_%2;$r.=sprintf"%b",$\=grep$t-$_,$r=~/./g}1..\$_}{


Try it online!

1-indexed because it's a byte shorter that way.

# Python 3.8 (pre-release), 79 75 bytes

Calculates the first n terms, zero indexed.

f=lambda n:n and(s:=f(n-1))+[sum(f"{k:b}".count("01"[n%2])for k in s)]or[0]


Try it online!

# PARI/GP, 57 bytes

f(n)=sum(i=1,n-1,#[1|d<-binary(f(i)),d-n%2])+2*(n>2&&n%2)


Attempt This Online!

1-index.