Pack sequences of non-negative integers
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:)