21
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ a) is printing essential, or can we just return a string or array? b) do the results have to be in ascending order? \$\endgroup\$ – Erresen Dec 22 '16 at 22:24
  • \$\begingroup\$ @Erresen as long as the digits are displayed I am fine with whatever is golfiest in your language. \$\endgroup\$ – Magic Octopus Urn Dec 23 '16 at 1:13
  • 2
    \$\begingroup\$ "For more information, click the link." No. Put it in the question. \$\endgroup\$ – cat Dec 23 '16 at 12:46

28 Answers 28

7
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Does ƒ work instead of >G? \$\endgroup\$ – Adnan Dec 22 '16 at 21:19
  • 1
    \$\begingroup\$ @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 :) \$\endgroup\$ – Emigna Dec 22 '16 at 21:20
  • \$\begingroup\$ @Emigna was hoping to see used ;). \$\endgroup\$ – Magic Octopus Urn Dec 27 '16 at 18:48
  • \$\begingroup\$ @carusocomputing: I considered that, but unfortunately I never got it shorter than this. \$\endgroup\$ – Emigna Dec 27 '16 at 21:18
8
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ That's an interesting approach, have you done this before? \$\endgroup\$ – Magic Octopus Urn Dec 22 '16 at 20:11
  • \$\begingroup\$ @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. \$\endgroup\$ – ETHproductions Dec 22 '16 at 20:16
  • \$\begingroup\$ 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). \$\endgroup\$ – Neil Dec 22 '16 at 20:36
  • \$\begingroup\$ @Neil "print the integers from 1 to n", n = 0 isn't a case ;). \$\endgroup\$ – Magic Octopus Urn Dec 22 '16 at 20:38
  • \$\begingroup\$ 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)) \$\endgroup\$ – Neil Dec 22 '16 at 20:38
4
\$\begingroup\$

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.

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

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 !

\$\endgroup\$
3
\$\begingroup\$

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

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 )

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

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.

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

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!

\$\endgroup\$
  • \$\begingroup\$ Nice method! I think you can do the base case as [1][n:]or. Also, x-~x for 2*x+1. \$\endgroup\$ – xnor Dec 23 '16 at 10:03
  • \$\begingroup\$ 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. \$\endgroup\$ – xnor Dec 23 '16 at 10:13
  • \$\begingroup\$ @xnor That's crazy short. Thanks! \$\endgroup\$ – Dennis Dec 23 '16 at 15:40
2
\$\begingroup\$

Mathematica, 59 bytes

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

Mathematica answer number 4...

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

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 
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Magic Octopus Urn Dec 22 '16 at 20:10
  • \$\begingroup\$ @carusocomputing Yes, I always read too fast :) \$\endgroup\$ – Luis Mendo Dec 22 '16 at 20:20
1
\$\begingroup\$

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.

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

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
\$\endgroup\$
  • \$\begingroup\$ Stacked looks like it could be fun to play with! \$\endgroup\$ – ElPedro Dec 22 '16 at 21:26
  • \$\begingroup\$ @ElPedro thanks :D it really is \$\endgroup\$ – Conor O'Brien Dec 22 '16 at 21:36
1
\$\begingroup\$

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.

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

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

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.

\$\endgroup\$
  • \$\begingroup\$ @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. \$\endgroup\$ – Zavada Dec 23 '16 at 3:23
0
\$\begingroup\$

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.

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

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.

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

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

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.

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

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ One byte saving you can take from my solution: !Or@@OddQ/@... \$\endgroup\$ – Martin Ender Dec 26 '16 at 0:04
0
\$\begingroup\$

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

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

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)]
\$\endgroup\$
0
\$\begingroup\$

Jelly, 10 bytes

2ṗx"`ḂḄf@R

Terribly inefficient. Try it online!

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

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.

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

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);
}
\$\endgroup\$
  • \$\begingroup\$ At a first glance, c%2==0 could be c%2<1. \$\endgroup\$ – Yytsi Dec 22 '16 at 22:01
  • \$\begingroup\$ Oh wait, this isn't even a valid submission. It should print the correct results from 1 to N. \$\endgroup\$ – Yytsi Dec 22 '16 at 22:04
  • \$\begingroup\$ @TuukkaX must've misread the question... revising answer now. \$\endgroup\$ – Erresen Dec 22 '16 at 22:06
  • \$\begingroup\$ @TuukkaX Edited and credited \$\endgroup\$ – Erresen Dec 22 '16 at 22:22
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Yytsi Dec 22 '16 at 23:37
0
\$\begingroup\$

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"&]&
\$\endgroup\$
0
\$\begingroup\$

Ruby, 53 Bytes

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

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)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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