Hilbert's binary Hotel

Question

In this challenge you will be asked to implement any function (or full program) that fulfills two properties. Those properties are:

• Your function must be an injective (reversible) function from the polynomials with non-negative integer coeffecients to the non-negative integers. This means no two unequal inputs can map to an equal output.

• Your function must preserve the total number of "on bits" from its input to its output. This means if you count the 1 bits of each coefficient of the polynomial, their sum should be the same as the number of 1 bits in the binary representation of the output. For example 9 is 1001 in binary so it has 2 1 bits.

---

IO

A non-negative integer polynomial is the same as a infinite list of non-negative integers such that after a certain point all the integers are zero. Thus, polynomials may be represented either by infinite lists (although this is probably undesirable) or by finite lists with implicit zeros after the end of the list.

The key distinction between polynomials and finite lists is that adding a zero to the end of a list will change the list:

While adding a zero to the end of a polynomial does not change its value:

Thus if your function takes a finite list representing a polynomial as input, adding a zero must not change its result.

When representing polynomials as lists, you may represent them either with the first or last entry representing the constant term. For example you could have either of the following possibilities:

In the first case, adding zeros to the end of the list should not change the result; in the second case, adding zeros to the front of the list should not change the result.

Of course if your language supports polynomials you may take those as inputs.

Output should be a non-negative integer output via any standard methods.

---

This is code-golf so answers will be scored in bytes, with fewer bytes being better.

Answer 1

Jelly, 8 bytes

BFṢḄæ«ÆẸ

Try it online!

Left inverse, 5 bytes

Bċ0ÆE

Try it online!

How it works

BFṢḄæ«ÆẸ  Main link. Argument: A (array)

B         Binary; convert each integer in A to base 2.
 F        Flatten; concatenate the resulting binary arrays.
  Ṣ       Sort the resulting bit array.
   Ḅ      Convert from base 2 to integer, yielding an integer x with as much set
          bits as there are set bits in A.
      ÆẸ  Unexponents; convert A = [a1, a2, ...] to y = (p1**a1 + p2**a2 + ...),
          where pn is the n-th prime number.
          By the fundamental theorem of arithmetic, the resulting integer is unique
          for each array A without trailing zeroes.
    æ«    Bitshift left; compute x * 2**y.

Answer 2

Wolfram Language (Mathematica), 36 20 bytes

x#/.x->2^(#/.x->2)!&

Try it online!

Takes a polynomial f(x) as input. Evaluates y*f(y), where y = 2^(f(2)!). Regrettably, this means that the outputs get pretty large.

Evaluating y*f(y) will preserve the number of 1-bits whenever y is a power of 2 bigger than any coefficient, which is true for the value chosen above. We choose y = 2^(f(2)!) to make the result injective:

• Two different inputs with the same value of y will give different outputs because we're essentially reading two different numbers in base y.
• If we fix k=f(2) and therefore y, the smallest value of y*f(y) is achieved when the input is a constant polynomial equal to k and the largest value is achieved when the input is the polynomial giving the base-2 expansion of k. In the first case, y*f(y) = 2^(k!)*k, and in the second case, y*f(y) < 2^(k!*ceil(lg k)), which is less than 2^((k+1)!)*(k+1).
• As a result, for two polynomials f and g with f(2) < g(2), the integer we get from f will be less than the integer we get from g.

Answer 3

Wolfram Language (Mathematica), 61 bytes

Tr[2^((2#2-1)2^#)&@@@Position[Reverse/@#~IntegerDigits~2,1]]&

Try it online!

Two positive integers can be mapped to a single positive integer. Let a, b be two positive integers. Then a, b -> (2a - 1) 2^(b-1) is a bijection from NxN to N.

This function finds the position of all 1 bits in the input (from the 1s place), and applies an injective-only variant of the above map to each position. Then, each resulting number is raised to the power of two, and all numbers are added together (which is okay since we applied an injective NxN -> N map).

For example:

{1, 2, 3}
{{1}, {1, 0}, {1, 1}}             (* Convert to binary *)
{{1}, {0, 1}, {1, 1}}             (* Reverse each *)
{{1, 1}, {2, 2}, {3, 1}, {3, 2}}  (* Position of 1s *)
{2, 12, 8, 24}                    (* Inject to N *)
{4, 4096, 256, 16777216}          (* Raise to the power of 2 *)
16781572                          (* Add *)

Inverse function (124 bytes)

##+#&~Fold~#&@*Reverse/@Normal@SparseArray[{Log2[j=#~BitAnd~-#],(#/j+1)/2}->1&@@@(Reverse[#~IntegerDigits~2]~Position~1-1)]&

Here's an inverse function to test for injectivity.

Try it online!

Answer 4

Python 2, 118 117 114 103 100 bytes

100 bytes by Jonathan Frech:

a=input()
while a[0]<1:a.pop(0)
y="".join("2"+bin(v)[2:]for v in a)
print~-2**y.count("1")<<int(y,3)

Try it online!

103 bytes with a golfing possibility¹

a=input()
while a[0]<1:a.pop(0)
x="".join(map(bin,a))
print~-(1<<x.count("1"))<<int(x.replace(*"b2"),3)

Try it online!

-15 bytes thanks to Jonathan Frech

It creates a number that first contains the "on bits" and then the unary representation of the array interpreted as a trinary number.

The trinary number is created by converting the numbers to binary strings (0bNNN), then replacing b with 2.

¹I could have saved 14 bytes by converting it to a base-12 number instead, but TIO ran out of memory so I decided to use this.

Answer 5

05AB1E, 14 bytes

gÅpImPoIbS{2β*

Try it online!

Yields the same results as Dennis' Jelly solution, yet the technique is slightly different.

How?

Let's try the input [1, 2, 3]:

gÅpImPoIbS{2β* | Full program.
               | STACK: [[1, 2, 3]]
               |
g              | Push the length.
               | STACK: [3]
 Åp            | Generate the first N primes.
               | STACK: [[2, 3, 5]]
   Im          | Push the input, and apply pairwise exponentiation.
               | STACK: [2, 9, 125]
     P         | Push the product.
               | STACK: 2250
      o        | Push 2 ** N.
               | STACK: 2 ** 2250 (way too large)
       Ib      | Push the input and convert to binary.
               | STACK: [2 ** 2250, ['1', '10', '11']].
         S{    | Sort all the characters.
               | STACK: [2 ** 2250, ['0', '1', '1', '1', '1']]
           2β  | Convert from binary.
               | STACK: [2 ** 2250, 15]
             * | Multiplication.
               | STACK: [2 ** 2250 * 15]
               | Implicitly print the top of the stack (2 ** 2250 * 15).

Answer 6

Python 2, 74 bytes

r='print 0';s='<<'
for n in input():r+=oct(n)[:0:-1];s+='0'+'1'*n
exec r+s

Try it online!

Answer 7

JavaScript 6, 96 83 Bytes

x=>(t=x.map(k=>(x[0]+=k)&&2+k.toString(2)).join``).replace(/0|2/g,'')+'0'.repeat(t)

outputs a binary expression

([1,2]) => 3*2^21210(Decimal)
([0,1,2]) => 3*2^21210
([1,2,0]) => 3*2^2121020
([1,2,3,4]) => 31*2^212102112100(Threotically)