Pack sequences of non-negative integers

Question

Let N be the set of nonnegative integers, i.e. {0, 1, 2, 3, ...}.

Let c₀(N) be the set of all infinite sequences in N that converge to 0, i.e. { (x_n) ∈ N^N | x_n → 0 as n → ∞}.

c₀(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 c₀(N).

Your task is to implement a bijection in your language between N and c₀(N), in as few characters as possible. This means every number in N corresponds to a unique item of c₀(N), and vice versa. Do this by defining two functions: f, going from N and c₀(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.

Answer 1

GolfScript, 41 bytes

{[2base[0]/{,}/]-1%}:f{:|;-1{).f|=!}do}:g

Function “f”

[
  2base       # Push the digits of the argument in base 2.
  [0]/        # Split the digits around the 0's. This leaves sequences of 1's.
  {,}/        # Compute the lengths of those sequences.
]-1%          # Reverse the array of the lengths.

The binary expansion of any given non-negative integer in its canonical form may have trailing 0's, but not leading 0's.

Thus, reversing the array is necessary and sufficient to comply with the specification.

Function “g”

:|;           # Save the argument in variable “|” and pop it from the stack.
-1            # Push the integer “-1”.
{             #
  )           # Increment the integer.
  .f|=        # Check whether it is the preimage of “|”.
  !           # If it is not,
}do           # repeat the loop.

Function “g” (alternative)

An alternative, straightforward and efficient implementation of g is

{[-1%{0\{1}*}/]2base}:g

The brute-force approach is much slower, but it is four bytes shorter.

[
  -1%         # Reverse the order of the integer sequence.
  {           # For each integer “N”,
    0         # push 0,
    \{1}*     # followed by “N” 1's.
  }/          #
]             # Convert this bit sequence into an array.
2base         # Convert the array into an integer.

Example

• 1250 is 10011100010 in base 2.

• The lengths of the sequences of consecutive 1's are 1,0,3,0,0,1,0.

• Thus, the sequence corresponding to 1250 is 0,1,0,0,3,0,1.

Proof of work

10000,(;      # Push an array of all integers from 1 to 9999.
{             # For each integer “N”,
  f-1=0=      # if “f(N)” has a trailing zero,
  {0p}*       # print a message.
}/

leaves nothing on the stack, so f is well-defined.

1000,.        # Push the array of all integers from 0 to 999 and duplicate it.
[             #     
  {f g}/      # For each integer “N”, push “g(f(N))”.
]=            # Check if the array of the images matches the original array.

leaves 1 on the stack (using either definition of g).

This means that g is a left inverse of f, so f is injective.

[
  1000,.      # Push the array of all integers from 0 to 999 and duplicate it.
  10%-        # Remove the integers with trailing 0's.
  {           # For each integer “N”,
    10base    # push the array of its digits in base 10,
    .0\+.0\+  # and create copies with one and two leading 0's.
  }/          #
].            # Collect all sequences in an array and duplicate it.
[             #     
  {g f}/      # For each sequence “S”, push “f(g(S))”.
]=            # Check if the array of the images matches the original array.

leaves 1 on the stack (using the second definition of g).

This means that g is a right inverse of f, so f is surjective.

Answer 2

J - 17 char

g=:(f=:_ q:>:)inv

We implement the prime exponent idea with this bijection—that's what the _ q: is doing, getting a list of the exponents of the primes of a number—except we also increment the input number by one before doing so, with >:, 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 _&q::

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

and then check the definition:

(p:@i.@# */ .^ ])"1 :.(_&q:)  NB. the alleged inverse of _&q:
                    :.(_&q:)  NB. defining _&q:inv inv to be _&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:

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

Answer 3

Jelly, 7 + 3 = 10 or 11 bytes, language postdates question

JÆN*¹P’
‘ÆE

Try it online!

Defines an packing function 1Ŀ and an unpacking function 2Ŀ. These could be defined in two separate programs, but if you define them both in a single program, you need a newline to separate the definitions. Thus I'm not 100% sure how to count it.

Explanation

This packs the sequence into a product of primes, which was one of the suggestions in the question.

Packing

JÆN*¹P’
J         Replace each element of {the input} by its index
 ÆN       Replace each index n by the nth prime number
   *      Raise each element to the power of
    ¹       {the original input}
     P    Take the product of all the elements
      ’   Subtract 1 (so that some sequence maps to 0, making a bijection)

Unpacking

‘ÆE
‘         Add 1 (undo the subtraction earlier)
 ÆE       Output the number of times each prime divides the current value

As can be seen, unpacking is very simple here due to the builtin ÆE, which is why I selected this format. There's no builtin to do the packing, but it has a fairly terse implementation too.

Jelly, 3 + 3 = 6 or 7 bytes, with some help from @Dennis

OK, apparently there is a builtin to do the packing…

ÆẸ’
‘ÆE

Try it online!

The explanation above still works; it's just that all of JÆN*¹P have been replaced by a builtin.

Answer 4

Python, 257 265B

from itertools import*
T=lambda i:[list(a)for l in range(i)for a in product(range(i-l+3),repeat=l+1)if a[-1]>0and sum(a)==i-l]
def f(N):
 A,i=[[0]],0
 while len(A)<=N:A+=T(i);i+=1
 return A[N]
def g(t):
 A,i=[[0]],0
 while t not in A:A+=T(i);i+=1
 return A.index(t)

To list every sequence, for each integer i, for each length l

0 :  1
1 :  2
2 :  0 1
3 :  3
4 :  0 2
5 :  1 1
6 :  0 0 1
7 :  4
8 :  0 3
9 :  1 2
10 :  2 1
11 :  0 0 2
12 :  0 1 1
13 :  1 0 1
14 :  0 0 0 1
15 :  5
16 :  0 4
17 :  1 3
18 :  2 2
19 :  3 1
20 :  0 0 3
21 :  0 1 2
22 :  0 2 1
23 :  1 0 2
24 :  1 1 1
25 :  2 0 1
26 :  0 0 0 2
27 :  0 0 1 1
28 :  0 1 0 1
29 :  1 0 0 1
30 :  0 0 0 0 1

so f(256)=[9], and g([4,2,0,3])=2254. NB that this is SLOW for large numbers.

Answer 5

MATL, 8+3 = 11 bytes

Function f

QYF

Nice and simple, outputs the exponents of the prime factor decomposition of the input+1, for instance input of 1752922079 gives [5, 3, 1, 4, 0, 2]

Function g

Takes a finite vector of non-negative integers and outputs a single non-negative integer.

n:YqG^pq

Explanation

n       % find the length of the input
:       % make a range that long
Yq      % use the range to find the first n primes
G       % paste the input vector again
^       % take powers element wise
p       % product of elements
q       % decrement by 1 so 0 is included
        % (implicit) convert to string and display

For instance, input [5, 3, 1, 4, 0, 2] first pushes the vector [2, 3, 5, 7, 11, 13], then combines them into [32, 27, 5, 2401, 1, 169] before taking the product, giving 1752922080 and decrementing to give the final answer 1752922079.