xkcd-Style Page Numbering

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. 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 => 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 1

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.

Demonstration.

It makes use of .f, Pyth's "loop until n matches have been found" function.

Answer 2

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.

Answer 3

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 4

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.

Answer 5

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.

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 6

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 7

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.

Answer 8

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 9

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 10

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 11

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.

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 12

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 13

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 14

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 15

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 16

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 17

Turing Machine Code, 333 293 bytes

I'm using an encoding as used here.

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.

Answer 18

Perl, 66 bytes

Number is to be input through STDIN.

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

Answer 19

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 20

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.

Answer 21

JavaScript (Node.js), 40 bytes

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

Try it online!

This solution does not work on last testcase. It just cause stack overflow on it.

Answer 22

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 23

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 24

Japt, 31 bytes

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

Try it online!

Almost direct port of this JS solution. 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 25

Stax, 16 bytes

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

Run and debug it

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

Answer 26

CoffeeScript, 92 69 bytes

Based of Qwertiy's answer 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