Pack sequences of non-negative integers Let N be the set of nonnegative integers, i.e. {0, 1, 2, 3, ...}.

Let c0(N) be the set of all infinite sequences in N that converge to 0, i.e. { (xn) &in; NN | xn &rarr; 0 as n &rarr; &infin;}.

c0(N) can be equivalently written as the set of all finite sequences of natural numbers, such that there are no trailing zeroes. The infinite sequence of all zeroes (corresponding to a finite sequence of length 0) is an element of c0(N).

Your task is to implement a bijection in your language between N and c0(N), in as few characters as possible. This means every number in N corresponds to a unique item of c0(N), and vice versa. Do this by defining two functions: f, going from N and c0(N); and g, the inverse of f. The length in bytes of these two definitions is your score.

You may use the largest internal integer and list types of your language, even if they aren't bignums or capable of handling infinite length. However, they should theoretically still be able to terminate with the right answer if the language was modified with a suitable bignum or lazy/infinite list type.

Some suggestions for ways to pack are below. Note that these aren't quite solutions yet and could need some tweaking to work; they're mostly to get the blood flowing.


f(1463616) = f(2^6 * 3^3 * 5^0 * 7^1 * 11^2) = [6, 3, 0, 1, 2] - Factorize the number into primes and read off exponents to get the sequence.
f(64971) = f(0b1111110111001011) = [6, 3, 0, 1, 2] - Expand the number in binary and use 0 as a separator to read strings of ones, representing the sequence in unary.




While this is a code-golf and the shortest answer will win, creative and interesting solutions are encouraged and may be subject to a bounty.
J - 17 char

g=:(f=:_ q:&gt;:)inv


We implement the prime exponent idea with this bijection&mdash;that's what the _ q: is doing, getting a list of the exponents of the primes of a number&mdash;except we also increment the input number by one before doing so, with &gt;:, so that we don't forget 0, who doesn't have its own prime factorization.

For the definition of g, it's exactly what it looks like: instead of writing it ourselves, we just tell J to take the inverse of f. Arguably this is cheating, or just not interesting, but I think that the ability to do this is what makes J such an interesting language: J can often figure things out for you, allowing you to focus on expressing your solution instead of implementing it.

   i. 20
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
   f i. 20  NB. J pads with zeroes on right
0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0
2 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0
1 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0
3 0 0 0 0 0 0 0
0 2 0 0 0 0 0 0
1 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0
2 1 0 0 0 0 0 0
0 0 0 0 0 1 0 0
1 0 0 1 0 0 0 0
0 1 1 0 0 0 0 0
4 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0
1 2 0 0 0 0 0 0
0 0 0 0 0 0 0 1
2 0 1 0 0 0 0 0
   g f i. 20
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19


Proving that this is a bijection is straightforward: the injectivity of this f is a well known fact and, if you assume that J's automagical inverse is correct (which it is), then this is trivial.

If you don't want to take it on faith that J knows how to take the inverse of f, we can inspect its automatic inverse for _&amp;q::

   _&amp;q: b. _1
(p:@i.@# */ .^ ])"1 :.(_&amp;q:)


and then check the definition:

(p:@i.@# */ .^ ])"1 :.(_&amp;q:)  NB. the alleged inverse of _&amp;q:
                    :.(_&amp;q:)  NB. defining _&amp;q:inv inv to be _&amp;q:
(               )"1           NB. operate on rows of the argument
       #                      NB. length of argument
    i.@                       NB. nonnegative integers less than
 p:@                          NB. n-th prime for each integer n
               ]              NB. the argument again
            .^                NB. pointwise exponentiation
         */                   NB. product


and then confirm that J's inverse of f gives the decrement of the result of this:

   &gt;: b. _1  NB. inverse of increment is decrement
&lt;:
   f b. _1   NB. ([: f g) is one way of writing f composed with g
[: &lt;: (p:@i.@# */ .^ ])"1 :.(_&amp;q:)