Find the next 1-sparse binary number

Question

A positive integer N is K-sparse if there are at least K 0s between any two consecutive 1s in its binary representation.

So, the number 1010101 is 1-sparse whereas 101101 is not.

Your task is to find the next 1-sparse number for the given input number. For example, if the input is 12 (0b1100) output should be 16 (0b10000) and if the input is 18 (0b10010) output should be 20 (0b10100).

Smallest program or function (in bytes) wins! Standard loopholes disallowed.

• FUZxxl: "next" as in "next highest" or as in "with least absolute difference" ?
• articuno: "next" as in "next highest".
• mbomb007: What range of input needs to be handled?
• mbomb007: I'm going to assume negative numbers don't need to be.
• mbomb007: @articuno Can we create a function, or does it have to be a full program? Functions are pretty standard.

Answer 1

Pyth, 9 bytes

• Borrowing the x & (x*2) != 0 algorithm from @alephalpha
• Borrowing Pyth boilerplate from @Jakube

My first attempt at Pyth:

f!.&TyThQ

Try it here

 implicit: Q = input() 
f hQ find the first integer T >= Q + 1, 
 that satisfies the condition:
 !.&TyT T & (T * 2) is 0

Answer 2

CJam, (削除) 14 (削除ここまで) 11 bytes

3 bytes saved thanks to DigitalTrauma.

l~{)___+&}g

Test it here.

Explanation

l~ "Read and eval input.";
 { }g "Do while...";
 )_ "Increment and duplicate (call this x).";
 __+ "Get two more copies and add them to get x and 2x on the stack.";
 & "Take their bitwise AND. This is non-zero is as long as x's base-2
 representation contains '11'.";

This leaves the last number on the stack which is printed automatically at the end of the program.

Answer 3

Python 2, 44 bytes

This is a complete python program that reads in n, and prints the answer. I think it does quite well in the readability sub-competition.

n=input()+1
while'11'in bin(n):n+=1
print n

The test results:

$ echo 12 | python soln.py 
16
$ echo 18 | python soln.py 
20

Answer 4

Pyth, (削除) 12 (削除ここまで) 11 bytes

f!}`11.BThQ

Try it online: Pyth Compiler/Executor.

 implicit: Q = input() 
f hQ find the first integer T >= Q + 1, 
 that satisfies the condition:
 !}`11.BT "11" is not in the binary representation of T

• orlp: You can save a character by turning "11" into `11.
• Jakube: @orlp Thanks, should have noticed this.

Answer 5

Mathematica, (削除) 41 (削除ここまで) 30 bytes

Saved 11 bytes thanks to Martin Büttner.

#+1//.i_/;BitAnd[i,2i]>0:>i+1&

• mbomb007: Could you add a description, please?

Answer 6

Perl, 31

#!perl -p
sprintf("%b",++$_)=~/11/&&redo

Or from the command line:

 perl -pe'sprintf("%b",++$_)=~/11/&&redo' <<<"18"

Answer 7

APL, 18 bytes

1∘+⍣{~∨/2∧/⍺⊤⍨⍺⍴2}

This evaluates to a monadic function. Try it here. Usage:

 1∘+⍣{~∨/2∧/⍺⊤⍨⍺⍴2} 12
16

Explanation

1∘+ ⍝ Increment the input ⍺
 ⍣{ } ⍝ until
 ~∨/ ⍝ none of
 2∧/ ⍝ the adjacent coordinates contain 1 1 in
 ⍺⊤⍨⍺⍴2 ⍝ the length-⍺ binary representation of ⍺.

Answer 8

J, 20 characters

A monadic verb. Fixed to obey the rules.

(+1 1+./@E.#:)^:_@>:

Explanation

First, this is the verb with spaces and then a little bit less golfed:

(+ 1 1 +./@E. #:)^:_@>:
[: (] + [: +./ 1 1 E. #:)^:_ >:

Read:

 ] The argument
 + plus
 [: +./ the or-reduction of
 1 1 E. the 1 1 interval membership in
 #: the base-2 representation of the argument,
[: ( )^:_ that to the power limit of
 >: the incremented argument

The argument plus the or-reduction of the 1 1 interval membership in the base-2 representation of the argument, that to the power limit applied to the incremented argument.

I basically compute if 1 1 occurs in the base-2 representation of the input. If it does, I increment the input. This is put under a power-limit, which means that it is applied until the result doesn't change any more.

• Zgarb: Nice algorithm! It has the same length in APL: {⍵+∨/2∧/⍵⊤⍨⍵⍴2}⍣=.
• FUZxxl: @randomra Ah, I see.

Answer 9

Javascript, (削除) 25 (削除ここまで) 19

Using the fact that, for a 1-sparse binary number, x&2*x == 0:

f=x=>x++&2*x?f(x):x

Answer 10

JavaScript (ES6), 39 (削除) 43 (削除ここまで)

No regexp, no strings, recursive:

R=(n,x=3)=>x%4>2?R(++n,n):x?R(n,x>>1):n

Iterative version:

F=n=>{for(x=3;x%4>2?x=++n:x>>=1;);return n}

It's very simple, just using right shift to find a sequence of 11. When I find it, skip to next number. The recursive version is directly derived from the iterative one.

Ungolfed and more obvious. To golf, the trickiest part is merging the inner and outer loops (having to init x to 3 at start)

F = n=>{
 do {
 ++n; // next number
 for(x = n; x != 0; x >>= 1) {
 // loop to find 11 in any position
 if ((x & 3) == 3) { // least 2 bits == 11
 break;
 }
 }
 } while (x != 0) // if 11 was found,early exit from inner loop and x != 0
 return n
}

• Jacob: This %4>2 looks like some sorcery from Number Theory, can you please explain || provide a link?
• edc65: @Jacob (x%4>2) is simply ((x&3)==3), but with the operator precedence is JS you avoid the 2 brackets
• Jacob: Simple than I thought. Now with the ungolfed version it's clear. Thanks!

Answer 11

Python 2, 37 bytes

f=input()+1
while f&2*f:f+=1
print f

Used the logic x & 2*x == 0 for 1-sparse number.
Thanks to @Nick and @CarpetPython.

• ETHproductions: Why the downvote? This works perfectly fine, and is well-golfed as well.
• ETHproductions: Welcome to PPCG, btw, and nice first answer! I encourage you to continue answering challenges on the site :-)

Answer 12

JavaScript, (削除) 75 (削除ここまで) (削除) 66 (削除ここまで) 62 bytes

Thanks to Martin Büttner for saving 9 bytes and Pietu1998 for 4 bytes!

function n(a){for(a++;/11/.test(a.toString(2));a++);return a;}

How it works: it runs a for loop starting from a + 1 as long as the current number is not 1-sparse, and if it is, the loop is interrupted and it returns the current number. To check whether a number is 1-sparse, it converts it to binary and checks whether it does not contain 11.

Un-golfed code:

function nextOneSparseNumber(num) {
 for (num++; /11/.test(num.toString(2)); num++);
 return num;
}

Answer 13

Julia, 40 bytes

n->(while contains(bin(n+=1),"11")end;n)

This creates an anonymous function that accepts a single integer as input and returns the next highest 1-sparse integer. To call it, give it a name, e.g. f=n->..., and do f(12).

Ungolfed + explanation:

function f(n)
 # While the string representation of n+1 in binary contains "11",
 # increment n. Once it doesn't, we've got the answer!
 while contains(bin(n += 1), "11")
 end
 return(n)
end

Examples:

julia> f(12)
16
julia> f(16)
20

Suggestions and/or questions are welcome as always!

Answer 14

Python, (削除) 39 (削除ここまで) 33 bytes

Try it here: http://repl.it/gpu/2

In lambda form (thanks to xnor for golfing):

f=lambda x:1+x&x/2and f(x+1)or-~x

Standard function syntax (削除) turned out to be shorter than a lambda for once! (削除ここまで)

def f(x):x+=1;return x*(x&x*2<1)or f(x)

• xnor: You can shorten the lambda one to 33 bytes: f=lambda x:1+x&x/2and f(x+1)or-~x. It turns out that of you bit-shift right rather than left, you can use x/2 instead of (x+1)/2 because the difference is always in zero bits of x+1. The spec asks for a program though.
• mbomb007: I asked and he said we can do functions. Most of the answers are already.

Answer 15

><> (Fish), 31 + 3 = 34 bytes

1+:>: 4%:3(?v~~
;n~^?-1:,2-%2<

Usage:

>python fish.py onesparse.fish -v 12
16

3 bytes added for the -v flag.

Answer 16

JavaScript (ECMAScript 6), 40

By recursion:

g=x=>/11/.test((++x).toString(2))?g(x):x

JavaScript, 56

Same without arrow functions.

function f(x){return/11/.test((++x).toString(2))?f(x):x}

Answer 17

Scala, 65 bytes

(n:Int)=>{var m=n+1;while(m.toBinaryString.contains("11"))m+=1;m}

(if a named function is required, solution will be 69 bytes)

Answer 18

Perl, 16 bytes

Combining the x&2*x from various answers (I think Nick's first) with nutki's redo yields:

perl -pe'++$_&2*$_&&redo'

Tested in Strawberry 5.26.

Answer 19

Japt, 8 bytes

_&ZÑ}fUÄ

Run it online.

Answer 20

Stax, 5 bytes

╦>ù╤x

Run and debug it

It works using this procedure. The input starts on top of the stack.

• Increment and copy twice.
• Halve the top of the stack.
• Bitwise-and top two elements on the stack.
• If the result is truthy (non-zero) repeat the entire program.

Answer 21

Java, 33 bytes.

Uses the method in this answer

n->{for(;(n++&2*n)>0;);return n;}

TIO

Answer 22

Vyxal, 6 bytes

λd⋏[›x

Try it Online!

How?

λd⋏[›x
λ # Open a lambda for recursion
 d # Double
 ⋏ # Bitwise AND the doubled input with the input
 [ # If this is truthy (non-zero):
 ›x # Increment and recurse

• Jonathan Allan: 18 returns 18 but should return 20, probably due to 18 being 1-sparse itself.

Answer 23

Jelly, (削除) 7 (削除ここまで) 6 bytes

‘‘&Ḥ$¿

A monadic Link that accepts a non-negative integer and yields a (higher) positive integer, the next higher 1-sparse integer.

Try it online!

How?

Start with v=n+1. Then increment v if doubling v to shift every bit up one place and then bit-wise AND-ing that with v is non-zero (meaning v is not 1-sparse); repeat until we hit a 1-sparse number.

‘‘&Ḥ$¿ - Main Link: n e.g. 12
‘ - increment -> v=n+1 13
 ¿ - while...
 $ - ...condition: last two links as a monad - f(v):
 Ḥ - double v -> 2v
 & - (v) bit-wise AND (2v) -> is v not 1-sparse?
 ‘ - ...do: increment

Answer 24

Vyxal 3, 7 bytes

λ:d∴[ꜝx

Vyxal It Online!

Uses the same algorithm as the Vyxal 2 answer.

Alternate algorithm for 14 bytes: (Vyxal It Online!)

ÞṆİ:dZ∴Ṡɨ0=0+ꜝ­⁡​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏⁠‎⁡⁠⁣‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁤‏⁠‎⁡⁠⁢⁡‏⁠‎⁡⁠⁢⁢‏⁠‎⁡⁠⁢⁣‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁢⁤‏⁠‎⁡⁠⁣⁡‏⁠‎⁡⁠⁣⁢‏⁠‎⁡⁠⁣⁣‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁣⁤‏⁠‎⁡⁠⁤⁡‏⁠‎⁡⁠⁤⁢‏‏​⁡⁠⁡‌­
ÞṆİ # ‎⁡For every positive integer after the input:
 :dZ∴ # ‎⁢Bitwise AND it with itself doubled
 Ṡɨ0= # ‎⁣Find the index of the first result which is equal to zero
 0+ꜝ # ‎⁤and add the input to that index.
💎

Created with the help of Luminespire.

Answer 25

Ruby, 44

->(i){loop{i+=1;break if i.to_s(2)!~/11/};i}

Pretty basic. A lambda with an infinite loop and a regexp to test the binary representation. I wish that loop yielded and index number.

Answer 26

Matlab ((削除) 77 (削除ここまで) 74 bytes)

m=input('');for N=m+1:2*m
if ~any(regexp(dec2bin(N),'11'))
break
end
end
N

Notes:

• It suffices to test numbers m+1 to 2*m, where m is the input.
• ~any(x) is true if x contains all zeros or if x is empty

Answer 27

C (32 bytes)

f(int x){return 2*++x&x?f(x):x;}

Recursive implementation of the same algorithm as so many other answers.