Based on the "binary, but with twos" notation mentioned in this numberphile video, write a function that takes a single number as input and outputs all variations of that number in a "binary" system where twos are allowed.


  • Code must only be a function/method, not a full program
  • Input is an integer passed as the sole parameter to the function
  • Output is all valid variations of the input number converted to "binary, but with twos" notation
  • Output is the return value of the function, but can be in whatever format is convenient as long as it's obvious (eg, 3 ints, 3 strings, comma/space delimited string, array of ints, etc), order is unimportant
  • In the unlikely event that a language happens to contain a built-in function to achieve the result, it's disallowed
  • Shortest code in bytes is the winner

Explanation of the output

By example, if you're passed the number 9, you can convert it to binary as 1001, but if you allowed 2s in each position, you could also write it as 201 (i.e. 2*4 + 0*2 + 1*1), or 121 (i.e. 1*4 + 2*2 + 1*1), as shown in this table:

| 8s | 4s | 2s | 1s |
|  1 |  0 |  0 |  1 |
|  0 |  2 |  0 |  1 |
|  0 |  1 |  2 |  1 |

So, if passed 9, your function would need to return the three numbers, 1001, 201 and 121.

Format and order are irrelevant, so long as it's obvious (i.e. [121,201,1001], "0201 0121 1001", ("1001","121","201") are valid results when given an input of 9).


  • 2 => 10, 2
  • 9 => 1001, 201, 121
  • 10 => 1010, 210, 202, 1002, 122
  • 23 => 2111, 10111
  • 37 => 100101, 20101, 100021, 20021, 12101, 12021, 11221

9 Answers 9


GolfScript (25 bytes) / CJam (19 17 bytes)



This creates an anonymous function (see meta discussion about permissibility of anonymous functions).

Online demo

A straight translation into CJam is (with thanks to Martin Büttner for shaving a couple of characters)



{             # Function boilerplate
  :^          # Store parameter as variable ^
  .*          # Square parameter - see detailed explanation below
  ,{3base}%   # Produce an array of 0 to ^*^-1 in ternary
  {2base^=},  # Filter to those which evaluate to ^ in binary

The reason for the squaring operation is that we need to iterate up to the largest possible value whose ternary representation, interpreted in binary, is equal to ^. Since 2 = 10, the "normal" binary representation of ^ is the one which matters. If we convert that to ternary, we find that the "worst" cases are powers of 2. An optimal approach would be to take the argument to the power of ln 3/ln 2 ~= 1.585, but squaring is much shorter.

  • \$\begingroup\$ I bet a CJam translation will be lot smaller. \$\endgroup\$
    – Optimizer
    Dec 4, 2014 at 9:46
  • 1
    \$\begingroup\$ @Optimizer go ahead ;-) \$\endgroup\$ Dec 4, 2014 at 9:53
  • \$\begingroup\$ GolfScript? man I'm such a noob \$\endgroup\$ Dec 4, 2014 at 15:15

Python 2 (59 bytes)

S=lambda n,B="":[B][n:]or~n%2*S(n/2-1,"2"+B)+S(n/2,`n&1`+B)

(Much thanks to @grc, @xnor and @PeterTaylor for helping out in chat)

Simple recursion, call with S(23) or similar.


The general idea is that if n's binary expansion ends in a 1, then any pseudo-binary ("binary, but with twos") expansion must also end with a 1. Otherwise it could end with 0 or 2.

Hence we look at the last bit of n, divide out and branch accordingly.


S=lambda n,B="":           # Lambda expression
[B][n:]or                  # Short circuit, return [B] if n==0 else what follows
~n%2*                      # Keep next list result if n is even else turn into []
S(n/2-1,"2"+B)             # Add a "2" to B, recurse
S(n/2,`n&1`+B)             # Add "0" or "1" to B depending on n's last bit, recurse


  • n: The number we want to find pseudo-binary expansions of
  • B: A pseudo-binary string being built right-to-left

Bash+coreutils, 77

f()(seq `dc -e2o$1p`|sed '/[3-9]/d;s/.*/&n9P2i&pAi/'|dc|grep -Po ".*(?= $1)")

(That is a TAB character in the grep expression.)

This is bending this rule a bit:

"In the unlikely event that a language happens to contain a built-in function to achieve the result, it's disallowed"

It turns out that dc has the reverse of what we need built in. For instance if we set the input base to 2 and input a binary number with twos, it will correctly parse it. (Similarly if the input mode is base 10, then A-F are parsed as decimal "digits" 10-15).

seq creates a list of all decimal numbers up to the standard binary representation of n, parsed as a decimal. Then all numbers that contain anything other than {0,1,2} are filtered out. Then dc parses the remaining numbers as binary to see which evaluate back to n.

Bash functions can only "return" scalar integers 0-255. So I'm taking the liberty of printing the list to STDOUT as my way of "returning". This is idiomatic for shell scripts.


$ f 2
$ f 9

Haskell, 82

t n=[dropWhile(==0)s|s<-mapM(\_->[0..2])[0..n],n==sum[2^(n-i)*v|(i,v)<-zip[0..]s]]

this is just a brute-force solution. it is very inefficient, because it is expected to crunch through 3^n possibilities.


Jelly, 10 bytes, language postdates challenge


Try it online!

A bruteforce solution up to a number of hyperbits equal to the input (this format is known as "hyperbinary"). As such, it's incredibly inefficient, running in O(3n).


ṗ@            Construct all lists with the given length, and elements taken from
  3Ḷ¤         the list [0,1,2]
        Ðf    then take only those elements which
     Ḅ=¥      when interpreted as binary, equal {the original number}

PHP, 138 Bytes

function p($v,$i=0,$r=""){global$a;if($v==0)$a[]=$r?:0;elseif($v>0)for(;$l<3;)p($v-2**$i*$l,$i+1,+$l++.$r);}p($argv[1]);echo join(",",$a);


function p($v,$i=0,$r=""){
    if($v==0)$a[]=$r?:0;  # fill result array
    elseif($v>0) # make permutations
            p($v-2**$i*$l,$i+1,+$l++.$r); #recursive
echo join(",",$a); # Output

C++, 159 bytes

void c(int x,string r){int i,t=0,s=r.size();if(s<8){if(r[0]>48){for(i=0;i<s;i++)t+=(r[s-i-1]-48)*1<<i;if(t==x)cout<<r<<" ";}for(char n=48;n<51;n++)c(x,r+n);}}

Test it here


k, 21 bytes

Uses the same method as Peter Taylor's Golfscript answer



k) {X@&x=2/:'X:3\:'!x*x}9
(1 2 1;2 0 1;1 0 0 1)
k) {X@&x=2/:'X:3\:'!x*x}10
(1 2 2;2 0 2;2 1 0;1 0 0 2;1 0 1 0)

Haskell, 80 bytes

f 0=[[]]
f n=((++[n-2*d])<$>f d)++[x|n==2*d,x<-(++[2])<$>(f$d-1)]where d=n`div`2

Try it online!

Recursive solution, and my first Haskell golf.

-- recursive definition
-- base case: a sum of 0 is possible as simply a 0-length "binary-with-two" string
f 0=[[]]
-- f n=all possibilities to form n
f n =
-- like normal binary, can have a last digit of 0 or 1 if even or odd, respectively
-- consider n`mod'`2 = n-2*d
    (++[n-2*d])<$> -- add that last digit to each
    f d -- possibility from n/2
-- additional possibility of last digit 2, only if n is even
     n==2*d -- if n is even:
  [x|      ,x<-(++[2])<$>(f$d-1)] -- add that last digit 2 to each possibility from (n-2)/2
  where d=n`div`2

Your Answer

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

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