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 , shortest byte count wins.

share|improve this question
    
a) is printing essential, or can we just return a string or array? b) do the results have to be in ascending order? – Erresen 22 hours ago
    
@Erresen as long as the digits are displayed I am fine with whatever is golfiest in your language. – carusocomputing 19 hours ago
2  
"For more information, click the link." No. Put it in the question. – cat 7 hours ago

23 Answers 23

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.

share|improve this answer
    
That's an interesting approach, have you done this before? – carusocomputing yesterday
    
@carusocomputing Not this particular sequence, but I've done this type of recursion several times in the past. f is similar to a function I use occasionally to count the number of 1-bits in a number. – ETHproductions yesterday
    
Doesn't f fail when n=0? Also as f only returns 0 or 1 you can shave off two bytes by using n&f(n>>1). – Neil yesterday
    
@Neil "print the integers from 1 to n", n = 0 isn't a case ;). – carusocomputing yesterday
    
I shaved a further byte off your recursive solution by switching to filter: n=>[...Array(n+1).keys()].filter(f=n=>n<2?n:n%4?n&f(n>>1):f(‌​n/4)) – Neil yesterday

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
share|improve this answer
    
Does ƒ work instead of >G? – Adnan 23 hours ago
1  
@Adnan: Yes of course. I didn't use it to avoid N=0, but as it contains an odd number of zeroes it doesn't matter. Silly of me. Thanks :) – Emigna 23 hours ago

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 !

share|improve this answer

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
share|improve this answer

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 )

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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 
share|improve this answer
    
Edited question for clarification, I figured some people would just click the OEIS and go from there without reading ;P. That's what I do sometimes too hah. – carusocomputing yesterday
    
@carusocomputing Yes, I always read too fast :) – Luis Mendo yesterday

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.

share|improve this answer

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
share|improve this answer
    
Stacked looks like it could be fun to play with! – ElPedro 23 hours ago
    
@ElPedro thanks :D it really is – Conor O'Brien 23 hours ago

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.

share|improve this answer

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
share|improve this answer

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.

share|improve this answer
    
FYI, your golfed version of the code has somehow ended up with an unwanted parenthesis after the return s. And with that removed I think your byte count goes down to 128. – James Holderness 17 hours ago
    
@JamesHolderness Thanks for catching that! I made the mistake of golfing and ungolfing it a few times when I was first writing it, so that must have been how it snuck through. – Zavada 17 hours ago

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!

share|improve this answer
    
Nice method! I think you can do the base case as [1][n:]or. Also, x-~x for 2*x+1. – xnor 10 hours ago
    
This gives a very clean solution if you recurse out the tree instead: f=lambda n,k=1:n/k*[1]and[k]+f(n,k-~k)+f(n,4*k), assuming the ouputs can be in any order. – xnor 10 hours ago
    
@xnor That's crazy short. Thanks! – Dennis 5 hours ago

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.

share|improve this answer

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.

share|improve this answer

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}}
share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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 :)

share|improve this answer

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);
}
share|improve this answer
    
At a first glance, c%2==0 could be c%2<1. – TuukkaX 22 hours ago
    
Oh wait, this isn't even a valid submission. It should print the correct results from 1 to N. – TuukkaX 22 hours ago
    
@TuukkaX must've misread the question... revising answer now. – Erresen 22 hours ago
    
@TuukkaX Edited and credited – Erresen 22 hours ago
1  
b[i++] == '0' could be b[i++]==48, but since the other possible character is '1' (ASCII 49), you can just check whether b[i++]<49. – TuukkaX 21 hours ago

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)]
share|improve this answer

Jelly, 15 13 bytes

saved two bytes after looking at other answers

Bœṣ0,0FẠ
RÇ€T

Explanation

Bœṣ0,0FẠ  -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]]
      F   -Flatten the list [[1,1],[0]] -> [1,1,0]
       Ạ  -Return 0 if the list contains falsey values: [1,1,*0*] -> 0

RÇ€T      -Main link: argument N (integer)
R         -Range from [1..N] inclusive.
 ǀ       -Map our helper link to each value of the range
   T      -Get the indices of all truthy values (1's)
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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