xkcd-Style Page Numbering 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. This number system is known as skew binary.

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 =&gt; 1
2 =&gt; 2
3 =&gt; 10
6 =&gt; 20
7 =&gt; 100
50 =&gt; 11011
100 =&gt; 110020
200 =&gt; 1100110
1000 =&gt; 111110120
10000 =&gt; 1001110001012
100000 =&gt; 1100001101010020
1000000 =&gt; 1111010000100100100
1048576 =&gt; 10000000000000000001

1000000000000000000 =&gt; 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, &lt;s&gt;104&lt;/s&gt; &lt;s&gt;101&lt;/s&gt; 96 bytes




&lt;script&gt;site = 'meta.codegolf'; postID = 5314; isAnswer = true; QUESTION_ID = 51517&lt;/script&gt;&lt;script src='https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js'&gt;&lt;/script&gt;&lt;script&gt;jQuery(function(){var u='https://api.stackexchange.com/2.2/';if(isAnswer)u+='answers/'+postID+'?order=asc&amp;sort=creation&amp;site='+site+'&amp;filter=!GeEyUcJFJeRCD';else u+='questions/'+postID+'?order=asc&amp;sort=creation&amp;site='+site+'&amp;filter=!GeEyUcJFJO6t)';jQuery.get(u,function(b){function d(s){return jQuery('&lt;textarea&gt;').html(s).text()};function r(l){return new RegExp('&lt;pre class="snippet-code-'+l+'\\b[^&gt;]*&gt;&lt;code&gt;([\\s\\S]*?)&lt;/code&gt;&lt;/pre&gt;')};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('&lt;style&gt;').text(d(c[1])));if (h!==null)jQuery('body').append(d(h[1]));if(j!==null)jQuery('body').append(jQuery('&lt;script&gt;').text(d(j[1])))})})&lt;/script&gt;
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.

If you try this code in the CJam interpreter, just ignore everything but the last line of output.

The error can be eliminated, at the cost of 2 bytes, by prepending 2&gt; 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 &lfloor;log2(n + 1)&rfloor; 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 -&gt; 2**J
  (   e#     -&gt; 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 -&gt; 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 0s from the stack, exits immediately instead of pushing anything and dumps the stack to STDOUT.