13
\$\begingroup\$

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.

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

14 Answers 14

5
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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.
\$\endgroup\$
4
\$\begingroup\$

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

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

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
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

Ruby, 42 bytes

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

Attempt This Online!

Prints the sequence indefinitely.

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 16 bytes

FN⊞υ№⭆υ⍘κ²I﹪ι²Iυ

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

FN

Repeat n times.

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

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.

Iυ

Output the resulting list.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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