Given a binary number as input through any means, "simplify" the number using a full program or a function.


  • binary is a number in binary that is over 0.


Take the input, convert it to base 10 without using a builtin, then if that number contains only 1s and 0s, convert it into a base 10 number as if it were another binary number. Repeat the process until the number cannot be read in binary and output that number.

Other information

  • If the input is 1, simply output 1. Your program should not go on infinitely simplifying 1.

  • This is code golf, so shortest answer in bytes by Tuesday (November 17th) wins.

  • If anything is confusing, leave a comment specifying what I need to clear up and I will edit it accordingly.

  • Builtins for base conversion are not allowed.


     Input | Output

         1 | 1
      1010 | 2
      1011 | 3
   1100100 | 4
   1100101 | 5
1111110011 | 3
  • 4
    \$\begingroup\$ Could use a couple test cases. \$\endgroup\$
    – isaacg
    Commented Nov 11, 2015 at 2:10
  • \$\begingroup\$ Is the input an ASCII string, or actually 1's and 0's? \$\endgroup\$ Commented Nov 11, 2015 at 2:15
  • \$\begingroup\$ @TomCarpenter 1s and 0s. \$\endgroup\$ Commented Nov 11, 2015 at 2:20
  • 1
    \$\begingroup\$ Are implicit base conversions allowed? e.g. sprintf("%d",n); in c effectively converts n to a base 10 string \$\endgroup\$ Commented Nov 11, 2015 at 2:48
  • 1
    \$\begingroup\$ @The_Basset_Hound To clarify Digital Trauma's question, is turning a number into its standard string representation, in base 10, allowed? I wouldn't consider it a base conversion, more of a typecast. \$\endgroup\$
    – isaacg
    Commented Nov 11, 2015 at 2:58

23 Answers 23


Pyth, 20 16 bytes


4 bytes thanks to Jakube

Half of the code (u+yNsTG0) is simply the base conversion code.

Test Suite

                    z = input() (The string of 1s and 0s)
                    T = 10
u              z    Apply until the value stops changing, starting with z
                    G is the current value, a string of 0s and 1s.
 ?-GT               If G - T, e.g., G with the digits 1 and 0 removed is not empty,
     G              Return G, to end the iteration.
       u     G0     Else, reduce over G with initial value 0.
         yN         Double the running total
        +  sT       and add the next digit, cast to an int.
      `             Convert to string.

The input 1 is handled by the fact that u notices the value has stopped changing.

  • 4
    \$\begingroup\$ Congratulations, you outgolfed Dennis! For the moment... \$\endgroup\$ Commented Nov 11, 2015 at 2:51
  • 9
    \$\begingroup\$ @CᴏɴᴏʀO'Bʀɪᴇɴ The secret is Pyth. \$\endgroup\$
    – isaacg
    Commented Nov 11, 2015 at 2:52

CJam, 24 23 bytes


Try it online in the CJam interpreter.

How it works

q                        Read all input.
 {                   }g  Do:
  :~                       Evaluate each character. Maps '0' -> 0 and '1' -> 1.
    {    }*                Fold; for each integer but the first:
     1$                      Copy the second-topmost integer.
       ++                    Add all three integers on the stack.
           s__             Cast to string and push two copies.
              ,(           Calculate string length and subtract 1.
                As         Push the string "10".
                  *        Repeat the string length-1 times.
                   -       Remove its elements from the string representation
                           of the integer.
                    !      Apply logical NOT.
                         If `!' pushed 1, repeat the loop.
  • \$\begingroup\$ Do you have to repeat the "10" string length-1 times, or could you skip the decrement? \$\endgroup\$
    – DLosc
    Commented Nov 11, 2015 at 3:34
  • \$\begingroup\$ Subtracting 1 from the length turns "10" into "" if the integer has a single digit. This makes sure the code doesn't get into an infinite loop. \$\endgroup\$
    – Dennis
    Commented Nov 11, 2015 at 3:35
  • 2
    \$\begingroup\$ Fascinating, captain. }:^| \$\endgroup\$
    – DLosc
    Commented Nov 11, 2015 at 3:37

Pip, 28 27 bytes


Takes input as a command-line argument. We want to loop until a=1 or a contains some character(s) besides 0's and 1's. This latter condition is tested by RM'ing all characters in t = 10 from a. If there's anything left, the condition is truthy.

Inside the loop, the conversion works as follows:


              ,#a  range(len(a))
            RV     reversed
         2**       2 to the power of each element
    (^a)*          multiplied item-wise with each digit in split(a)
  $+               Sum
a:                 and assign back to a

Putting a at the end auto-prints it.

A recursive solution in 28 bytes:


Python 2, 52

f=lambda n:n>1<'2'>max(`n`)and f(n%10+2*f(n/10))or n

It's easier to think of this as two recursive functions:

g=lambda n:n and n%10+2*g(n/10)
f=lambda n:n>1<'2'>max(`n`)and f(g(n))or n

The function g converts a decimal value to binary, and the function f applies g repeatedly is long as its argument is made of digits 0 and 1 ('2'>max(`n`)) and is not 1. The golfed code collapses them into a single function by inserting the definition of g(n) for f(n), replacing the recursive call to g with f. The base case of n=0 of g is automatically handled by the check n>1.

  • \$\begingroup\$ Nice :) The only thing is that the usual problem applies - the pesky L from repr... \$\endgroup\$
    – Sp3000
    Commented Nov 11, 2015 at 7:47

Prolog, 220 212 bytes

y(B,J-M,I-N):-B in 0..1,N#=M+B*2^J,I#=J+1.
b(N,I):-N>47,N<50,I is(N-48).

p is the main function and performs the following steps (with help from b,x,y):

  • checks if current number is bigger than 1
  • converts integer to list of ascii representations of digits
  • checks that all numbers are 0 or 1
  • converts ascii list to binary integer list
  • converts binary integer list to decimal number
  • recurses
  • prints when a predicate fails.

Edit: Saved 8 bytes by unifying the p-clauses with OR.


Mathematica 107 106

With a byte saved by DLosc.

Which[d<2,1,Complement[v,{0,1}]=={},j@Fold[#+#2 2^p++&,0,Reverse@v],1<2,d])

Break the input into its digits. If the input is 1, output 1.

If the input is a number consisting of 0's and 1's, convert that to decimal and run it through again.

Otherwise, return the input.









The first step yields 1011 which in turn yields 3.

Here we test starting with 1011.




JavaScript ES6, 52

As a function. The function argument must be either a string of binary digits or a number whose decimal representation contains only 1 and 0.

Test running the snippet below in an EcmaScript 6 compliant browser - implementing arrow functions, template strings and spread operator (I use Firefox)


// To test

// Basic test cases
.forEach(t=>console.log(t[0]+' -> '+f(t[0])+' expected '+t[1]))

function longtest() {
  var o=[],i;
  for (i=1;i<1e6;i++)
    b=i.toString(2),v=f(b),v!=i?o.push(b+' '+v):0;
Click to run the long test <button onclick="longtest()">go</button>
<pre id=O></pre>

  • 2
    \$\begingroup\$ Really liking n+=+c+n for the binary conversion. So elegant... \$\endgroup\$
    – nderscore
    Commented Nov 11, 2015 at 15:14

Javascript, 132, 123 bytes

Well, it's not the best answer, but..

FYI, if an invalid input is given, it displays the same to the user.

function c(x){while(x!=0&&!/[2-9]/.test(x)){for(i=r=0;x;i++)r+=x%10*Math.pow(2,i),x=parseInt(x/10);x=r}alert(x)}c(prompt())

  • 1
    \$\begingroup\$ You could save 19 bytes by using forinstead of while and setting values directly in the statement (this also reduces some {}), discarding some ;, using ES6 function description, increment i inline. It'll look like this: c=x=>{for(r=0;x&&!/[2-9]/.test(x);x=r)for(i=0;x>0;r+=x%10*Math.pow(2,i++),x=parseInt(x/10));alert(x)};c(prompt()). \$\endgroup\$ Commented Nov 11, 2015 at 14:00
  • 1
    \$\begingroup\$ 114: function c(x){while(x^0&&!/[2-9]/.test(x)){for(i=r=0;x;i++)r+=x%10*Math.pow(2,i),x=0|x/10;x=r}alert(x)}c(prompt()) \$\endgroup\$ Commented Nov 13, 2015 at 6:03
  • \$\begingroup\$ @insertusernamehere, thanks for the suggestion, but I didn't understand the c=x=> at the start, didn't work on Chrome or Firefox console. :( @ןnɟuɐɯɹɐןoɯ, could not wrap my head around the XOR condition and the x=0|x/10‌ instead of parseInt, I've incorporated the rest of the changes. Thanks.. \$\endgroup\$ Commented Nov 16, 2015 at 5:36
  • \$\begingroup\$ @GauthamPJ I'm sorry, somehow the code got broken while copying and contained unprintable characters. Here's the correct version: c=x=>{for(r=0;x!=0&&!/[2-9]/.test(x);x=r)for(i=r=0;x;)r+=x%10*Math.pow(2,i++),x=parseInt(x/10);alert(x)};c(prompt()). It definitely runs in Firefox 42, try this fiddle. Note that this more golfed version and also your original code don't work for 1 and will run into an endless loop. c=x=> is like function c(x){} see "Arrow functions". \$\endgroup\$ Commented Nov 16, 2015 at 9:44

Mathematica, 62 59 55 48 bytes

Saved 7 bytes thanks to Martin Büttner.


R, 75 68 bytes

  • -7 bytes by rewriting if and digit extraction (pajonk)

Attempt This Online!

A recursive function: the first if-condition is checking whether the input is not 1 or 0; the second condition checks whether there are only the digits 0 or 1 in the generated on the fly K vector. Then the function is called again, with the b converted to its decimal form as the input. Outside of if In the else-clause b is output (outputted ?).


Javascript (ES7) 87 80 78 77 74 bytes

Snippet demo for supporting browsers (currently only Firefox nightly supports the exponential operator)

<input type="text" id="x" value="1111110011"><button onclick="o.innerHTML=f(x.value)">Run</button><div id="o"></div>

[...x].reverse(i=y=j=0) // reverse string as array, initialize vars
.map(z=>( // iterate over the all chatacters
    j|=z, // keep track of whether a digit higher than 1 is encountered
    y+=z*2**i++ // build decimal result from binary
j<2&y>1? // if we encountered only 1's and 0's and result > 1
    f(y+[]) // then call recursively and cast to a string
    :x // else return x

Javascript (ES6) 81 bytes

Snippet demo for supporting browsers

<input type="text" id="x" value="1111110011"><button onclick="o.innerHTML=f(x.value)">Run</button><div id="o"></div>


𝔼𝕊𝕄𝕚𝕟, 37 chars / 54 bytes


Try it here (Firefox only).

Not sure if the + operator counts as a built-in for binary conversion...


Perl 6, 67 bytes

get,{$_=0;for $^a.comb {$_+<=1;$_+=$^b};$_}...1|/<-[01]>/;say $_//1

PHP, 210 204 bytes

It's my first time posting here, so hope you guys will like it ! Even if it's obviously not the best way to write it, I'm still glad to show it off here !

The Code

<?function j($a){$c=0;if($a==1){return 1;}else{if(preg_match("#^[01]+$#",$a)){$b=strlen($a);$a=str_split($a);foreach($a as$d){$c+=($d==0?0:2**($b-1));$b--;}return j($c);}else{return$a;}}}echo j($_GET[0]);

I've made a recursive function "j" that will first check if the input is equal to 1. If so, the function returns 1 as expected, else it'll split the number in an array to calculate the decimal value, but only if the number is a binary one. If it's not, it'll return the number as is.

Ungolfed code

function j($a) {
  $c = 0;
  if ($a == 1) {
    return 1;
  else {
    if (preg_match("#^[01]+$#", $a) {
      $b = strlen($a);
      $a = str_split($a);
      foreach ($a as $d) {
        $c += ($d == 0 ? 0 : 2 ** ($b - 1));
      return j($c);
    else {
      return $a;
echo j($_GET[0]);

I've used a "foreach" statement instead of my initial "for" one, allowing me a gain of 6 bytes but I'm pretty sure there's a lot more to do.


PHP, 114 112 bytes

also works for 0. Run with -r.


count_chars($s,3) returns a string containing all characters from the string (like array_unique does for arrays). For binary numbers, this will be 0, 1 or 01. For other numbers, this will contain a digit larger than 1, so <2will return true only for binary numbers.

&$s>1 is needed for the special case 1.

The rest is straight forward: Loop through the bits with shifting the value and adding the current bit, finally copy the number (cast to string) to $s for the outer loop test.


Go, 123 bytes

func f(n int)(o int){if n<2{return n}
for i:=0;n>0;i++{o+=n%10<<i
for k:=o;k>0;k/=10{if k%10>1{return}}
return f(o)}

Attempt This Online!

A recursive function that takes in an int containing only 0s and 1s, and outputs an `int.

Ungolfed Explanation

// input is a decimal number with only 0s and 1s
func f(n int)(o int){
// return immediately if n=1
if n<2{return n}
// bin-to-dec conversion
for i:=0;n>0;i++{
// checking for non-0-or-1 digits
for k:=o;k>0;k/=10{
   // if there is one, immediately return
   if k%10>1{return}
// otherwise repeat the process
return f(o)}

Vyxal 3, 14 bytes


Try it Online!


Scala 3, 104 bytes

A port of @xor's Python 2 answer in Scala.

Golfed version. Attempt This Online!

def g(n:Int):Int=if(n<1)0 else n%10+2*g(n/10)
def f(n:Int):Int=if(n>1&&'2'>n.toString.max)f(g(n)) else n

Ungolfed version. Attempt This Online!

object Main {
  def main(args: Array[String]): Unit = {
    def g(n: Int): Int = if (n == 0) 0 else n % 10 + 2 * g(n / 10)

    def f(n: Int): Int = if (n > 1 && '2' > maxDigit(n.toString)) f(g(n)) else n

    def maxDigit(s: String): Char = s.max


Jelly, 5 chars (8 bytes)

  $      # 2 previous functions
D        # Split number into digits
 Ḅ       # Convert to binary
   ÐL    # Repeat until output matches input

I mean, obviously this still counts as a win for Dennis.


Perl 5 -p, 48 + 1 = 49 bytes


Try it online!


CoffeeScript, 92 89 bytes

f=(x)->x>1&/^[01]+$/.test(x)&&f(''+x.split('').reverse().reduce ((p,v,i)->p+v*2**i),0)||x

JavaScript (ES6), 105 101 90 bytes



Only works in ES6-compliant browsers such as Firefox and Microsoft Edge


// Snippet stuff
$(`form`).submit((e) => {
  document.getElementById(`y`).textContent = f(document.getElementById(`x`).value);
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
    <input pattern=^[01]+$ required id=x>
  <button type=submit>Go</button>
    <output id=y></output>

  • \$\begingroup\$ If you use eval, you might be able to pull off an implicit return. \$\endgroup\$ Commented Nov 11, 2015 at 5:08
  • \$\begingroup\$ 5 bytes shorter with eval and anonymous functions \$\endgroup\$
    – Downgoat
    Commented Nov 11, 2015 at 5:15
  • \$\begingroup\$ @ןnɟuɐɯɹɐןoɯ For some reason the eval'd function does not work with 1. because it doesn't enter the loop I assume \$\endgroup\$ Commented Nov 11, 2015 at 5:20
  • 1
    \$\begingroup\$ @nderscore Thanks, but recursion was 4 bytes shorter :-) \$\endgroup\$ Commented Nov 11, 2015 at 5:46

Scala, 128 bytes

def b(s:String):String=if(s.matches("[10]{2,}"))b(""+s.reverse.zipWithIndex.collect{case('1',i)=>Math.pow(2,i)}.sum.toInt)else s

Matlab (115)


  • The anonymous function is number type conversion (bin2dec)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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