[Question]
  [
Randall Munroe's book "xkcd, volume 0" uses a rather odd number system for the page numbers. The first few page numbers are
```
1, 2, 10, 11, 12, 20, 100, 101, 102, 110, 111, 112, 120, 200, 1000, 1001, ...
```
This looks a bit like ternary, but notice that he skips from `20` straight to `100`, from `120` to `200` and from `200` to `1000`. One way to define this sequence is to say that it enumerates all ternary numbers that contain at most one `2` and no `1` after that `2`. You can find this on OEIS in entry [A169683](https://oeis.org/A169683). This number system is known as [skew binary](http://en.wikipedia.org/wiki/Skew_binary_number_system).
Your task is to find the representation of a given positive integer `N` in this number system.
You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.
Output may be a string, a number with a decimal representation equal to the skew binary representation, or a list of digits (as integers or characters/strings). You must not return leading zeroes.
This is code golf, so the shortest answer (in bytes) wins.
**Fun fact:** There is actually some merit to this number system. When incrementing a number, you will always change at most two adjacent digits - you'll never have to carry the change through the entire number. With the right representation that allows incrementing in O(1).
## Test Cases
```
1 => 1
2 => 2
3 => 10
6 => 20
7 => 100
50 => 11011
100 => 110020
200 => 1100110
1000 => 111110120
10000 => 1001110001012
100000 => 1100001101010020
1000000 => 1111010000100100100
1048576 => 10000000000000000001
1000000000000000000 => 11011110000010110110101100111010011101100100000000000001102
```
I will give a bounty to the shortest answer which can solve the last test case (and any other input of similar magnitude, so don't think about hardcoding it) in less than a second.
## Leaderboards
Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language.
To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:
```
# Language Name, N bytes
```
where `N` is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:
```
# Ruby, <s>104</s> <s>101</s> 96 bytes
```
```
<script>site = 'meta.codegolf'; postID = 5314; isAnswer = true; QUESTION_ID = 51517</script><script src='https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js'></script><script>jQuery(function(){var u='https://api.stackexchange.com/2.2/';if(isAnswer)u+='answers/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJeRCD';else u+='questions/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJO6t)';jQuery.get(u,function(b){function d(s){return jQuery('<textarea>').html(s).text()};function r(l){return new RegExp('<pre class="snippet-code-'+l+'\\b[^>]*><code>([\\s\\S]*?)</code></pre>')};b=b.items[0].body;var j=r('js').exec(b),c=r('css').exec(b),h=r('html').exec(b);if(c!==null)jQuery('head').append(jQuery('<style>').text(d(c[1])));if (h!==null)jQuery('body').append(d(h[1]));if(j!==null)jQuery('body').append(jQuery('<script>').text(d(j[1])))})})</script>
```
  
[Answer]
# CJam, ~~24~~ ~~23~~ ~~22~~ ~~21~~ 19 bytes
```
ri_)2b,,W%{2\#(md}/
```
This is an **O(log n)** approach, where **n** is the input, that completes the last test case instantly. It converts **n** directly to skew binary, using modular division by the values of the digit **1**.
This code finishes with an error that goes to STDERR with the Java interpreter, which is allowed according to the [consensus on Meta](https://codegolf.meta.stackexchange.com/a/4781).
If you try this code in the [CJam interpreter](http://cjam.aditsu.net/#code=ri_)2b%2C%2CW%25%7B2%5C%23(md%7D%2F&input=1000000000000000000), just ignore everything but the last line of output.
The error can be eliminated, at the cost of 2 bytes, by prepending `2>` to `W%`.
*Thanks to @MartinBüttner for golfing off one byte.*
### Background
The skew binary representation **ak...a0** corresponds to the integer **n = (2k+1-1)ak+...+(21-1)a0**.
Since both **(2k-1) + ... + (21-1) = 2k+1 - (k + 2)** and **(2k-1) + ... + 2(2j-1) = 2k+1 - (2j+1 - 2j + k + 1)** are less than **2k+1-1**, the values of **ak** to **a0** can be recovered by successive modular division by **2k+1-1**, **2k-1**, etc.
To begin, we have to find the value of **2k+1-1** first. Since **n** is at most **2(2k+1-1)**, the integer **n + 1** must be strictly smaller than **2k+2**.
Thus, taking the integer part of the binary logarithm of **n + 1** yields **k + 1**.
Finally, we observe that the integer **n + 1** has **⌊log2(n + 1)⌋** digits in base 2.
### How it works
```
ri    e# Read an integer N from STDIN.
2b,   e# Push the number of binary digits of N + 1, i.e, K + 2 = log(N + 1) + 1.
,W%   e# Push the range [K+1 ... 0].
{     e# For each J in the range:
  2\# e#   J -> 2**J
  (   e#     -> 2**J - 1
  md  e#   Perform modular division of the integer on the stack (initially N)
      e#   by 2**J - 1: N, 2**J - 1 -> N/(2**J - 1), N%(2**J - 1)
}/    e#
```
In the last two iterations, we perform modular division by **1** and **0**. The first pushes an unwanted **0** on the stack. The last attempts to execute `0 0 md`, which pops both unwanted **0**s from the stack, exits immediately instead of pushing anything and dumps the stack to STDOUT.
[Answer]
# Python 2, 67 bytes
```
def f(n):x=len(bin(n+1))-3;y=2**x-1;return n and n/y*10**~-x+f(n%y)
```
Seems to work for the given test cases. If I've got this right, this should be about `O(place values set in output)`, so it does the last case with ease.
Call like `f(100)`. Returns a decimal representation equal to the skew binary.
# Python 3, 65 bytes
```
def g(n,x=1):*a,b=n>x*2and g(n,x-~x)or[n];return a+[b//x,b%x][:x]
```
Slightly less efficient but still logarithmic, so the last case is near-instant.
Call like `g(100)`. Returns a list of digits.
[Answer]
# Pyth, 17 bytes
```
Ljb3ye.f!-P-yZ01Q
```
This is somewhat ridiculously slow - `O(output^log_2(3))`. It's exponential in the length of the input, but not doubly exponential, like some of the answers on the page. Some ideas taken from @Dennis's answer, [here](https://codegolf.stackexchange.com/a/51529/20080).
[Demonstration.](https://pyth.herokuapp.com/?code=Ljb3ye.f!-P-yZ01Q&input=100&debug=0)
It makes use of `.f`, Pyth's "loop until n matches have been found" function.
[Answer]
# CJam, ~~22~~ ~~21~~ 20 bytes
```
ri_me,3fb{0-W<1-!},=
```
This is an **O(enn)** approach, where **n** is the input. It lists the first **⌊en⌋** non-negative integers in base 3, eliminates those that have **2**s or **1**s after the first **2** (if any) and selects the **n+1**th.
Try it online in the [CJam interpreter](http://cjam.aditsu.net/#code=ri_2%23)%2C3fb%7B0-W%3C1-!%7D%2C%3D&input=10).
### How it works
```
ri    e# Read an integer N from STDIN.
_me,  e# Push [0 ... floor(exp(N))-1].
3fb   e# Replace each integer in the range by the array of its digits in base 3.
{     e# Filter; for each array A:
  0-  e#   Remove all 0's.
  W<  e#   Remove the last element.
  1-  e#   Remove all 1's.
  !   e#   Logical NOT. Pushes 1 iff the array is empty.
},    e#   If ! pushed 1, keep the array.
=     e# Select the (N+1)th element of the filtered array.
```
[Answer]
# Pyth, 20 bytes
```
Jt^2hslhQ#p/=%QJ=/J2
```
Runs in O(log(input())), well under a second for the final test case. Based around a run until error loop. No trailing newline.
[Demonstration.](https://pyth.herokuapp.com/?code=Jt%5E2hslhQ%23p%2F%3D%25QJ%3D%2FJ2&input=1000000000000000000&debug=0)
Explanation:
```
Jt^2hslhQ#p/=%QJ=/J2
                        Implicit: Q is the input.
      lhQ                          log(Q+1,2)
     slhQ                    floor(log(Q+1,2))
    hslhQ                    floor(log(Q+1,2))+1
  ^2hslhQ                 2^(floor(log(Q+1,2))+1)
 t^2hslhQ                 2^(floor(log(Q+1,2))+1)-1
Jt^2hslhQ               J=2^(floor(log(Q+1,2))+1)-1
         #              until an error is thrown:
            =%QJ        Q=Q%J
                =/J2    J=J/2
           /            The value Q/J, with the new values of Q and J.
          p             print that charcter, with no trailing newline.
```
J is initialized to the value of the smallest skew binary digit position that is larger than the input. Then, each time through the loop, we do the following:
* Remove each digit of value `J` from `Q` with `=%QJ`. For instance, if `Q=10` and `J=7`, `Q` becomes `3`, which corresponds to the skew binary changing from `110` to `10`. This has no effect in the first iteration.
* Change `J` to the next smaller skew binary base value with `=/J2`. This is floored division by 2, changing `J=7` to `J=3`, for instance. Because this happens before the first digit is output, `J` is intialized one digit position higher than needed.
* Find the actual digit value with `/QJ` (effectively).
* Print that value with `p`, instead of Pyth`s default printing, to avoid the trailing newline.
This loop will repeat until `J` becomes zero, at which point a divide by zero error will be thrown, and the loop will end.
[Answer]
# ES6, 105 bytes
```
f=n=>{for(o=0;n--;c?o+=Math.pow(3,s.length-c):o++)s=t(o),c=s.search(2)+1;return t(o);},t=a=>a.toString(3)
```
Usage is:
`f(1048576)` => `"10000000000000000001"
Test the last argument at your own peril. I gave up after 5 seconds.
And pretty print with comments!
```
f=n=>{ //define function f with input of n (iteration)
    for(o=0; //define o (output value in decimal)
        n--; //decrement n (goes towards falsy 0) each loop until 0
        c?o+=Math.pow(3,s.length-c):o++) //if search finds a 2, increment output by 3^place (basically moves the 2 to the left and sets the place to 0), else ++
        s=t(o), //convert output to base 3      
        c=s.search(2)+1; //find the location of 2, +1, so a not-found becomes falsy 0.
    return t(o); //return the output in base 3
},
t=a=>a.toString(3);  //convert input a to base 3
```
[Answer]
# Retina, 55 bytes
```
^
0a
(+`12(.*a)1
20$1
0?2(.*a)1
10$1
0a1
1a
)`1a1
2a
a
<empty line>
```
Takes input in unary.
Each line should go to its own file but you can run the code as one file with the `-s` flag. E.g.:
```
> echo 11111|retina -s skew
12
```
Method: Executes incrementation on a string input number times starting from the string `0`.
We use the following incrementation rules:
* if contains `2`: `^2 -> ^12`; `02 -> 12`; `12 -> 20`
* if doesn't contain `2`: `0$ -> 1$`; `1$ -> 2$`
(There can be at most one `2` in the string; `^` and `$` marks the start and end of the string in the rules.)
[More information about Retina.](https://github.com/mbuettner/retina)
[Answer]
# Java, ~~154~~ 148
```
n->{String s="0";for(;n-->0;)s=s.contains("2")?s.replaceAll("(^|0)2","10").replace("12","20"):s.replaceAll("1$","2").replaceAll("0$","1");return s;}
```
This answer take the form of a single anonymous function that takes an integer argument and returns the answer as a String. Below is a complete class for testing this solution.
```
import java.util.function.Function;
public class Skew {
    public static void main(String[] args){
        Function<Integer,String> skew = n->{String s="0";for(;n-->0;)s=s.contains("2")?s.replaceAll("(^|0)2","10").replace("12","20"):s.replaceAll("1$","2").replaceAll("0$","1");return s;};
        for(String s:args){
            System.out.println(skew.apply(Integer.parseInt(s)));
        }
    }
}
```
[Answer]
# Bash + coreutils, 52
```
dc -e3o0[r1+prdx]dx|grep -v 2.\*[12]|sed -n $1{p\;q}
```
This is a brute-forcer, so its rather slow for larger numbers.
### Output:
```
$ ./xkcdnum.sh 1000
111110120
$ 
```
[Answer]
# Java, ~~337~~ ~~335~~ ~~253~~ ~~246~~ 244 bytes
A method that takes in the index as a `long` and returns the result as a string
Uses a `long` for the index so can *theoretically* handle the last test case, but I *really* wouldn't suggest it.
```
String f(long i){List<Long>l=new ArrayList<>();l.add(0L);for(;i-->0;){int j=l.indexOf(2);if(j!=-1){l.set(j,0L);if(j==0){l.add(0,1L);}else{l.set(j-1,l.get(j-1)+1);}}else{j=l.size()-1;l.set(j,l.get(j)+1);}}String s="";for(long q:l)s+=q;return s;}
```
[Answer]
# Haskell, ~~73~~ 72
Thanks to @nimi for 1 byte!
This solution won't be winning any bounty, the last couple tests take an inordinate amount of time to run, but, I think I've golfed it fairly well. 
```
i(2:b)=1:0:b
i[b]=[b+1]
i(b:2:c)=b+1:0:c
i(b:c)=b:i c
s=(iterate i[0]!!)
```
This solution is a rather naïve approach that calculates the skew binary number `n` by incrementing 0 `n` times.
[Answer]
# CJam, 24 bytes
```
Q{0\+2a/())+a\+0a*}ri*si
```
This is an **O(n log n)** approach, where **n** is the input. It starts with the skew binary representation of **0** and increments the corresponding integer **n** times.
Try it online in the [CJam interpreter](http://cjam.aditsu.net/#code=Q%7B0%5C%2B2a%2F())%2Ba%5C%2B0a*%7Dri*si&input=1000).
### Background
Incrementing a number in skew binary can be done by following two easy steps:
1. Replace an eventual **2** by a **0**.
2. If a **2** has been replaced, increment the digit to its left.
Otherwise, increment the last digit.
### How it works
```
Q     e# Push an empty array.
{     e# Define an anonymous function:
  0\+ e#   Prepend a 0 to the array.
  2a/ e#   Split the array at 2's.
  (   e#   Shift out the first chunk of this array.
  )   e#   Pop the last digit.
  )+  e#   Increment it and append it to the array.
  a\+ e#   Prepend the chunk to the array of chunks.
  0a* e#   Join the chunks, using [0] as separator.
      e#   If there was a 2, it will get replaced with a 0. Otherewise, there's
      e#   only one chunk and joining the array dumps the chunk on the stack.
}     e#
ri*   e# Call the function int(input()) times.
si    e# Cast to string, then to integer. This eliminates leading 0's.
```
[Answer]
# VBA, ~~209~~ ~~147~~ 142 bytes
```
Sub p(k)
For i=1To k
a=StrReverse(q)
If Left(Replace(a,"0",""),1)=2Then:q=q-2*10^(InStr(a,2)-1)+10^InStr(a,2):Else:q=q+1
Next
msgbox q
End Sub
```
My math is inefficient and my golfing could use work. But it's my first attempt at PoG and thought I'd give this one a try. Sort of a Brute Force way though.
It's just counting by 1 unless the last digit is a 2 then steps back by 2 and jumps forward 10. Plus the trailing 0's.
This stops working at 65534 because VBA insists on giving output in scientific notation, but the logic should work fine for even higher numbers
Looking forward to golfing suggestions, VBA is not very golf-friendly but it's not often represented, and I think it can beat Java for length.
Edit1:
Thanks **Manu** for helping shave off 62 bytes
Edit2: Swapped `debug.print` for `msgbox` as output. Saved 5 bytes
[Answer]
# Javascript ES6, ~~99~~ ~~86~~ ~~78~~ ~~76~~ 72 chars
```
f=n=>{for(s="1";--n;s=s.replace(/.?2|.$/,m=>[1,2,10][+m]||20));return s}
// Old version, 76 chars:
f=n=>{for(s="1";--n;s=s.replace(/02|12|2|.$/,m=>[1,2,10][+m]||20));return s}
// Old version, 86 chars:
f=n=>{for(s="1";--n;s=s.replace(/(02|12|2|.$)/,m=>[1,2,10,,,,,,,,,,20][+m]));return s}
// Old version, 99 chars:
f=n=>{for(s="1";--n;s=s.replace(/(^2|02|12|20|.$)/,m=>({0:1,1:2,2:10,12:20,20:100}[+m])));return s}
```
Test:
```
;[1,2,3,6,7,50,100,200,1000,10000,100000,1000000,1048576].map(f) == "1,2,10,20,100,11011,110020,1100110,111110120,1001110001012,1100001101010020,1111010000100100100,10000000000000000001"
```
> 
> **Fun fact:** There is actually some merit to this number system. When incrementing a number, you will always change at most two adjacent digits - you'll never have to carry the change through the entire number. With the right representation that allows incrementing in O(1).
> 
> 
> 
Thank you for the fact - it is the base of my solution :)
[Answer]
# Octave, ~~107~~ 101 bytes
Should be **O(log n)** if I'm figuring this right...
```
function r=s(n)r="";for(a=2.^(uint64(fix(log2(n+1))):-1:1)-1)x=idivide(n,a);r=[r x+48];n-=x*a;end;end
```
Pretty-print:
```
function r=s(n)
  r="";
  for(a=2.^(uint64(fix(log2(n+1))):-1:1)-1)
    x=idivide(n,a);
    r=[r x+48];
    n-=x*a;
  end
end
```
I was somewhat stymied addressing the final challenge, since Octave by default treats everything as floating point numbers and I didn't have the necessary precision to calculate the last one. I got around that by spending precious bytes to force everything to be an unsigned integer. The result of the last one was too big to treat as a number, so the result is a string.
Output (I'm including `1e18 - 1` to show I can do that accurately, and the last set of outputs shows how long it takes to calculate that value):
```
octave:83> s(uint64(1e18))
ans = 11011110000010110110101100111010011101100100000000000001102
octave:84> s(uint64(1e18)-1)
ans = 11011110000010110110101100111010011101100100000000000001101
octave:85> tic();s(uint64(1e18)-1);toc()
Elapsed time is 0.0270021 seconds.
```
[Answer]
## T-SQL, ~~221~~ ~~189~~ 177 bytes
EDIT: The original versions of this code would produce incorrect output for some numbers, this has been corrected.
With every query here, just add the number to calculate before the first comma.
Everyone know that T-SQL is the best golfing language. Here is a version that will calculate even the last test case. On the machine I tested it on, it ran in under a second, I'd be interested to see how it runs for everyone else.
```
DECLARE @ BIGINT=,@T VARCHAR(MAX)='';WITH M AS(SELECT CAST(2AS BIGINT)I UNION ALL SELECT I*2FROM M WHERE I<@)SELECT @T += STR(@/(I-1),1),@%=(I-1)FROM M ORDER BY I DESC SELECT @T
```
And here it is again, but readable:
```
DECLARE 
    @ BIGINT=,
    @T VARCHAR(MAX)='';
    
WITH M AS
(
    SELECT
        CAST(2 AS BIGINT) I
        
    UNION ALL
       
    SELECT I * 2
    FROM M
    WHERE I < @
)
SELECT 
    @T+=STR(@/(I-1),1),
    @%=(I-1)
FROM M 
ORDER BY I DESC
SELECT @T
```
---
If I only use ints, this can be a bit shorter, coming out at 157 bytes:
```
DECLARE @ INT=,@T VARCHAR(MAX)='';WITH M AS(SELECT 2I UNION ALL SELECT I*2FROM M WHERE I<@)SELECT @T+=STR(@/(I-1),1),@%=(I-1)FROM M ORDER BY I DESC SELECT @T
```
And once more again, more readable:
```
DECLARE 
    @ INT=,
    @T VARCHAR(MAX)='';
    
WITH M AS
(
    SELECT
        2I
        
    UNION ALL
       
    SELECT 
        I * 2
    FROM M
    WHERE I < @
)
SELECT 
    @T+=STR(@/(I-1),1),
    @%=(I-1)
FROM M 
ORDER BY I DESC
SELECT @T
```
[Answer]
# Turing Machine Code, ~~333~~ 293 bytes
I'm using an encoding as used [here](http://morphett.info/turing/turing.html).
This machine uses 9 states and 11 colors.
If binary input is permissible, this can be reduced to a mere 4 colors, saving a few tens of bytes in the process.
```
0 _ _ l 1
0 * * r 0
1 9 8 l 2 
1 8 7 l 2
1 7 6 l 2
1 6 5 l 2
1 5 4 l 2
1 4 3 l 2
1 3 2 l 2
1 2 1 l 2
1 1 0 l 2
1 0 9 l 1
1 _ _ r 8
2 _ _ l 3
2 * * l 2
3 _ 1 r 4
3 * * l 5
4 _ _ r 0
4 * * r 4
5 * * l 5
5 _ _ r 6
6 _ _ l 7
6 2 0 l 7
6 * * r 6
7 _ 1 r 4
7 0 1 r 4
7 1 2 r 4
8 _ _ * halt
8 * _ r 8
```
If the above link isn't working (sometimes it works for me, other times the page refuses to load) you may also test this using [this java implementation.](http://pastebin.com/fQz6DBRU)
[Answer]
# Perl, 66 bytes
Number is to be input through STDIN.
```
$_=1;$c=<>;s/(.*)(.?)2(.*)/$1.$2+1 .$3.0/e||$_++while(--$c);print;
```
[Answer]
# Pyth, 19 bytes
```
m/=%Qtydtd^L2_SslhQ
```
Logarithmic complexity. Easily finishes in the necessary amount of time. Output in the form of a list of digits.
[Demonstration](https://pyth.herokuapp.com/?code=m%2F%3D%25Qtydtd%5EL2_SslhQ&input=1000000000000000000&debug=0).
[Answer]
# Perl, ~~84~~ ~~70~~ 67 bytes
```
$n=<>;$d*=2while($d++<$n);$_.=int($n/$d)while($n%=$d--,$d/=2);print
```
~~Not very golfy,~~ Getting better but it does work very quickly!
Dennis's suggestion gets it down to 51 (50 bytes + -p switch)
```
$d*=2while$d++<$_;$\.=$_/$d|0while$_%=$d--,$d/=2}{
```
It *must* be called like `perl -p skew_binary.pl num_list.txt` where `num_list.txt` contains a single line with the number to encode on it.
[Answer]
# [JavaScript (Node.js)](https://nodejs.org), 40 bytes
```
v=>(g=n=>n>v?'':g(n-~n)+(v-(v%=n))/n)(1)
```
[Try it online!](https://tio.run/##XY/LTsMwEEX3/opskGdUYuxAW0TlsOIrAKmR6wQj14liE3XFrwc7D4rw@9w7dyR/VkPlVW@6kLv2pMdajoMsoZFOlq4cnil9asDl3w43MOQw3EiHeOcQBI4HErQPqvLaZzI7EpHJMhOkSFdB7ifiZDchJ/uZOdny6SW4ECTyAjyWFFeKO5kLi1RdzApf@iQtnlGf5d/oFE6Tr4lrGz7764r2w@N2v1ta/h@CHP/8kfnOmgD0zVFktbFB93BJyQszTtmvk/ZAZUkR2bnqwCbLrqFZr9v@pVIfAK/mNtPvmEpU63xrNbNtAzVsDEaHhd6cAREP4w8 "JavaScript (Node.js) – Try It Online")
This solution does not work on last testcase. It just cause stack overflow on it.
[Answer]
## Mathematica, 65
Should be quite fast enough, although I have to admit I peeked at the other submissions before making this.
```
f = (n = #;
     l = 0; 
     While[n > 0,
      m = Floor[Log2[1 + n]];
      l += 10^(m - 1);
      n -= 2^m - 1
     ]; l)&
```
Usage:
```
f[1000000000000000000]
```
Output:
```
11011110000010110110101100111010011101100100000000000001102
```
Starts giving MaxExtraPrecision error messages somewhere past 10^228 (for which it calculates the result in .03 seconds on my machine)
After removing the MaxExtraPrecision limit, it will handle numbers up to around 10^8000 in a second.
Input:
```
Timing[Block[{$MaxExtraPrecision = Infinity}, f[10^8000]];]
```
Output:
```
{1.060807, Null}
```
[Answer]
# C, 95 bytes
```
void f(unsigned long i,int*b){for(unsigned long a=~0,m=0;a;a/=2,b+=!!m)m|=*b=i/a,i-=a**b;*b=3;}
```
This accepts an integer and a buffer in which to return the digits. The results are stored in `b`, terminated with value `3` (which can't occur in the output). We don't have to handle input of `0` (as the question specified only positive integers), so there's no special-casing to avoid empty output.
### Expanded code
```
void f(unsigned long i,int*b)
{
    for (unsigned long a=~0, m=0;  a;  a/=2, b+=(m!=0)) {
        *b = i/a;               /* rounds down */
        i -= *b * a;
        m = m | *b;             /* m != 0 after leading zeros */
    }
    *b=3;                       /* add terminator */
}
```
We operate by successive subtraction, starting with the most significant digit. The only complication is that we use the variable `m` to avoid printing leading zeros. A natural extension to `unsigned long long` may be made if desired, at the cost of 10 bytes.
### Test program
Pass numbers to be converted as command arguments. It converts the `int` array buffer to a printable digit string. Runtime is less than one millisecond for input `1000000000000000000`.
```
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char**argv)
{
    while (*++argv) {
        unsigned long i = strtoul(*argv, NULL, 10);
        int result[1024];
        f(i,result);
        /* convert to string */
        char s[1024];
        {char*d=s;int*p=result;while(*p!=3)*d++=*p+++'0';*d=0;}
        printf("%lu = %s\n", i, s);
    }
    return EXIT_SUCCESS;
}
```
### Test results
```
$ ./51517 $(seq 20)
1 = 1
2 = 2
3 = 10
4 = 11
5 = 12
6 = 20
7 = 100
8 = 101
9 = 102
10 = 110
11 = 111
12 = 112
13 = 120
14 = 200
15 = 1000
16 = 1001
17 = 1002
18 = 1010
19 = 1011
20 = 1012
```
[Answer]
## CoffeeScript, ~~92~~ 69 bytes
Based of [Qwertiy's answer](https://codegolf.stackexchange.com/a/51599/22867) and updates:
```
f=(n)->s='1';(s=s.replace /(.?2|.$)/,(m)->[1,2,10][+m]||20)while--n;s
# older version, 92 bytes
f=(n)->s='1';(s=s.replace /(^2|02|12|20|.$)/,(m)->{0:1,1:2,2:10,12:20,20:100}[+m])while--n;s
```
[Answer]
# [Japt](https://github.com/ETHproductions/japt), 31 bytes
```
_r/?2|.$/g_÷C ç20 ª°Zs3}}gU['0]
```
[Try it online!](https://ethproductions.github.io/japt/?v=2.0a0&code=X3IvPzJ8LiQvZ1/3QyDnMjAgqrBaczN9fWdVWycwXQ==&input=LW1SIFsxLDIsMyw2LDcsNTAsMTAwLDIwMCwxMDAwLDEwMDAwXQ==)
Almost direct port of [this JS solution](https://codegolf.stackexchange.com/a/51599/78410). No idea if there's better way.
### Unpacked & How it works
```
X{Xr/?2|.$/gZ{Z÷C ç20 ||++Zs3}}gU['0]
X{     Declare a function...
Xr       Accept a string, replace the regex...
/?2|.$/g   /.?2|.$/   (g is needed to match *only once*, opposite of JS)
Z{       ...with the function... (matched string will be 0,1,2,02 or 12)
Z÷C        Implicitly cast the matched string into number, divide by 12
ç20        Repeat "20" that many times (discard fractions)
||         If the above results in "", use the next one instead
++Z        Increment the value
s3         Convert to base-3 string (so 0,1,2 becomes 1,2,10)
}}
gU['0] Repeatedly apply the function on "0", U (input) times
```
[Answer]
# [Stax](https://github.com/tomtheisen/stax), 16 [bytes](https://github.com/tomtheisen/stax/blob/master/docs/packed.md#packed-stax)
```
üxëàè£öΦGΩ│Je5█ò
```
[Run and debug it](https://staxlang.xyz/#p=817889858a9c94e847eab34a6535db95&i=1%0A2%0A3%0A6%0A7%0A50%0A100%0A200%0A1000%0A10000%0A100000%0A1000000%0A1048576%0A1000000000000000000&a=1&m=2)
I'm not sure exactly what the formal complexity class is, but it's fast enough to do all the test cases in a tenth of a second on this machine.
Unpacked, ungolfed, and commented, it looks like this. In this program, the x register originally contains the input.
```
z       push []
{       start block for while loop
 |X:2N  -log2(++x)
 {^}&   increment array at index (pad with 0s if necessary)
 xc:G-X unset high bit of x; write back to x register
w       while; loop until x is falsy (0)
$       convert to string
```
[Run this one](https://staxlang.xyz/#c=z%09push+[]%0A%7B%09start+block+for+while+loop%0A+%7CX%3A2N%09-log2%28%2B%2Bx%29%0A+%7B%5E%7D%26%09increment+array+at+index+%28pad+with+0s+if+necessary%29%0A+xc%3AG-X%09unset+high+bit+of+x%3B+write+back+to+x+register%0Aw%09while%3B+loop+until+x+is+falsy+%280%29%0A%24%09convert+to+string&i=1%0A2%0A3%0A6%0A7%0A50%0A100%0A200%0A1000%0A10000%0A100000%0A1000000%0A1048576%0A1000000000000000000&a=1&m=2)
[Answer]
# [Husk](https://github.com/barbuz/Husk), 16 bytes
```
!mdfö¬f≠1hfImB3N
```
[Try it online!](https://tio.run/##yygtzv7/XzE3Je3wtkNr0h51LjDMSPPMdTL2@///v6GBAQA "Husk – Try It Online") or [Verify first 100 values](https://tio.run/##ATYAyf9odXNr/23CpytzKCsiIOKGkiAic@KCgSnhuKP/IW1kZsO2wqxm4omgMWhmSW1CM07///8xMDA "Husk – Try It Online")
Same method as Dennis' CJam answer.
]