Binary Expansion Counting Sequence

Question

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:

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
"Given n, output the first n terms" can I assume that if n=0, no terms are output, even if I use 0-indexing? — Joao-3, Commented Jan 26 at 21:01

Arnauld · Accepted Answer · 2024-01-20 11:21:14Z

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.

lyxal · Accepted Answer · 2024-01-20 00:09:05Z

4

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.

edited Jan 20 at 0:09

answered Jan 19 at 23:53

lyxal

34k2 gold badges63 silver badges139 bronze badges

Add a comment |

ZaMoC · Accepted Answer · 2024-02-03 09:54:18Z

4

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

edited Feb 3 at 9:54

answered Jan 19 at 21:48

ZaMoC

24.9k2 gold badges30 silver badges81 bronze badges

\$\begingroup\$ 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. \$\endgroup\$
– Greg Martin
Commented Jan 21 at 20:18
\$\begingroup\$ DigitCount \$\endgroup\$
– att
Commented Feb 2 at 23:11
\$\begingroup\$ @att I get 62 bytes again \$\endgroup\$
– ZaMoC
Commented Feb 3 at 9:05
\$\begingroup\$ Use the 3-argument form \$\endgroup\$
– att
Commented Feb 3 at 9:14
\$\begingroup\$ finally, got it \$\endgroup\$
– ZaMoC
Commented Feb 3 at 9:54

Add a comment |

Jonathan Allan · Accepted Answer · 2024-01-19 23:01:52Z

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

doubleunary · Accepted Answer · 2024-01-20 09:09:39Z

2

Google Sheets, 103 bytes

=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.

edited Jan 20 at 9:09

answered Jan 19 at 23:41

doubleunary

2,2101 gold badge2 silver badges12 bronze badges

Add a comment |

l4m2 · Accepted Answer · 2024-01-20 14:17:53Z

2

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!

edited Jan 20 at 14:17

answered Jan 19 at 21:35

l4m2

26.1k2 gold badges23 silver badges97 bronze badges

Add a comment |

Kirill L. · Accepted Answer · 2024-01-21 11:29:08Z

2

Ruby, 42 bytes

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

Attempt This Online!

Prints the sequence indefinitely.

answered Jan 21 at 11:29

Kirill L.

14.1k2 gold badges16 silver badges50 bronze badges

Add a comment |

Kevin Cruijssen · Accepted Answer · 2024-01-24 08:20:40Z

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

Neil · Accepted Answer · 2024-01-20 01:26:29Z

1

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.

answered Jan 20 at 1:26

Neil

174k12 gold badges73 silver badges277 bronze badges

Add a comment |

pxeger · Accepted Answer · 2024-01-21 10:55:18Z

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

colossus16 · Accepted Answer · 2024-01-24 15:27:42Z

1

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

answered Jan 24 at 15:27

colossus16

1,8917 silver badges10 bronze badges

Add a comment |

Xcali · Accepted Answer · 2024-01-24 22:06:34Z

1

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.

edited Jan 24 at 22:06

answered Jan 24 at 17:49

Xcali

15.8k2 gold badges15 silver badges39 bronze badges

Add a comment |

movatica · Accepted Answer · 2024-02-03 18:48:12Z

1

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!

edited Feb 3 at 18:48

answered Feb 3 at 15:54

movatica

1,2937 silver badges8 bronze badges

Add a comment |

alephalpha · Accepted Answer · 2024-01-21 14:47:16Z

0

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.

answered Jan 21 at 14:47

alephalpha

49.4k7 gold badges65 silver badges181 bronze badges

Add a comment |

Stack Exchange Network

Binary Expansion Counting Sequence

14 Answers 14

JavaScript (ES6), 62 bytes

Formula

Implementation

Vyxal 3, 8 bytes

Explained

Wolfram Language (Mathematica), 47 bytes

Jelly, 10 bytes

How?

Google Sheets, 103 bytes

JavaScript (Node.js), 61 bytes

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

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

Ruby, 42 bytes

05AB1E, 8 bytes

Charcoal, 16 bytes

Zsh, 46 bytes

Haskell, 82 bytes

Perl 5 `-p`, 57 bytes

Python 3.8 (pre-release), 79 75 bytes

PARI/GP, 57 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
sequence
or ask your own question.

Hot Network Questions

Binary Expansion Counting Sequence

14 Answers 14

JavaScript (ES6), 62 bytes

Formula

Implementation

Vyxal 3, 8 bytes

Explained

Wolfram Language (Mathematica), 47 bytes

Jelly, 10 bytes

How?

Google Sheets, 103 bytes

JavaScript (Node.js), 61 bytes

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

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

Ruby, 42 bytes

05AB1E, 8 bytes

Charcoal, 16 bytes

Zsh, 46 bytes

Haskell, 82 bytes

Perl 5 -p, 57 bytes

Python 3.8 (pre-release), 79 75 bytes

PARI/GP, 57 bytes

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golfsequence or ask your own question.

Related

Hot Network Questions

Perl 5 `-p`, 57 bytes

Not the answer you're looking for? Browse other questions tagged
code-golf
sequence
or ask your own question.