The Baum-Sweet Sequence

Question

The Baum-Sweet Sequence (A086747 with a Twist)

Take in a positive integer n and print the integers from 1 to n for which the Baum-Sweet sequence returns true. The Baum-Sweet sequence should return falsy if the binary representation of the number contains an odd number of consecutive zeros anywhere in the number, and truthy otherwise. For more information, click the link. Here's a couple of examples:

1 -> 1 -> Truthy
2 -> 10 -> Falsy
3 -> 11 -> Truthy
4 -> 100 -> Truthy (Even run of zeros)

Here's an example given n=32

Step 1: The Baum-Sweet sequence visualized for n=32

1               1 (1)
1 0             0 (2)
11              1 (3)
1 00            1 (4)
1 0 1           0 (5)
11 0            0 (6)
111             1 (7)
1 000           0 (8)
1 00 1          1 (9)
1 0 1 0         0 (10)
1 0 11          0 (11)
11 00           1 (12)
11 0 1          0 (13)
111 0           0 (14)
1111            1 (15)
1 0000          1 (16)
1 000 1         0 (17)
1 00 1 0        0 (18)
1 00 11         1 (19)
1 0 1 00        0 (20)
1 0 1 0 1       0 (21)
1 0 11 0        0 (22)
1 0 111         0 (23)
11 000          0 (24)
11 00 1         1 (25)
11 0 1 0        0 (26)
11 0 11         0 (27)
111 00          1 (28)
111 0 1         0 (29)
1111 0          0 (30)
11111           1 (31)
1 00000         0 (32)

So, after computing the Baum-Sweet sequence for n, take the numbers that were truthy for the sequence and collect them for the final result. For n=32 we would have:

[1, 3, 4, 7, 9, 12, 15, 16, 19, 25, 28, 31]

As the final answer.

---

This is code-golf, shortest byte count wins.

Answer 1

JavaScript (ES6), 70 68 63 bytes

g=n=>n?g(n-1).concat(/0/.test(n.toString(2).split`00`)?[]:n):[]

console.log(g(1000).join(", "))

Slightly more interesting recursive solution:

n=>[...Array(n+1).keys()].filter(f=n=>n<2?n:n%4?n&f(n>>1):f(‌​n/4))

67 bytes thanks to @Neil.

g is the function to call.

Answer 2

05AB1E, 10 9 bytes

Saved a byte thanks to Adnan

ƒNb00¡SP–

Try it online!

Explanation

ƒ          # for N in [0 ... input]
 Nb        # convert N to binary
   00¡     # split at "00"
      S    # convert to list of digits
       P   # product of list
        –  # if 1, print N

Answer 3

Python 2, 62 bytes

g=lambda n:n*[0]and g(n-1)+[n]['0'in`bin(n)[1:].split('00')`:]

Checks for odd runs of 1's in the binary representation by splitting on 00 and checking if any zeroes remain in the string representation of the resulting list. Annoyingly, binary numbers start with 0b, which has a zero that needs to be removed to avoid a false positive.

The enumeration is done by recursing down.

Answer 4

Bash, 58, 46 bytes

EDITS:

• Replaced bc with dc (Thx @Digital Trauma !)
• Start with 1;

Golfed

seq $1|sed 'h;s/.*/dc -e2o&p/e;s/00//g;/0/d;x'

Test

>./baum 32
1 
3
4
7 
9
12
15
16
19
25
28
31

Explained

shell

seq $1 #generate a sequence of integers from 1 to N, one per line
|sed   #process with sed

sed

h                #Save input line to the hold space
s/.*/dc -e2o&p/e #Convert input to binary, with dc
s/00//g          #Remove all successive pairs of 0-es
/0/d             #If there are still some zeroes left
                 #(i.e. there was at least one odd sequence of them)
                 #drop the line, proceed to the next one
x                #Otherwise, exchange the contents of the hold 
                 #and pattern spaces and (implicitly) print

Try It Online !

Answer 5

Batch, 143 bytes

@for /l %%i in (1,1,%1)do @call:c %%i
@exit/b
:c
@set/ai=%1
:l
@if %i%==1 echo %1&exit/b
@set/ar=%i%%%4,i/=4-r%%2*2
@if %r% neq 2 goto l

Answer 6

Perl 6, 40 bytes

{grep {.base(2)!~~/10[00]*[1|$]/},1..$_}

Try it

{
  grep            # find all of them
  {
    .base(2)      # where the binary representation
    !~~           # does not match
    /
      10          # ｢10｣
      [ 00 ]*     # followed by an even number of ｢0｣s
      [ 1 | $ ]   # either at end or before a ｢1｣
    /
  }, 1 .. $_      # from one to the input
}

( [] are used for non-capturing grouping, with <[]> used for character classes )

Answer 7

PowerShell, 79 61 bytes

1..$args[0]|?{0-notin([convert]::ToString($_,2)-split'1|00')}

Try it online!

I had inspiration this morning to change how I perform the -split operation, then see that it's similar to how xnor's answer is constructed, so, I guess great minds think alike?

We loop from 1 up to input $args[0], and use a Where-Object operator to pull out the appropriate numbers |?{...}. The clause is a simple Boolean value -- we're ensuring that 0 is -notin the results of (...).

Inside the parens, we [convert]:: the current number $_ ToString with the base 2 (i.e., turn it into a binary string). We then -split the string on the regex 1|00 -- this is a greedy match, and results in an array of strings (for example, 100010 would turn into '','','0','','0' and so forth).

Thus, if every run of 0s in the binary string is even (meaning the regex has split them out into empty strings), then 0 will be -notin the result, so the Where clause is true, and the number is selected. Those numbers are left on the pipeline and output is implicit.

Answer 8

Python 2, 67 47 bytes

f=lambda n,k=1:n/k*[1]and[k]+f(n,k-~k)+f(n,4*k)

Thanks to @xnor to golfing off 20(!) bytes!

Returns an unordered list. It's quite efficient: input 100,000 takes roughly 40 ms on TIO.

Try it online!

Answer 9

Mathematica, 59 bytes

Select[Range@#,!Or@@OddQ/@Tr/@Split[1-#~IntegerDigits~2]&]&

Mathematica answer number 4...

Answer 10

MATL, 12 11 bytes

:"@BY'og)?@

Try it online!

Explanation

To detect if a number is valid this converts to binary, applies run-length encoding, keeps only runs of odd length, and checks if no run of zeros survives.

:       % Take input n implicitly. Push range [1 2 ... n]
"       % For each k in [1 2 ... n]
  @     %   Push k
  B     %   Convert to binary
  Y'    %   Run-length encoding. Pushes array of values and array of run-lengths
  o     %   Parity. Gives array that contains 0 for even lengths, 1 for odd
  g)    %   Convert to logical and use index into the array of values
  ?     %   If the result does not contain zeros
    @   %     Push k
        %   End
        % End
        % Implicitly display stack 

Answer 11

R, 75 bytes

for(i in 1:scan()){x=rle(miscFuncs::bin(i));if(!any(x$l%%2&!x$v))cat(i,"")}

Reads input from stdin and uses the bin function from the miscFuncs package to convert from decimal to binary vector. Consequently performs run-length encoding to check values == 0 and lengths are odd.

Answer 12

Stacked, 69 bytes

Try it here!

:>1+[bits{e.b:e b 0#=}chunkby[0 has]filter$sizemap 2%0 eq all]"filter

Or, noncompeting at 67 bytes:

:>1+[bits{e.b:e b 0#=}chunkby[0 has]filter$sizemap even all]"filter

And, even more noncompeting at 49 bytes:

:>1+[bits rle{k:k 0=}filter values even all]fkeep

All take input as TOS and leaves output on TOS.

Explanation

:>1+[...]"filter   input: n
:>                 range from [0, n)
  1+               range from [1, n]
    [...]          a function
         "filter   apply to each cell and filter

The function:

bits{e.b:e b 0#=}chunkby[0 has]filter$sizemap 2%0 eq all  input: c
bits                                                      convert c to binary
    {e.b:e b 0#=}chunkby                                  split into chunks of contiguous 0s
                        [0 has]filter                     take only chunks with 0s
                                     $sizemap             map each chunk to its size
                                              2%          vectorized modulus 2
                                                0 eq      vectorized equality with 0
                                                     all  all of them are of even lengths

Explanation of noncompeting:

It's the same as above, with a few key differences:

:>1+[bits rle{k:k 0=}filter values even all]fkeep   input: y
          rle                                       run length encode y
             {k:k 0=}filter                         keep keys that = 0
                            values                  get those values
                                            fkeep   like `filter`, but is implemented with
                                                    taking `f` as a boolean mask

Answer 13

Befunge, 84 51 49 bytes

After a bit of experimentation, I realised I could do quite a bit better than my original solution by using a technique similar to the Batch answer that Neil came up with.

<v::\<&1
:_v#:/+2*2!%2:_v#-2%4
:$<@_v#!:-1\+1$<:.

Try it online!

As with my original solution, there are two loops - the outer loop iterating over the numbers we want to test, and an inner loop testing the bit sequence for each number. The way the test works is by examining two bits at a time (modulo 4 of the current value). If that's equal to 2 we've got an odd sequence of zeros and can abort the inner loop and proceed to the next number.

If the modulo 4 is not equal to 2, we need to continue testing the remaining bits, so we shift up the bits that have already been tested. This is done by dividing the value, lets call it n, by 2+2*!(n%2). This means if the first bit was a 1, we divide by 2 (dropping that 1 bit), but if it was a 0, we divide by 4, so we'll always be dropping pairs of zeros.

If we eventually get down to zero, that means there weren't any odd sequences of zero bits, so we write out the number.

Answer 14

Visual Basic(.net 4.5) 163 bytes

First ever answer here so I'm sure I've screwed something up. Let me know and I'll fix. Are Visual Basic lambdas even allowed?

Thanks to MamaFunRoll for the remove consecutive zeroes idea

Dim R=Sub(m)System.Console.WriteLine(String.Join(",",System.Linq.Enumerable.Range(1, m).Where(Function(s) Not Convert.ToString(s,2).Replace("00","").Contains(0))))

R(32) outputs

1,3,4,7,9,12,15,16,19,25,28,31

Answer 15

Java, 144 130 128 Bytes

This isn't as golfed as I think it can be, but I thought it'd be a cute solution to use a Regex, despite never having used one.

Golfed:

static String a(int n){String s="";for(Integer i=0;i++<n;)if(i.toString(i,2).replaceAll("00|1","").isEmpty())s+=i+" ";return s;}

Ungolfed:

static String a(int n){
    String s="";                      //Cheaper than using a list/array
    for(Integer i=0;i++<n;)           //Loop n times
        if(i.toString(i,2)            //Convert int to base 2 string
                .replaceAll("00|1","")//Find and remove ones and consecutive zeroes
                .isEmpty())           //If any chars remain, i is truthy
            s+=i+" ";                 //Append i to the storage string
    return s;                         //Return all values
}

Edit: I was able to save 14 bytes by making the regex 00|1 instead of 00, and removing ".replace("1","")" between the replaceAll and isEmpty!

Edit 2: I was able to save 2 bytes by making i an Integer and referencing Integer.toString with i.toString.

Answer 16

Clojure, 103 bytes

I don't think this is the shortest way...

#(remove(fn[v]((set(map(fn[s](mod(count s)2))(re-seq #"0+"(Integer/toString v 2))))1))(range 1(inc %)))

Uses re-seq to find consecutive zeros, maps their modulo-2 lengths to a set, discards them if number 1 is found from the set.

Answer 17

Wonder, 38 bytes

@(!>@=1len iO0Rstr#["00"]bn#0)rng1+1#0

Usage:

(@(!>@=1len iO0Rstr#["00"]bn#0)rng1+1#0) 32

Explanation

More readable:

@(
  fltr@
    = 1 
      len 
        iO 0 
          Rstr #["00"] 
            bn #0
) rng 1 +1 #0

rng 1 +1 #0: Range from 1 to input.

fltr@ ...: Filter range with the following predicate.

bn #0: Convert current item to binary. (This will have a leading 0b).

Rstr #["00"]: Recursively prune any occurrences of 00 in the string.

len iO 0: Count the amounts of 0s in the string.

=1: Check if the amount is equal to 1. If the only 0 left in the string after pruning is in the leading 0b, then this returns true; otherwise, this returns false.

Answer 18

Ruby, 78 69 68 bytes

->n{(1..n).select{|m|m.to_s(s=2).split(?1).map{|i|s|=i.size};s&1<1}}

Older versions:

->n{(1..n).select{|m|m.to_s(2).split(?1).select{|i|i.size%2>0}[0].!}}
->n{(1..n).select{|m|b=z=0;(m.to_s(2)+?1).each_char{|i|z+=i>?0?b|=z:1};b&1<1}}

Answer 19

Mathematica, 81 bytes

Select[Range@#,FreeQ[Union@#+Mod[Length@#,2,1]&/@Split[#~IntegerDigits~2],{1}]&]&

Computes, for each run of consecutive digits in a number, { the common digit in that run plus (1 if the length is odd, 2 if the length is even) }; if any of the answers is {1} then the number isn't in the sequence.

Answer 20

Mathematica, 75 bytes

Select[Range@#,And@@EvenQ/@Length/@Cases[Split[#~IntegerDigits~2],{0..}]&]&

#~IntegerDigits~2 computes the list of binary digits of the input #. Split that list into runs of identical elements, take the Cases that match {0..}, take the Length of each of them, take EvenQ of the lengths and then return And of the results.

Answer 21

Python 3, 86 82 bytes

Golfing in progress...

lambda n:[x for x in range(1,n+1)if 1-any(i%2for i in map(len,bin(x).split('1')))]

Golfed off 4 bytes by changing bin(x)[2:] to just bin(x) - this leaves 0b at the start of the string, but I realised this does not actually affect the calculations :)

Answer 22

Python, 142 bytes

This is mainly just to practice golfing my Python.

def o(n):
 r=0
 for i in bin(n)[2:]:
  if i=='1':
   if r&1:return 0
   r=0
  else:r+=1
 return ~r&1
lambda n:[i for i in range(1,n+1)if o(i)]

Answer 23

Jelly, 10 bytes

2ṗx"`ḂḄf@R

Terribly inefficient. Try it online!

Answer 24

Ruby, 54 53 48 bytes

->n{(1..n).reject{|x|x.to_s(2)=~/10(00)*(1|$)/}}

I didn't think the regex for this was going to be quite so basic.

edit 1: switched to reject to get rid of negation for -1.

edit 2: switched match to =~ for -5.

Answer 25

C# 159 157 155 bytes

Saved 2 x two bytes thanks to TuukkaX.

Note: prints out the ints in reverse order.

void B(int n){var b=Convert.ToString(n,2);int c=0,i=0;for(;i<b.Length;){if(b[i++]<49)c++;else if(c%2>0)break;}if(c%2<1)Console.WriteLine(n);if(n>1)B(--n);}

Explanation:

void B(int n)
{
    // convert our int to a binary string
    var b = Convert.ToString(n, 2);

    // set our '0' counter 'c' and our indexer 'i' 
    int c = 0, i = 0;

    // loop over the binary string, without initialisation and afterthought
    for (; i < b.Length;)
    {
        // check for '0' (48 ASCII) and increment i. increment c if true
        if (b[i++] < 49)
            c++;

        // otherwise check if c is odd, and break if it is
        else if (c%2 > 0)
            break;
    }

    // print the int if c is even
    if (c%2 < 1)
        Console.WriteLine(n);

    // recursively call B again with the next number
    if (n > 1)
        B(--n);
}

Answer 26

Mathematica, 69 bytes

Select[Range@#,FreeQ[#~IntegerDigits~2//.{x___,0,0,y___}:>{x,y},0]&]&

The same length:

Select[Range@#,#~IntegerString~2~StringDelete~"00"~StringFreeQ~"0"&]&

Answer 27

Ruby, 53 Bytes

->n{(1..n).each{|n|p n if n.to_s(2).count(?0).even?}}

Answer 28

Jelly, 15 13 10 bytes

saved two bytes after looking at other answers, another 3 bytes thanks to Dennis

Bœṣ0,0Ȧµ€T

Explanation

Bœṣ0,0Ȧµ€T -Helper link: argument K (integer): ex. 24
B          -Convert K to a list of its binary digits: 24 -> [1,1,0,0,0]
   0,0     -Create a list of two 0's: [0,0]
 œṣ        -Split the binary digits on instances of the sublist: [1,1,0,0,0]-> [[1,1],[0]]
      Ȧ    -Any and All: Check if our list has any falsy values or is empty
       µ   -Take all our previous atoms and wrap them into one monad.
        €  -Map this new monad over a list. Since our input is an integer, this implicitly maps it over the range [1..N] (Like the 'R' atom)
         T -Get the indices of all truthy values (1's)