30
\$\begingroup\$

Task

Find the set of numbers such that the binary representation contains two or more runs of 1 separated by at least one 0.

For example, the for the numbers that are 4 bits long:

 0 0000        (no ones)
 1 0001        (only one run)
 2 0010        (only one run)
 3 0011        (only one run)
 4 0100        (only one run)
 5 0101 Valid
 6 0110        (only one run)
 7 0111        (only one run)
 8 1000        (only one run)
 9 1001 Valid
10 1010 Valid
11 1011 Valid
12 1100        (only one run)
13 1101 Valid
14 1110        (only one run)
15 1111        (only one run)

Input

An integer provided to the application via some input in the range 3 .. 32. This represents the maximum number of bits to count up to.

The input of n indicates that the numbers 0 .. 2n-1 need to be examined.

Output

A delimited (your choice) list of all numbers meeting the criteria. The numbers are to be presented in numeric order. An extra trailing delimiter is acceptable. Data structure enclosures (e.g. [] and similar) are also acceptable.

Example

Input: 3
Output: 5

Input: 4
Output: 5, 9, 10, 11, 13

Input: 5
Output: 5, 9, 10, 11, 13, 17, 18, 19, 20, 21, 22, 23, 25, 26, 27, 29

This is - the answer with the least amount of bytes wins.

\$\endgroup\$
  • \$\begingroup\$ I think you missed 23 for n=5. \$\endgroup\$ – xnor Oct 21 '15 at 21:02
  • \$\begingroup\$ @xnor you are correct. Thank you, and yep, that also makes it not equivalent to A094695. Hmm. oeis.org/A101082 vs oeis.org/A166934 \$\endgroup\$ – user12166 Oct 21 '15 at 21:03
  • \$\begingroup\$ @VTCAKAVSMoACE yes. If one is \n delimiting and putting a \n on the last line, then , delimited with a , trailing should be acceptable too. Updated. \$\endgroup\$ – user12166 Oct 21 '15 at 21:24
  • 1
    \$\begingroup\$ Can the input be in a list format like [1, 2, 3]? \$\endgroup\$ – kirbyfan64sos Oct 21 '15 at 22:33
  • \$\begingroup\$ @kirbyfan64sos yes. Updated. \$\endgroup\$ – user12166 Oct 21 '15 at 23:11

32 Answers 32

7
\$\begingroup\$

Pyth, 12 bytes

f<2r.BT8U^2Q

Try it online.

Idea

The binary representation of any positive number always begins with a run of 1s, possibly followed by other, alternating runs of 0s and 1s. If there are at least three separate runs, two of them are guaranteed to be runs of 1s.

Code

              (implicit) Store the evaluated input in Q.
         ^2Q  Calculate 2**Q.
f       U     Filter; for each T in [0, ..., 2**Q-1]:
    .BT         Compute T's binary representation.
   r   8        Perform run-length encoding.
                This returns a list of character/run-length pairs.
 <2             Discard the trailing two pairs.
                This returns a non-empty array if there are more than 2 runs.
              Keep T if the array was truthy (non-empty).
\$\endgroup\$
22
\$\begingroup\$

Python, 48

lambda n:[i for i in range(2**n)if'01'in bin(i)]

I had been vastly overthinking this. We just need to check if the binary expansion contains '01'.

For there to be two runs of ones, the one on the right must be preceded by a 0. If there's only one run, there won't be any leading 0's, so that won't happen.


Old answer:

lambda n:[i for i in range(2**n)if len(set(bin(i).split('0')))>2]

The Python binary representation works very nicely here. A binary number is written like bin(9)=='0b10110'. Splitting at '0' results in a list of

  • Empty strings to the left of the initial 0, between any two consecutive 0's, and to the right of any final 0
  • The letter b followed by one or more leading ones
  • Runs of 1's that are not leading

The first two categories always exist, but the last one only exists if there is a run one 1's that doesn't contain the leading '1', and so only if there's more than one run of 1's. So, it suffices to check if the list contains more than 2 distinct elements.

Python 3.5 saves 2 chars by unpacking {*_} in place of set(_).

\$\endgroup\$
  • \$\begingroup\$ Thanks for the idea to use /01/ instead of /10+1/. I took advantage of that in Perl. \$\endgroup\$ – msh210 Oct 21 '15 at 22:48
13
\$\begingroup\$

Ruby, 44 40 38 chars

crossed out 44 is still regular 44 ;(

->n{(0..2**n).select{|x|/01/=~'%b'%x}}

An anonymous function (proc, actually) that takes an integer and returns an array.

Uses the regex /10+1/: a 1, at least one 0, and then another 1. @histocrat points out that if 01 is anywhere in the string, there must be a 1 somewhere before it.

\$\endgroup\$
  • 1
    \$\begingroup\$ Using a format string is a bit shorter here: /10+1/=~'%b'%x. Also, you can save a character by using an inclusive range(0..2**n) since 2**n will never have multiple runs. \$\endgroup\$ – histocrat Oct 21 '15 at 21:07
  • \$\begingroup\$ @histocrat Huh, I never knew you could flip the order of the string and the regex with =~. Thanks! \$\endgroup\$ – Doorknob Oct 21 '15 at 21:10
  • 1
    \$\begingroup\$ Wait, actually the regex /01/ works just as well. If there's a 01, there must be a 1 to the left somewhere. \$\endgroup\$ – histocrat Oct 21 '15 at 21:27
  • \$\begingroup\$ @histocrat Oh, that's clever! That saves two characters. \$\endgroup\$ – Doorknob Oct 21 '15 at 21:30
7
\$\begingroup\$

Julia, 43 41 bytes

n->filter(i->ismatch(r"01",bin(i)),1:2^n)

This creates an unnamed function that accepts an integer and returns an array. It uses histocrats's regex trick (used in Doorknob's answer), where 01 will only match if there's a preceding 1.

Ungolfed:

function f(n::Int)
    # Take the integers from 1 to 2^n and filter them down to
    # only those such that the binary representation of the integer
    # matches the regex /01/.
    filter(i -> ismatch(r"01", bin(i)), 1:2^n)
end
\$\endgroup\$
  • \$\begingroup\$ histocrat's trick, not mine. :) \$\endgroup\$ – Doorknob Oct 22 '15 at 20:48
  • \$\begingroup\$ @Doorknob Oh hey, now you both get credit. :) \$\endgroup\$ – Alex A. Oct 22 '15 at 20:49
6
\$\begingroup\$

Matlab, 79 68 64 59

The idea is interpreting the binary number as array of zeros and ones, and then calculating the absolute difference between each pair of neighbours. If we have two or more times a difference of 1, then we obviously have a run of two or more ones. Note that this only works if we represent the binary number without leading zeros.

@(n)find(arrayfun(@(k)sum(~~diff(dec2bin(k)+0))>1,1:2^n-1))

Old versions:

k=1:2^input('')-1;k(arrayfun(@(k)sum(~~diff(dec2bin(k)+0))>1,k))

for k=1:2^input('')-1;if sum(~~diff(dec2bin(k)+0))>1;disp(k);end;end

for k=1:2^input('')-1;if sum(~~conv(dec2bin(k)+0,[-1,1],'v'))>1;disp(k);end;end
\$\endgroup\$
6
\$\begingroup\$

JavaScript (ES7), 89 85 72 69 62 bytes

Holy cow, creating ranges in JS is not easy. Perhaps it would be shorter with an actual for loop. Nope, I lied; it's actually a bit longer. Oh well. I guess I'll just have to settle for 27 bytes saved. (7 thanks to Mwr247!)

x=>[for(a of Array(1<<x).keys())if(/01/.test(a.toString(2)))a]

Works properly in the latest versions of Firefox, but probably not in any other browser. Try it out:

<!--                               Try the test suite below!                              --><strong id="bytecount" style="display:inline; font-size:32px; font-family:Helvetica"></strong><strong id="bytediff" style="display:inline; margin-left:10px; font-size:32px; font-family:Helvetica; color:lightgray"></strong><br><br><pre style="margin:0">Code:</pre><textarea id="textbox" style="margin-top:5px; margin-bottom:5px"></textarea><br><pre style="margin:0">Input:</pre><textarea id="inputbox" style="margin-top:5px; margin-bottom:5px">5</textarea><br><button id="testbtn">Test!</button><button id="resetbtn">Reset</button><br><p><strong id="origheader" style="font-family:Helvetica; display:none">Original Code Output:</strong><p><div id="origoutput" style="margin-left:15px"></div><p><strong id="newheader" style="font-family:Helvetica; display:none">New Code Output:</strong><p><div id="newoutput" style="margin-left:15px"></div><script type="text/javascript" id="golfsnippet">var bytecount=document.getElementById("bytecount");var bytediff=document.getElementById("bytediff");var textbox=document.getElementById("textbox");var inputbox=document.getElementById("inputbox");var testbtn=document.getElementById("testbtn");var resetbtn=document.getElementById("resetbtn");var origheader=document.getElementById("origheader");var newheader=document.getElementById("newheader");var origoutput=document.getElementById("origoutput");var newoutput=document.getElementById("newoutput");textbox.style.width=inputbox.style.width=window.innerWidth-50+"px";var _originalCode="x=>[for(a of Array(1<<x).keys())if(/01/.test(a.toString(2)))a]";function getOriginalCode(){if(_originalCode!=null)return _originalCode;var allScripts=document.getElementsByTagName("script");for(var i=0;i<allScripts.length;i++){var script=allScripts[i];if(script.id!="golfsnippet"){originalCode=script.textContent.trim();return originalCode}}}function getNewCode(){return textbox.value.trim()}function getInput(){try{var inputText=inputbox.value.trim();var input=eval("["+inputText+"]");return input}catch(e){return null}}function setTextbox(s){textbox.value=s;onTextboxChange()}function setOutput(output,s){output.innerHTML=s}function addOutput(output,data){output.innerHTML+='<pre style="background-color:'+(data.type=="err"?"lightcoral":"lightgray")+'">'+escape(data.content)+"</pre>"}function getByteCount(s){return(new Blob([s],{encoding:"UTF-8",type:"text/plain;charset=UTF-8"})).size}function onTextboxChange(){var newLength=getByteCount(getNewCode());var oldLength=getByteCount(getOriginalCode());bytecount.innerHTML=newLength+" bytes";var diff=newLength-oldLength;if(diff>0){bytediff.innerHTML="(+"+diff+")";bytediff.style.color="lightcoral"}else if(diff<0){bytediff.innerHTML="("+diff+")";bytediff.style.color="lightgreen"}else{bytediff.innerHTML="("+diff+")";bytediff.style.color="lightgray"}}function onTestBtn(evt){origheader.style.display="inline";newheader.style.display="inline";setOutput(newoutput,"");setOutput(origoutput,"");var input=getInput();if(input===null){addOutput(origoutput,{type:"err",content:"Input is malformed. Using no input."});addOutput(newoutput,{type:"err",content:"Input is malformed. Using no input."});input=[]}doInterpret(getNewCode(),input,function(data){addOutput(newoutput,data)});doInterpret(getOriginalCode(),input,function(data){addOutput(origoutput,data)});evt.stopPropagation();return false}function onResetBtn(evt){setTextbox(getOriginalCode());origheader.style.display="none";newheader.style.display="none";setOutput(origoutput,"");setOutput(newoutput,"")}function escape(s){return s.toString().replace(/&/g,"&amp;").replace(/</g,"&lt;").replace(/>/g,"&gt;")}window.alert=function(){};window.prompt=function(){};function doInterpret(code,input,cb){var workerCode=interpret.toString()+";function stdout(s){ self.postMessage( {'type': 'out', 'content': s} ); }"+" function stderr(s){ self.postMessage( {'type': 'err', 'content': s} ); }"+" function kill(){ self.close(); }"+" self.addEventListener('message', function(msg){ interpret(msg.data.code, msg.data.input); });";var interpreter=new Worker(URL.createObjectURL(new Blob([workerCode])));interpreter.addEventListener("message",function(msg){cb(msg.data)});interpreter.postMessage({"code":code,"input":input});setTimeout(function(){interpreter.terminate()},1E4)}setTimeout(function(){getOriginalCode();textbox.addEventListener("input",onTextboxChange);testbtn.addEventListener("click",onTestBtn);resetbtn.addEventListener("click",onResetBtn);setTextbox(getOriginalCode())},100);function interpret(code,input){window={};alert=function(s){stdout(s)};window.alert=alert;console.log=alert;prompt=function(s){if(input.length<1)stderr("not enough input");else{var nextInput=input[0];input=input.slice(1);return nextInput.toString()}};window.prompt=prompt;(function(){try{var evalResult=eval(code);if(typeof evalResult=="function"){var callResult=evalResult.apply(this,input);if(typeof callResult!="undefined")stdout(callResult)}}catch(e){stderr(e.message)}})()};</script>

(Snippet taken from this page)

Suggestions welcome!

\$\endgroup\$
  • \$\begingroup\$ You can use .keys() instead of .fill() and a instead of i to tie mine for 62: x=>[for(a of Array(1<<x).keys())if(/01/.test(a.toString(2)))a] \$\endgroup\$ – Mwr247 Oct 22 '15 at 20:55
  • \$\begingroup\$ @Mwr247 Thanks! I wonder if it's possible in under 62... :) \$\endgroup\$ – ETHproductions Oct 22 '15 at 23:30
6
\$\begingroup\$

Haskell, 68 61 53 bytes

Improvement from Damien

g x|x`mod`4==1=x>4|2>1=g$x`div`2
a x=filter g[1..2^x]

History:

This fixes the bug(Switched == and =, and square instead of power of two). And replace true with 2>1 and false with 1>2. Also thanks to point out that 2^x is always fail. Thanks to Thomas Kwa and nimi

g x|x<5=1>2|x`mod`4==1=2>1|2>1=g$x`div`2
a x=filter g[1..2^x]

Originally

g x|x<5=False|x`mod`4=1==True|2>1=g$x`div`2
a x=filter g[1..(x^2-1)]

If it have to be full program,

g x|x<5=False|x`mod`4==1=True|2>1=g$x`div`2
main=interact$show.a
a x=filter g[1..2^(read x)]
\$\endgroup\$
  • 1
    \$\begingroup\$ Lambdas are fine, since OP didn't specify writing a named function or program. By the way, welcome to PPCG! \$\endgroup\$ – lirtosiast Oct 22 '15 at 15:29
  • 1
    \$\begingroup\$ I think you mean 1..(2^x-1) which can just be 1.. (2^x) since 2^x always fails. \$\endgroup\$ – lirtosiast Oct 22 '15 at 16:45
  • \$\begingroup\$ You can replace the constants False and True with 1>2 and 1<2. No need for the parentheses around 2^x-1. (BTW: you have a typo: it must be 4==1=True). \$\endgroup\$ – nimi Oct 22 '15 at 17:56
  • \$\begingroup\$ Thanks for typo correction. It was late night in my time. \$\endgroup\$ – Akangka Oct 23 '15 at 5:29
  • \$\begingroup\$ nice tricks!I think you can reduce g to: g x|xmod4==1=x>4|2>1=g$xdiv2 \$\endgroup\$ – Damien Oct 23 '15 at 11:47
5
\$\begingroup\$

APL, 34 27 bytes

{0~⍨{⍵×2<+/2≢/⍵⊤⍨⍵/2}¨⍳2*⍵}

This creates an unnamed monadic function that accepts an integer on the right and returns an array.

Explanation:

                     }¨⍳2*⍵}  ⍝ For each integer from 1 to 2^input...
              ⍵⊤⍨⍵/2         ⍝ Get the binary representation as a vector
           2≢/                ⍝ Pairwise non-match, yielding a boolean vector
       2<+/                   ⍝ Check whether the number of trues is >2
     ⍵×                       ⍝ Yield the integer if so, otherwise 0
{0~⍨{                         ⍝ Remove the zeros from the resulting array

Saved 7 bytes thanks to Dennis!

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

R, 55 47 bytes

(with some help from @Alex.A)

cat(grep("10+1",R.utils::intToBin(1:2^scan())))

R doesn't have a built in function to display converted numbers in a convenient way, so I'm using R.utils::intToBin for this, while all the rest is pretty much just report the location of the matched regex expression and print to STDOUT while separated by a space.

\$\endgroup\$
  • \$\begingroup\$ I think the default separator for cat is a space, so you could omit ,sep="," entirely, saving 7 bytes. \$\endgroup\$ – Alex A. Oct 21 '15 at 22:45
  • \$\begingroup\$ @AlexA. yeah, so can I use a space here as a sep? I wasn't sure \$\endgroup\$ – David Arenburg Oct 21 '15 at 22:47
  • 1
    \$\begingroup\$ The OP said a delimiter of your choice, so I think a space seems reasonable enough. :) \$\endgroup\$ – Alex A. Oct 21 '15 at 22:48
  • \$\begingroup\$ Does this really need the cat function? without it, it the output will be tab delimited. The left hand counter is part of the UI, if you write it to a file this won't be included so it's not part of the output. \$\endgroup\$ – freekvd Oct 23 '15 at 12:02
  • \$\begingroup\$ @freekvd without it won't print to STDOUT, Something about the silly rules of this site. \$\endgroup\$ – David Arenburg Oct 23 '15 at 12:18
4
\$\begingroup\$

CJam, 14

2qi#{2b2,#)},p

3 bytes shorter thanks to Dennis. Try it online

\$\endgroup\$
  • \$\begingroup\$ How about 2be`,2>. \$\endgroup\$ – jimmy23013 Oct 21 '15 at 23:27
  • 2
    \$\begingroup\$ 2be`2> and 2,#) should work as well. Also, the OP has clarified that the output can be printed in list form. \$\endgroup\$ – Dennis Oct 22 '15 at 0:06
4
\$\begingroup\$

JavaScript (ES6), 69 68 67 62 bytes

a=>[...Array(1<<a).keys()].filter(i=>/01/.test(i.toString(2)))

Today I discovered a new shorter way to dynamically fill arrays without the use of fill or map. Doing x=>[...Array(x).keys()] will return an array of range 0 to x. If you want to define your own range/values, use x=>[...Array(x)].map((a,i)=>i), as it's just a few bytes longer.

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

Java, 214 165 155 154 148 141 110 bytes

This submission exploits the fact that a binary string representation of a number in Java never has a leading zero. If the string "01" appears in the binary representation of a number, that must mark the second occurrence of the number "1".

Golfed:

String f(int l){String r="";for(long i=5;i<1L<<l;++i)if(Long.toString(i,2).contains("01"))r+=i+", ";return r;}

Ungolfed:

public class NumbersWithMultipleRunsOfOnes {

  public static void main(String[] a) {
    // @formatter:off
    String[][] testData = new String[][] {
      { "3", "5" },
      { "4", "5, 9, 10, 11, 13" },
      { "5", "5, 9, 10, 11, 13, 17, 18, 19, 20, 21, 22, 23, 25, 26, 27, 29" }
    };
    // @formatter:on

    for (String[] data : testData) {
      System.out.println("Input: " + data[0]);
      System.out.println("Expected: " + data[1]);
      System.out.print("Actual:   ");
      System.out.println(new NumbersWithMultipleRunsOfOnes().f(Integer.parseInt(data[0])));
      System.out.println();
    }
  }

  // Begin golf
  String f(int l) {
    String r = "";
    for (long i = 5; i < 1L << l; ++i)
      if (Long.toString(i, 2).contains("01")) r += i + ", ";
    return r;
  }
  // End golf
}

Program output (remember, trailing delimiters are acceptable):

Input: 3
Expected: 5
Actual:   5, 

Input: 4
Expected: 5, 9, 10, 11, 13
Actual:   5, 9, 10, 11, 13, 

Input: 5
Expected: 5, 9, 10, 11, 13, 17, 18, 19, 20, 21, 22, 23, 25, 26, 27, 29
Actual:   5, 9, 10, 11, 13, 17, 18, 19, 20, 21, 22, 23, 25, 26, 27, 29, 
\$\endgroup\$
  • \$\begingroup\$ Couln't you use int for the counter variable? \$\endgroup\$ – flawr Oct 21 '15 at 21:23
  • \$\begingroup\$ All integer types in Java are unsigned. In order to work with a 32 bit positive integer, a 64 bit long is required. Furthermore, using an int would actually increase the size of the code due to referencing the Integer wrapper class which does the number parsing. I think the likely place to save space would be the regex, but my testing showed I have to have leading and trailing .* \$\endgroup\$ – user18932 Oct 21 '15 at 21:28
  • \$\begingroup\$ Oh right, but I thought you could use the Long wrapper with int? (Well not in this case but generally?) \$\endgroup\$ – flawr Oct 21 '15 at 21:34
  • \$\begingroup\$ Yes, the int will promote to long when used as a parameter with Long. In this case though there is not really any way to use an int because of the sign bit, and Integer is longer than Long. Still, I have found a few ways to squeeze some extra space out of a language as verbose as Java. \$\endgroup\$ – user18932 Oct 21 '15 at 21:38
  • \$\begingroup\$ Can you use new Long() instead of Long.parseLong()? \$\endgroup\$ – Ypnypn Oct 21 '15 at 23:57
4
\$\begingroup\$

C (gcc), 111 99 bytes

long i,x;main(a,b)char**b;{for(;++i<1L<<atol(b[1]);x>>ffsl(~x)-1&&printf("%ld,",i))x=i>>ffsl(i)-1;}

Try it online!

12 bytes shaved of thanks to @ceilingcat!

Ungolfed:

int main(int a, char **b) {
  for(long i = 0, x = 0; ++i < (1LL << atol(b[1])); ) {
    x = i >> (ffsl(i) - 1);
    if (x >> (ffsl(~x) - 1))
      printf("%ld,", i);
  }
}

The function ffsl() gives you the index of the first bit that is set in a long integer. So we loop from i = 1 to 2^number_of_bits. We set x to i shifted right until we have removed all consecutive zero bits on the least significant end. Then, we shift x right until we have removed all consecutive 1 bits at the least signficant end. If the result is still non-zero, we found a match.

\$\endgroup\$
  • 2
    \$\begingroup\$ I've gotta say that I really like that someone did a bit manipulation answer rather than a "convert to string and regex" approach. \$\endgroup\$ – user12166 Oct 22 '15 at 1:45
  • \$\begingroup\$ @MichaelT I wonder if there's a short olution using only primitive bitwise operations. \$\endgroup\$ – lirtosiast Oct 22 '15 at 1:50
  • \$\begingroup\$ @ThomasKwa That might be something to do as a code-challenge. \$\endgroup\$ – user12166 Oct 22 '15 at 1:54
  • \$\begingroup\$ Interesting. You can also write the test like this: if (popcount(i ^ (i*2))>3), and expand popcount() to a series of bitwise ANDs and shift operations. But that would result in quite long code. \$\endgroup\$ – G. Sliepen Oct 22 '15 at 6:57
  • 1
    \$\begingroup\$ @ThomasKwa y=x|(x-1) to turn on all rightmost 0 bits. Then z=y&(y+1) to turn off all trailing 1 bits. If z is non-zero, then the original number had more than one run. \$\endgroup\$ – Alchymist Oct 26 '15 at 14:41
3
\$\begingroup\$

JavaScript (ES6) 76

f=n=>Array(1<<n).fill().map((_,x)=>/01/.test(x.toString(2))?x+',':'').join``

//TEST
for(i=1;i<16;i++)O.innerHTML+=i+' -> '+f(i)+'\n'
<pre id=O></pre>

\$\endgroup\$
  • \$\begingroup\$ @DLosc no, the result would be something like ,,,,,5,,,,9,10,11,,13,,,,17,18,19,20,21,22,23,,25,26,27,,29,, \$\endgroup\$ – edc65 Oct 22 '15 at 7:45
3
\$\begingroup\$

K5, 19 bytes

This operates along similar principles as Dennis' solution, but with fewer builtins to take advantage of.

{&2<+/'~0=':'+!x#2}

First, generate a series of binary x-tuples (+!x#2), then for each tuple find every point that a digit does not match the previous if we treat the -1st element of the list as 0 for this purpose (~0=':'). Our solutions are where two is less than the sum of each run count. (&2<+/').

Showing each intermediate step is clearer:

  4#2
2 2 2 2

  !4#2
(0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1)

  +!4#2
(0 0 0 0
 0 0 0 1
 0 0 1 0
 0 0 1 1
 0 1 0 0
 0 1 0 1
 0 1 1 0
 0 1 1 1
 1 0 0 0
 1 0 0 1
 1 0 1 0
 1 0 1 1
 1 1 0 0
 1 1 0 1
 1 1 1 0
 1 1 1 1)

  ~0=':'+!4#2
(0 0 0 0
 0 0 0 1
 0 0 1 1
 0 0 1 0
 0 1 1 0
 0 1 1 1
 0 1 0 1
 0 1 0 0
 1 1 0 0
 1 1 0 1
 1 1 1 1
 1 1 1 0
 1 0 1 0
 1 0 1 1
 1 0 0 1
 1 0 0 0)

  +/'~0=':'+!4#2
0 1 2 1 2 3 2 1 2 3 4 3 2 3 2 1

  2<+/'~0=':'+!4#2
0 0 0 0 0 1 0 0 0 1 1 1 0 1 0 0

  &2<+/'~0=':'+!4#2
5 9 10 11 13

And all together:

  {&2<+/'~0=':'+!x#2}'3 4 5 
(,5
 5 9 10 11 13
 5 9 10 11 13 17 18 19 20 21 22 23 25 26 27 29)
\$\endgroup\$
2
\$\begingroup\$

Pip, 13 + 1 = 14 bytes

Takes input from the command line and uses the -s flag for spaces between output numbers.

01NTB_FI,2**a

Pretty straightforward: build range(2**a) and filter on lambda _: "01" in toBinary(_). I was pretty happy about thinking up the 01 idea independently. No quotes are needed around 01 because it scans as a numeric literal (numbers and strings are the same type in Pip).

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

Julia, 40 bytes

n->filter(i->count_ones(i$i>>1)>2,1:2^n)

This uses a somewhat different approach to the other Julia solution - rather than doing a string search for "01" in the bit string, it uses some mathematics to determine whether the number satisfies the condition.

i$i>>1 will have ones only in the places where the digit changes from zero to one, or one to zero. As such, there must be at least three ones for i to switch back and forth between zero and one enough times. count_ones finds the number of ones, and then filter removes the ones that don't have enough ones.

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

C++, 197 188 141 bytes

Note: this was written and tested using MSVC++ 2013. It appears that #includeing <iostream> includes all of the necessary C headers to make this work. It also appears that the code is no longer truly C++, but compiling using C++ allows that header trick which reduces the code size compared to including a bunch more C headers.

Using printf instead of cout also saves a couple bytes.

Golfed:

#include<iostream>
int main(int a,char**b){char c[34];for(long i=5;i<1L<<atol(b[1]);++i){_ltoa(i,c,2);if(strstr(c,"01"))printf("%ld\n",i);}}

Ungolfed:

#include <iostream>
int main(int a, char **b) {
  char c[34];
  for (long i = 5; i < 1L << atol(b[1]); ++i) {
    _ltoa(i, c, 2);
    if (strstr(c, "01"))
      printf("%ld\n", i);
  }
}
\$\endgroup\$
  • \$\begingroup\$ Yoiu can use '\n' instead of std::endl (in general), or ',' since any separator is valid and a trailing one is fine. \$\endgroup\$ – G. Sliepen Oct 22 '15 at 0:10
  • \$\begingroup\$ Instead of regexs, you could just do it with strstr(c,"01"). \$\endgroup\$ – G. Sliepen Oct 22 '15 at 0:14
  • \$\begingroup\$ @G.Sliepen thanks! I honestly just copied my Java solution and converted to C++, but the simple solution is often best. I should probably do something similar with Java now. \$\endgroup\$ – user18932 Oct 22 '15 at 1:32
  • \$\begingroup\$ Two small errors: 1<<atol(b[1]) should be 1L<<atol(b[1]), otherwise the result of that expression will be a signed 32 bit integer, which means the code will only run up to 2^30. The printf should use %ld to print numbers between 2^31 and 2^32 correctly. \$\endgroup\$ – G. Sliepen Oct 22 '15 at 6:45
2
\$\begingroup\$

Perl 5, 55 53 49 47 41 bytes

sprintf("%b",$_)=~/01/&&say for 0..2**<>

54 52 48 46 40 bytes, plus one for the -E flag instead of -e.


Thanks to xnor for the hint about using /01/ instead of /10+1/, which saved two bytes.

Thanks to Dennis for the advice to use <> instead of $ARGV[0], which saved six bytes.

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

C, 84 81 bytes

long i,j,k;main(){for(scanf("%ld",&j);++i<1L<<j;k&k+1&&printf("%ld ",i))k=i|i-1;}

This is based on the comments I made on another C answer to this question about the possibility of using simple bitwise operators. It works by switching all trailing 0 bits to 1 in the statement i|(i-1). Then it switches all trailing 1 bits to 0 using k&(k+1). This will result in a zero if there is only one run of ones and non-zero otherwise. I do make the assumption that long is 64-bit but could correct this at the expense of three bytes by using int64_t instead.

Ungolfed

long i,j,k;
main()
{
    for(scanf("%ld",&j);++i<1L<<j;)
    {
        k=i|(i-1);
        if((k&(k+1)) == 0)
            printf("%d ",i);
    }
}
\$\endgroup\$
  • \$\begingroup\$ int64_t is only defined if you #include<stdint.h>. ensuring 64 bit operation requires long long type at a cost of 5 bytes. \$\endgroup\$ – chqrlie Oct 29 '15 at 10:55
  • \$\begingroup\$ Note that you invoke undefined behaviour passing long i for %d format. Note also that () are superfluous for the & and | operators. Fixing this saves 3 bytes! long i,j,k;main(){for(scanf("%ld",&j);++i<1L<<j;k&k+1&&printf("%ld ",i))k=i|i-1;} \$\endgroup\$ – chqrlie Oct 29 '15 at 10:57
  • \$\begingroup\$ @chqrlie All very good points. Thank you. \$\endgroup\$ – Alchymist Oct 29 '15 at 16:08
1
\$\begingroup\$

Pyth, 20 17 16 bytes

f:.BT"10+1"ZU^2Q

Live demo.

\$\endgroup\$
  • \$\begingroup\$ You can simply match "01". Except for 0, the binary repr. will always start with a 1. \$\endgroup\$ – Dennis Oct 22 '15 at 0:08
1
\$\begingroup\$

Python 2.7, 89 bytes

print[i for i in range(1,2**input())if[n[:1]for n in bin(i)[2:].split("0")].count("1")-1]

I think this could be golfed a bit.

\$\endgroup\$
  • \$\begingroup\$ @mbomb007 I tried that, it didn't work. \$\endgroup\$ – Loovjo Oct 21 '15 at 20:57
  • \$\begingroup\$ @mbomb007 Are you using Python 2.7? \$\endgroup\$ – Loovjo Oct 21 '15 at 21:03
  • \$\begingroup\$ Does it matter which version of 2.7? I run it on repl.it (2.7.2) and it doesn't work, but Ideone (2.7.10) does. It might just be a bug in repl.it though, not necessarily a version difference. \$\endgroup\$ – mbomb007 Oct 21 '15 at 21:29
  • \$\begingroup\$ Your program incorrectly prints 0 in the output. \$\endgroup\$ – mbomb007 Oct 21 '15 at 21:33
  • \$\begingroup\$ Also print[i for i in range(2**input())if[n[:1]for n in bin(i)[2:].split("0")].count("1")-1] is two bytes shorter. But with the fix for 0 would be the same length (89), if you use range(1,2**input()). \$\endgroup\$ – mbomb007 Oct 21 '15 at 21:35
1
\$\begingroup\$

TI-BASIC, 34 32 30 bytes

For a TI-83+/84+ series calculator.

For(X,5,e^(Ans
If log(sum(2=int(4fPart(X/2^randIntNoRep(1,Ans
Disp X
End

For a number to contain two runs of 1s, it must contain two 10s when we tack a trailing zero onto the binary representation.

Rather than generate the binary representation and check for a 10, we test pairs of bits mathematically by using remainder by 4 (int(4fPart(), which will give 2 where there is a 10. Because we don't care about order, randIntNoRep( is the shortest way to generate the list of exponents.

We use log( to check for the number of runs:

  • If there are at least 2 runs, then the log( is positive, and the number is displayed.

  • If there is one run, then the log( is 0, and the number is not displayed.

  • If there are no runs (which first happens at X=2^Ans), then log( throws an ERR:DOMAIN, stopping the output at exactly the right point.

We use e^(Ans as the ending argument of the For( loop—it's always greater than 2^Ans, but e^( is a single token, so it's one byte shorter.

Input/output for N=4:

4:prgmRUNSONES
               5
               9
              10
              11
              13

Then the calculator throws an error; the error screen looks like this:

ERR:DOMAIN
1:Quit
2:Goto

When 1 is pressed, the home screen is displayed again:

4:prgmRUNSONES
               5
               9
              10
              11
              13
           Error

TI calculators store all numbers in a BCD float with 14 digits of precision, not an int or binary float. Therefore, divisions by powers of two greater than 2^14 may not be exact. While I have verified that the trickiest numbers, 3*2^30-1 and 2^32-1, are handled correctly, I have not ruled out the possibility of rounding errors. I would however be surprised if there were errors for any input.

\$\endgroup\$
  • \$\begingroup\$ How do you count 32 bytes? It looks like 70 to me (including the newlines). \$\endgroup\$ – msh210 Oct 22 '15 at 16:46
  • \$\begingroup\$ TI-BASIC is tokenized; it uses a proprietary character encoding in which all of these commands are one byte each and the others are two. It is the community consensus to score by this encoding-- see meta.codegolf.stackexchange.com/a/4764/39328 for details. \$\endgroup\$ – lirtosiast Oct 22 '15 at 16:52
  • \$\begingroup\$ Oh, cool. Thanks FYI. \$\endgroup\$ – msh210 Oct 22 '15 at 16:55
1
\$\begingroup\$
  • this doesnt beat flawr's answer but i couldnt resist the charm of the question

matlab(90)(70)

j=input('');for l=2:j-1,a=1;for k=l:-1:2,a=a+2^k;a:a+2^(k-1)-2,end,end

execution

4

ans =

5

ans =

9    10    11

ans =

13

principle

  • The series of numbers are a result of consequent strip of 1's, which does mean f(n,l)=2^l+2^(l+1)+....2^n

Any number taken from the interval ]f(n,l),f(n,l)+2^(l-1)[ where l>1 verifies this condition, so the outcome is a result of the negation of this series in terms of n.

x=1

x=x+1=01,

x=x+2^0=11,

x=x+1=001,

x=x+2^1=011,

x=x+2^0=111,

x=x+1=0001,

x=x+2^2=0011,

x=x+2^1=0111,

x=x+2^0=0111,

x=x+1=1111 ...

x+1, x=x+2^n, x=x+2^(n-1)...x=x+2^0

My program prints the range between each two lines (if exists)


Edit: unfortunately that doesnt make it golfed more but i wanted to add another approach of proceding this idea

after a period of struggle i succeded to find a mathematical representation for this series which is:

2^l(0+1+2^1+...2^k) with l+k < n

=2^l(2^k-1)

score=90

@(n)setdiff(0:2^n-1,arrayfun(@(x)2^mod(x,(n+1)-fix(x/(n+1)))*(2^fix(x/(n+1))-1),0:(n+1)^2))
\$\endgroup\$
1
\$\begingroup\$

C, 103 102 bytes

long i,x;main(int a,char**b){for(;++i<1L<<atoi(b[1]);)for(x=i;x>4&&(x%4!=1||!printf("%ld,",i));x/=2);}

Expanding (actually contracting) on G.Sliepen entry, taking advantage of xnor remark on the 01 pattern in the binary representation, but using only standard functions and some bit twiddling.

Ungolfed version:

long i, x;
main(int a, char**b) {
    for (; ++i < 1L << atoi(b[1]);) {
        for (x = i; x > 4 && (x % 4 != 1 || !printf("%ld,", i)); x /= 2)
            ;
    }
}

The inner loop scans i for the binary pattern 01 by iteratively shifting x to the right as long as it has 3 bits left. printf returns the number of characters printed, hence never 0, so the inner loop test fails after the printf, avoiding the need for a break statement.

C++, 129 128 bytes

Adapting the same idea, the C++ variant is here:

#include<iostream>
long i,x;int main(int a,char**b){for(;++i<1L<<atoi(b[1]);)for(x=i;x>4&&(x%4!=1||!(std::cout<<i<<','));x/=2);}

Technically, I should make i a long long to ensure 64 bit operation and compute upto 2^32 for an extra 5 bytes, but modern platforms have 64 bit ints.

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

JavaScript ES6, 60 bytes

Code

n=>[...Array(1<<n).keys()].filter(g=x=>x>4?x%4==1|g(x>>1):0)

Try it online!

Explanation

[...Array(1<<n).keys()]                                          Create an array of numbers from 0 to 2^n-1
                       .filter(                                  Find the numbers which meet criteria
                               g=x=>x>4?                  :0     If x is less than or equal to four return zero (false/invalid)
                                        x>4?x%4==1|              If the binary pattern ends with 01 return one (true/valid)
                                                   g(x>>1)       Otherwise bitshift right by one and try again
\$\endgroup\$
0
\$\begingroup\$

C (sort of - compiles with warnings in GCC) - 103

This uses no library functions of any kind except printf. You can see by looking at this that no effort has been spared to make it standards compliant or avoid UB.

x,c;main(n,v){n--;for(;c<1<<n;c++)for(v=0;v<32;v++)if(c&1<<v){if(x&&x<v&&printf("%d ",c))break;x=v+1;}}

To make it compliant you would need to do lots of things like including stdio.h which would be against the spirit of making it as small as possible.

If anyone has suggestions for making it shorter please let me know.

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

PowerShell, 80 bytes

while([Math]::Pow(2,$args[0])-gt$n++){$n|?{[Convert]::ToString($n,2)-match"01"}}
\$\endgroup\$
0
\$\begingroup\$

Python, 44 Bytes

Okay, this could probably be shorter but it's my first codegolf:

x=1
while True:
    if '01' in bin(x):
        print(x)
    x+=1

Think this answers the question, please don't down vote if it doesn't, just post whats wrong with it below.

\$\endgroup\$
  • 1
    \$\begingroup\$ You need to take input (input() is ideal) to get n, and then only count up to 2^n-1, rather than looping indefinitely. Also, you can use 1 and 2 spaces for the nesting, rather than 4 and 8, and using map or a list comprehension would probably shorten your code tremendously. \$\endgroup\$ – Mego Oct 23 '15 at 13:50
0
\$\begingroup\$

another different matlab answer of good score.

matlab 60(57)

@(n)find(mod(log2(bitcmp(1:2^n,fix(log2(1:2^n)+1))+1),1))

execution

>> @(n)find(mod(log2(bitcmp(1:2^n,fix(log2(1:2^n)+1))+1),1))

ans =

@(n)find(mod(log2(bitcmp(1:2^n,fix(log2(1:2^n)+1))+1),1))

>> ans(5)

ans =

 5     9    10    11    13    17    18    19    20    21    22    23    25    26    27    29

  • The idea is picking up numbers x where the binary representation of -(x)+1 doesnt contain only one occurence of 1

example:

0000111 is rejected because ~x=1111,~x+1=00001 contains one digit=1

0100111 is accepted because ~x=1011,~x+1=0111 contains many 1's

\$\endgroup\$

Your Answer

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