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 7 hours ago
    
@Erresen as long as the digits are displayed I am fine with whatever is golfiest in your language. – carusocomputing 5 hours ago

21 Answers 21

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 10 hours ago
    
@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 10 hours ago
    
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 9 hours ago
    
@Neil "print the integers from 1 to n", n = 0 isn't a case ;). – carusocomputing 9 hours ago
    
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 9 hours ago

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

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

PowerShell, 79 bytes

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

Try it online!

Thanks to a ridiculously long .NET call to convert the number to binary, this is a whopper.

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 1 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+ to filter out only the substrings of 0s, using -ne'' to remove any empty results. For each of those substrings |%{...}, we put an odd/even modulo on the pipeline (1 or 0). Thus, if every run of 0s in the binary string is even, then 1 will be -notin the result, so the Where clause is true, and the number is selected. Those are left on the pipeline and output is implicit.

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

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 10 hours ago
    
@carusocomputing Yes, I always read too fast :) – Luis Mendo 9 hours ago

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 8 hours ago
    
@ElPedro thanks :D it really is – Conor O'Brien 8 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

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 2 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 2 hours ago

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

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

C# 163 161 bytes

Saved 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++]=='0')c++;else if(c%2>0)break;}if(c%2<1)Console.WriteLine(n);if(n>1)Baums(--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' and increment i. increment c if true
        if (b[i++] == '0')
            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 8 hours ago
    
Oh wait, this isn't even a valid submission. It should print the correct results from 1 to N. – TuukkaX 8 hours ago
    
@TuukkaX must've misread the question... revising answer now. – Erresen 8 hours ago
    
@TuukkaX Edited and credited – Erresen 7 hours ago
    
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 6 hours ago

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

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

Python 2, 67 bytes

f=lambda n:n and{t for x in f(n/2)for t in(x,2*x+1,4*x)if n/t}or{1}

Returns a set. Try it online!

No match for @xnor's answer, but I still think it's interesting. On the bright side, it's quite efficient; input 100,000 takes roughly 20 ms.

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.