Convert numbers to binary... but you're allowed to use twos as well

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

GolfScript:

{:^.*,{3base}%{2base^=},}

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)

{:X_*,3fb{2bX=},}

Dissection

{             # 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.

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.

Explanation

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.

Dissection

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

Variables:

• 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.

Output:

$ f 2
2   
10  
$ f 9
121 
201 
1001    
$