Bijective mapping from integers to a variable number of trits

Question

This challenge is a harder version of this one.

A variable number of trits is an array of 0 or more trits (a trit is a ternary digit). So [0, 2, 2, 1] is a variable number of trits, but so is [].

Write a function or program that, given an non-negative integer returns a variable number of trits such that every integer has a one-to-one (bijective) mapping with an array.

There are an infinite amount of such mappings, you are free to construct one as you please, but it must be one-to-one. Your mapping must conceptually be one-to-one for an arbitrarily sized integer, but it's OK if your implementation fails for large integers due to numerical limits of types in your preferred language (e.g. C's int).

As an example of what is not a one-to-one mapping, is simply listing the ternary digits of the integer. In such a system 5 becomes [1, 2] (because 1*3^1 + 2*3^0 = 5), but it's not one-to-one, because [0, 1, 2] also means 5 (because 0*3^2 + 1*3^1 + 2*3^0 = 5).

It should be fairly obvious that a mapping is not one-to-one if it skips an integer (e.g. it doesn't work for 5), but I'd like to make it clear that skipping a variable trit array is also not one-to-one. You must map to every possible variable trit array, including [].

Bonus challenge

You will be awarded the official Super Smaht® Award™ if your answer includes an algorithm (not necessarily in your golfed program) that not only works for base 2 or 3, but for all bases.

---

Shortest code in bytes wins.

Answer 1

Pyth, 6 bytes

tjyhQ3

Explanation:

    Q    Input number.
   h     Add 1.
  y      Multiply by 2.
 j   3   Convert to base 3 as a list.
t        Remove the first element.

Test suite

Inverse function: Pyth, 14 bytes

t/i+-2%sQ2Q3 2

Explanation:

        Q        Input list.
       s         Sum.
      %  2       Modulo 2.
    -2           Subtract from 2.
   +      Q      Prepend to input list.
  i        3     Convert from base 3.
 /           2   Divide by 2.
t                Subtract 1.

Test suite

The bijection looks like this:

0: []
1: [1]
2: [0]
3: [2]
4: [0, 1]
5: [1, 0]
6: [1, 2]
7: [2, 1]
8: [0, 0]
9: [0, 2]
10: [1, 1]
11: [2, 0]
12: [2, 2]
13: [0, 0, 1]
14: [0, 1, 0]
15: [0, 1, 2]
16: [0, 2, 1]
17: [1, 0, 0]
18: [1, 0, 2]
19: [1, 1, 1]
⋮

General base

To make this work in any base b, simply replace 3 with b, 2 with (b − 1), and y with *(b − 1).

Answer 2

JavaScript, 24 bytes

f=n=>n?f(--n/3|0)+n%3:''

Try it online!

Implements the standard ternary bijective numeration, except with the digits reduced by 1.

How it works: First, check if n is 0, returning the empty string if so. Otherwise, n is pre-decremented, and that value is divided by 3 and rounded down (|0 is a short way to do the rounding) and passed recursively to f – the final digit will contribute 1, 2, or 3, while the rest contribute a multiple of 3, so \$\lfloor\frac{n-1}{3}\rfloor\$ is the value the non-final digits should represent on their own. Finally, n%3 appends the final digit, reduced by 1 from the standard (n having already been decremented).

Answer 3

Jelly, 3 bytes

ḃ3’

Try it online!

ḃ3   Convert to bijective base 3
  ’  Decrement all digits

Inverse, 3 bytes

‘ḅ3

Try it online!

‘    Increment all digits
 ḅ3  Convert from base 3

Both versions can be made to use an arbitrary base by removing the 3.

Answer 4

Jelly, 12 bytes

ḤR‘b3Ḣ’$Ðḟị@

There is no empty list in Jelly; it is represented as 0 (an integer not a list).

For other bases: change Ḥ to ×n and b3 to bn, where n is the intended base.

Try it online!

Test suite.

For other bases

It only costs 11 bytes if given base as second input.

Try it online!

Test suite.

Algorithm

I thought of appending a 1 before the list and then convert it to a ternary.

That way, [0,0] will become 100 = 9 while [0,0,0] will become 1000 = 27.

However, a problem arises: that 2011 and 1011 both map to [0,1,1].

I only need numbers whose ternary representation starts with 1.

Therefore, I generated those whose ternary representation starts with 1, and then use their index instead.

That is, the list begins as [1, 3, 4, 5, 9, 10, 11, 12, 13, 14, 15, 16, 17, ...].

Therefore:

• 1 will be mapped to 1
• 2 will be mapped to 3
• 3 will be mapped to 4
• 4 will be mapped to 5
• 5 will be mapped to 9
• n will be mapped to a(n) where a is that list.

There's another problem: both 0 and 1 are mapped to the empty list. Therefore, I removed 1 from the list, making a = [3, 4, 5, 9, 10, 11, 12, 13, 14, 15, 16, 17, ...].

Those are the integers whose ternary representation starts with 1, except 1.

The same algorithm can be applied to other bases.

Answer 5

Jelly, 6 bytes

‘Ḥb3ṫ2

Translation of Kaseorg's answer in Pyth.

Try it online!

Hardcoded base: try it online!

Given base: try it online!

Answer 6

CJam, 9 bytes

ri)_+3b(;

Translation of Kaseorg's answer in Pyth.

Try it online!

Answer 7

JavaScript (ES6), 31 bytes

n=>(n*2+2).toString(3).slice(1)

Since everyone else is translating @AndreasKaseorg's fine answer. Generic version (36 bytes):

b=>n=>(-~n*~-b).toString(b).slice(1)