xkcd-Style Page Numbering
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.