O livro de Randall Munroe "xkcd, volume 0" usa um sistema de números bastante ímpar para os números de página. Os primeiros números de página são

1, 2, 10, 11, 12, 20, 100, 101, 102, 110, 111, 112, 120, 200, 1000, 1001, ...

Este parece um pouco com ternária, mas noto que ele ignora a partir 20direto para 100, a partir 120de 200e para 200a 1000. Uma maneira de definir essa sequência é dizer que ela enumera todos os números ternários que contêm no máximo um 2e não 1depois disso 2. Você pode encontrar isso no OEIS na entrada A169683 . Esse sistema numérico é conhecido como binário inclinado .

Sua tarefa é encontrar a representação de um número inteiro positivo Nnesse sistema numérico.

Você pode escrever um programa ou função, recebendo entrada via STDIN (ou alternativa mais próxima), argumento da linha de comando ou argumento da função e emitindo o resultado via STDOUT (ou alternativa mais próxima), valor de retorno da função ou parâmetro da função (saída).

A saída pode ser uma sequência, um número com uma representação decimal igual à representação binária inclinada ou uma lista de dígitos (como números inteiros ou caracteres / sequências). Você não deve retornar zeros à esquerda.

Isso é código de golfe, então a resposta mais curta (em bytes) vence.

Curiosidade: Na verdade, há algum mérito nesse sistema numérico. Ao incrementar um número, você sempre alterará no máximo dois dígitos adjacentes - nunca precisará realizar a alteração no número inteiro. Com a representação correta que permite incrementar em O (1).

Casos de teste

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

Darei uma recompensa à resposta mais curta que possa resolver o último caso de teste (e qualquer outra entrada de magnitude semelhante, por isso não pense em codificá-la) em menos de um segundo.

Classificação

Aqui está um snippet de pilha para gerar uma classificação regular e uma visão geral dos vencedores por idioma.

Para garantir que sua resposta seja exibida, inicie-a com um título, usando o seguinte modelo de remarcação:

# Language Name, N bytes

onde Nestá o tamanho do seu envio. Se você melhorar sua pontuação, poderá manter as pontuações antigas no título, identificando-as. Por exemplo:

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

Pitão, 17 bytes

Ljb3ye.f!-P-yZ01Q

Isso é ridiculamente lento - O(output^log_2(3)). É exponencial no comprimento da entrada, mas não duplamente exponencial, como algumas das respostas na página. Algumas idéias retiradas da resposta de @ Dennis, aqui .

Demonstração.

Ele utiliza a .ffunção "loop" de Pyth até que n correspondências sejam encontradas ".

CJam, 24 23 22 21 19 bytes

ri_)2b,,W%{2\#(md}/

Essa é uma abordagem O (log n) , em que n é a entrada, que conclui o último caso de teste instantaneamente. Ele converte n diretamente em binário inclinado, usando a divisão modular pelos valores do dígito 1 .

Esse código termina com um erro que vai para STDERR com o interpretador Java, o que é permitido de acordo com o consenso no Meta .

Se você tentar esse código no interpretador CJam , ignore tudo, menos a última linha de saída.

O erro pode ser eliminado, ao custo de 2 bytes, acrescentando-o 2>a W%.

Obrigado a @ MartinBüttner por jogar um byte.

fundo

A representação binária inclinada a _k ... a ₀ corresponde ao número inteiro n = (2 ^{k + 1} -1) a _k + ... + (2 ¹ -1) a ₀ .

Dado que ambos (2 ^k -1) + ... + (2 ¹ -1) = 2 ^{k + 1} - (k + 2) e (2 ^k -1) + ... + 2 (2 ^j -1) = 2 ^{k + 1} - (2 ^{j + 1} - 2 ^j + k + 1) é inferior a 2 ^{k + 1} -1 , os valores de um _K para um ₀ pode ser recuperado por divisão modular sucessiva por duas ^{k + 1} -1 , 2 ^k -1 etc.

Para começar, temos que encontrar o valor de 2 ^{k + 1} -1 primeiro. Como n é no máximo 2 (2 ^{k + 1} -1) , o número inteiro n + 1 deve ser estritamente menor que 2 ^{k + 2} .

Assim, assumir a parte inteira do logaritmo binário de n + 1 produz k + 1 .

Finalmente, observamos que o número inteiro n + 1 possui ⌊log ₂ (n + 1) ⌋ dígitos na base 2.

Como funciona

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#

Nas duas últimas iterações, realizamos a divisão modular por 1 e 0 . O primeiro coloca um 0 indesejado na pilha. As últimas tentativas para executar 0 0 md, que aparece tanto indesejados 0 s da pilha, sai imediatamente em vez de empurrar qualquer coisa e despeja a pilha para 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)

Parece funcionar para os casos de teste fornecidos. Se eu entendi direito, isso deve ser sobre O(place values set in output), então o último caso é fácil.

Ligue como f(100). Retorna uma representação decimal igual ao binário de inclinação.

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]

Um pouco menos eficiente, mas ainda logarítmico, portanto, o último caso é quase instantâneo.

Ligue como g(100). Retorna uma lista de dígitos.

CJam, 22 21 20 bytes

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

Essa é uma abordagem O (e ⁿ n) , em que n é a entrada. Ele lista os primeiro ⌊e ⁿ ⌋ inteiros não negativos em 3 de base, elimina aqueles que têm 2 s ou 1 s após o primeiro 2 (se houver) e selecciona o n + 1 ^th .

Experimente online no intérprete CJam .

Como funciona

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.

Pitão, 20 bytes

Jt^2hslhQ#p/=%QJ=/J2

É executado em O (log (input ())), bem menos de um segundo para o caso de teste final. Baseado em uma execução até o loop de erro. Nenhuma nova linha à direita.

Demonstração.

Explicação:

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 é inicializado com o valor da menor posição do dígito binário inclinado que é maior que a entrada. Então, sempre que fizermos o loop, fazemos o seguinte:

• Remova cada dígito do valor Jde Qcom =%QJ. Por exemplo, se Q=10e J=7, Qtorna-se 3, o que corresponde ao binário inclinado que muda de 110para 10. Isso não tem efeito na primeira iteração.
• Mude Jpara o próximo valor base binário de inclinação menor com =/J2. Esta é a divisão com piso por 2, mudando J=7para J=3, por exemplo. Como isso acontece antes da saída do primeiro dígito, Jé inicializada uma posição de um dígito acima do necessário.
• Encontre o valor real do dígito com /QJ(efetivamente).
• Imprima esse valor com p, em vez da impressão padrão de Pyth, para evitar a nova linha à direita.

Esse loop será repetido até que Jse torne zero; nesse ponto, será gerado um erro de divisão por zero e o loop será encerrado.

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)

O uso é: f(1048576)=> `" 10000000000000000001 "

Teste o último argumento por sua própria conta e risco. Desisti após 5 segundos.

E bonita impressão com comentários!

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

Retina, 55 bytes

^
0a
(+`12(.*a)1
20$1
0?2(.*a)1
10$1
0a1
1a
)`1a1
2a
a
<empty line>

Recebe entrada em unário.

Cada linha deve ir para seu próprio arquivo, mas você pode executar o código como um arquivo com o -ssinalizador. Por exemplo:

> echo 11111|retina -s skew
12

Método: Executa incremento em um número de entrada de sequência vezes, a partir da sequência 0.

Usamos as seguintes regras de incremento:

• se contém 2: ^2 -> ^12; 02 -> 12;12 -> 20
• se não contém 2: 0$ -> 1$;1$ -> 2$

(Pode haver no máximo uma 2na string; ^e $marca o início e o fim da string nas regras.)

Mais informações sobre Retina.

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;}

Esta resposta assume a forma de uma única função anônima que recebe um argumento inteiro e retorna a resposta como uma String. Abaixo está uma classe completa para testar esta solução.

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)));
        }
    }
}

Bash + coreutils, 52

dc -e3o0[r1+prdx]dx|grep -v 2.\*[12]|sed -n $1{p\;q}

Este é um forçador bruto, por isso é bastante lento para números maiores.

Resultado:

$ ./xkcdnum.sh 1000
111110120
$ 

Java, 337 335 253 246 244 bytes

Um método que recebe o índice como a longe retorna o resultado como uma sequência

Usa um longpara o índice, portanto, teoricamente, podemos lidar com o último caso de teste, mas eu realmente não o sugeriria.

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;}

Haskell, 73 72

^{Obrigado a @nimi por 1 byte!}

Essa solução não ganhará nenhuma recompensa, os últimos dois testes demoram muito tempo para serem executados, mas acho que joguei bastante bem.

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]!!)

Esta solução é uma abordagem bastante ingênua que calcula o número binário inclinado nincrementando 0 nvezes.

CJam, 24 bytes

Q{0\+2a/())+a\+0a*}ri*si

Essa é uma abordagem O (n log n) , em que n é a entrada. Começa com a representação binária inclinada de 0 e incrementa o número inteiro correspondente n vezes.

Experimente online no intérprete CJam .

fundo

O incremento de um número no binário inclinado pode ser feito seguindo duas etapas fáceis:

1. Substitua um 2 eventual por um 0 .

2. Se um 2 foi substituído, aumente o dígito para a esquerda.

   Caso contrário, aumente o último dígito.

Como funciona

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.

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

Minha matemática é ineficiente e meu golfe pode funcionar. Mas é a minha primeira tentativa no PoG e pensei em experimentar este. Tipo de uma maneira Brute Force embora.

É apenas contar 1, a menos que o último dígito seja 2, depois recue 2 e pule para a frente 10. Mais os zeros à direita.

Isso deixa de funcionar em 65534 porque o VBA insiste em fornecer saída em notação científica, mas a lógica deve funcionar bem para números ainda mais altos

Ansioso por sugestões de golfe, o VBA não é muito favorável ao golfe, mas nem sempre é representado, e acho que ele pode superar o Java.

Edit1: Obrigado Manu por ajudar a remover 62 bytes

Edit2: Trocado debug.printpor msgboxcomo saída. Salvo 5 bytes

Javascript ES6, 99 86 78 76 72 caracteres

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}

Teste:

;[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"

Curiosidade: Na verdade, há algum mérito nesse sistema numérico. Ao incrementar um número, você sempre alterará no máximo dois dígitos adjacentes - nunca precisará realizar a alteração no número inteiro. Com a representação correta que permite incrementar em O (1).

Obrigado pelo fato - é a base da minha solução :)

Oitava, 107 101 bytes

Deve ser O (log n) se eu estiver pensando nisso direito ...

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

Fiquei um pouco frustrado ao enfrentar o desafio final, já que o Octave, por padrão, trata tudo como números de ponto flutuante e não tinha a precisão necessária para calcular o último. Eu consegui contornar isso gastando bytes preciosos para forçar tudo a ser um número inteiro não assinado. O resultado do último foi grande demais para ser tratado como um número; portanto, o resultado é uma sequência.

Saída (estou incluindo 1e18 - 1mostrar que posso fazer isso com precisão, e o último conjunto de saídas mostra quanto tempo leva para calcular esse valor):

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.

T-SQL, 221 189 177 bytes

EDIT: As versões originais deste código produziriam saída incorreta para alguns números, isso foi corrigido.

Em todas as consultas aqui, basta adicionar o número a calcular antes da primeira vírgula.

Todos sabem que o T-SQL é a melhor linguagem de golfe. Aqui está uma versão que calculará até o último caso de teste. Na máquina em que a testei, ela foi executada em menos de um segundo, eu estaria interessado em ver como funciona para todos os outros.

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

E aqui está novamente, mas legível:

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

Se eu usar apenas ints, isso pode ser um pouco menor, saindo em 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

E mais uma vez, mais legível:

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

Código da Máquina de Turing, 333 293 bytes

Estou usando uma codificação usada aqui .

Esta máquina usa 9 estados e 11 cores.

Se a entrada binária for permitida, isso poderá ser reduzido para meras 4 cores, economizando algumas dezenas de bytes no processo.

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

Se o link acima não estiver funcionando (às vezes funciona para mim, outras vezes a página se recusa a carregar), você também pode testar isso usando esta implementação java.

Perl, 66 bytes

O número deve ser inserido através do STDIN.

$_=1;$c=<>;s/(.*)(.?)2(.*)/$1.$2+1 .$3.0/e||$_++while(--$c);print;

Pitão, 19 bytes

m/=%Qtydtd^L2_SslhQ

Complexidade logarítmica. Termina facilmente na quantidade de tempo necessária. Saída na forma de uma lista de dígitos.

Demonstração .

Perl, 84 70 67 bytes

$n=<>;$d*=2while($d++<$n);$_.=int($n/$d)while($n%=$d--,$d/=2);print

Não é muito golfista, está ficando melhor, mas funciona muito rapidamente!

A sugestão de Dennis reduz para 51 (50 bytes + -p switch)

$d*=2while$d++<$_;$\.=$_/$d|0while$_%=$d--,$d/=2}{

Ele deve ser chamado como perl -p skew_binary.pl num_list.txtonde num_list.txtcontém uma única linha com o número para codificar nele.

Mathematica, 65

Deve ser rápido o suficiente, embora eu deva admitir que espiei as outras submissões antes de fazer isso.

f = (n = #;
     l = 0; 
     While[n > 0,
      m = Floor[Log2[1 + n]];
      l += 10^(m - 1);
      n -= 2^m - 1
     ]; l)&

Uso:

f[1000000000000000000]

Resultado:

11011110000010110110101100111010011101100100000000000001102

Começa a transmitir mensagens de erro MaxExtraPrecision em algum lugar após 10 ^ 228 (para o qual calcula o resultado em 0,03 segundos na minha máquina)

Depois de remover o limite MaxExtraPrecision, ele manipulará números de até 10 ^ 8000 em um segundo.

Entrada:

Timing[Block[{$MaxExtraPrecision = Infinity}, f[10^8000]];]

Resultado:

{1.060807, Null}

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;}

Isso aceita um número inteiro e um buffer no qual retornar os dígitos. Os resultados são armazenados b, finalizados com valor 3(que não pode ocorrer na saída). Não precisamos manipular a entrada de 0(como a pergunta especifica apenas números inteiros positivos); portanto, não existe uma caixa especial para evitar saída vazia.

Código expandido

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 */
}

Operamos por subtração sucessiva, começando com o dígito mais significativo. A única complicação é que usamos a variável mpara evitar a impressão de zeros à esquerda. Uma extensão natural unsigned long longpode ser feita, se desejado, ao custo de 10 bytes.

Programa de teste

Passe números a serem convertidos como argumentos de comando. Ele converte o intbuffer da matriz em uma sequência de dígitos imprimível. O tempo de execução é menor que um milissegundo para entrada 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;
}

Resultado dos testes

$ ./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

JavaScript (Node.js) , 40 bytes

v=>(g=n=>n>v?'':g(n-~n)+(v-(v%=n))/n)(1)

Experimente online!

Esta solução não funciona no último testcase. Apenas causa excesso de pilha.

CoffeeScript, 92 69 bytes

Baseado nas respostas e atualizações de Qwertiy :

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

Japonês , 31 bytes

_r/?2|.$/g_÷C ç20 ª°Zs3}}gU['0]

Experimente online!

Porta quase direta desta solução JS . Não faço ideia se há uma maneira melhor.

Descompactado e como funciona

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

Stax , 16 bytes

üxëàè£öΦGΩ│Je5█ò

Execute e depure

Não sei exatamente qual é a classe de complexidade formal, mas é rápida o suficiente para executar todos os casos de teste em um décimo de segundo nesta máquina.

Descompactado, não jogado e comentado, parece com isso. Neste programa, o registro x originalmente contém a entrada.

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

Execute este