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> to W%.

Thanks to @MartinBüttner for golfing off one byte.

Background

The skew binary representation a_k...a₀ corresponds to the integer n = (2^k+1-1)a_k+...+(2¹-1)a₀.

Since both (2^k-1) + ... + (2¹-1) = 2^k+1 - (k + 2) and (2^k-1) + ... + 2(2^j-1) = 2^k+1 - (2^j+1 - 2^j + k + 1) are less than 2^k+1-1, the values of a_k to a₀ can be recovered by successive modular division by 2^k+1-1, 2^k-1, etc.

To begin, we have to find the value of 2^k+1-1 first. Since n is at most 2(2^k+1-1), the integer n + 1 must be strictly smaller than 2^k+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 ⌊log₂(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 0s from the stack, exits immediately instead of pushing anything and dumps the stack to STDOUT.

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.

CJam, 22 21 20 bytes

ri_me,3fb{0-W<1-!},=

This is an O(eⁿn) approach, where n is the input. It lists the first ⌊eⁿ⌋ non-negative integers in base 3, eliminates those that have 2s or 1s after the first 2 (if any) and selects the n+1^th.

Try it online in the CJam interpreter.

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.