A standard ternary code for integers is the binary-plus-termination code, which uses the characters 1, 0, and X (for 'end of number').
n | cB(n) |
1 | 1X |
2 | 10X |
3 | 11X |
4 | 100X |
5 | 101X |
n | cb(n) |
1 | X |
2 | 0X |
3 | 1X |
4 | 00X |
5 | 01X |
If the duration of the X character is the same as the duration of the 0 and 1 then the probabilities are
n | cb(n) | Pb(n) |
1 | X | 1/3 |
2 | 0X | 1/9 |
3 | 1X | 1/9 |
4 | 00X | 1/27 |
5 | 01X | 1/27 |
Asymptotically, \[ Pb(n) ~ 1/n^r \] for some $r$.
Here's an alternative ternary code for integers based on different character durations. Let the durations of 0 and 1 be
character | duration |
0 | 1 unit |
1 | 2 units |
Here is such a code.
n | c(n) |
1 | X |
2 | 0X |
3 | 00X |
4 | 1X |
5 | 000X |
6 | 01X |
7 | 10X |
8 | 0000X |
9 | 001X |
10 | 010X |
11 | 100X |
12 | 11X |
13 | 00000X |
14 | 0001X |
15 | 0010X |
16 | 0100X |
17 | 011X |
18 | 1000X |
19 | 101X |
20 | 110X |
21 | 000000X |
The code can be generated by the fibonacci game that Graeme learned from John Conway. Each 0 means "move along the row". Each 1 means "transfer to the row labelled by the current integer". X means "read out the current integer". Notice the patterns in this code.
This code assigns a non-increasing probability to the integers. Jumps in the probability occur at the fibonacci numbers. In the following table the last column is the count $ 2 1(c(n)) + 0(c(n))$ that appeared in equation \ref{eq.2}:
Table X | ||
---|---|---|
n | c(n) | log 1/P (scaled) |
1 | X | 0 |
2 | 0X | 1 |
3 | 00X | 2 |
4 | 1X | 2 |
5 | 000X | 3 |
6 | 01X | 3 |
7 | 10X | 3 |
8 | 0000X | 4 |
9 | 001X | 4 |
10 | 010X | 4 |
11 | 100X | 4 |
12 | 11X | 4 |
13 | 00000X | 5 |
14 | 0001X | 5 |
15 | 0010X | 5 |
16 | 0100X | 5 |
17 | 011X | 5 |
18 | 1000X | 5 |
19 | 101X | 5 |
20 | 110X | 5 |
21 | 000000X | 6 |
Note:
Table Y | ||
---|---|---|
n | c(n) | log 1/P (scaled) |
1 | X | 0 |
2 | 0X | 1 |
3 | 00X | 2 |
4 | 1X | 2 |
5 | 000X | 3 |
6 | 01X | 3 |
7 | 10X | 3 |
8 | 0000X | 4 |
9 | 001X | 4 |
10 | 010X | 4 |
11 | 100X | 4 |
12 | 11X | 4 |
Table Z | |||
---|---|---|---|
13 | 0 | 0000X | 5 |
14 | 0 | 001X | 5 |
15 | 0 | 010X | 5 |
16 | 0 | 100X | 5 |
17 | 0 | 11X | 5 |
18 | 1 | 000X | 5 |
19 | 1 | 01X | 5 |
20 | 1 | 10X | 5 |
21 | 000000X | 6 |
Connections:
The fibonacci table. Each row is a fibonacci series. Each integer from 1 upwards appears exactly once in the table proper, and can be located by a unique binary string as described above.
Row number Reminder number The table proper ---------- --------------- ---------------------------------------------------- 0 1 1 2 3 5 8 13 21 ... 1 3 4 7 11 18 29 ... 2 4 6 10 16 26 42 68 3 6 9 15 24 39 ... 4 8 12 20 32 52 ... 5 9 14 23 37 60 ... 6 11 17 28 45 .... 7 12 19 ...... 8 14 22 ... 9 16 25 41 ...
Note that we can associate with each row a count, which is the weighted number of digits required to get to that row. Then if we sort the rows by that count, the sequence of integers moves through the table strictly in accordance with a triangular expanding region where the triangle has slope 1. If you add diagonal lines to the table below, it might look right. Slide a piece of paper over the table and see the integers appear almost in sequence. [You need to superpose rows with equal count, for best effect!]
Row number Reminder number The table proper and COUNT ---------- --------------- ---------------------------------------------------- 0 0 1 1 2 3 5 8 13 21 ... 1 2 3 4 7 11 18 29 ... 2 3 4 6 10 16 26 42 68 3 4 6 9 15 24 39 ... 4 4 8 12 20 32 52 ... 5 5 9 14 23 37 60 ... 6 5 11 17 28 45 .... 7 5 12 19 ...... 8 6 14 22 ... 9 6 16 25 41 ...
Non-constructive proof of the theorem that the
Fibonacci table contains every integer exactly once.
When we started thinking about this code for integers, one of our motivations was the idea that this code might provide a way to assign a smoother monotonic distribution on integers than \[ Pb(n) = \frac{1}{Z(\alpha)} \exp(-\alpha l(n)) \frac{1}{2^{l(n)}}, \] which has jumps between plateaus at the powers of two.
We have hunted through hundreds of rules for generating fibonacci-code strings, either starting from the head or from the tail, trying to find a generative probabilistic model that gives a smooth monotone distribution. We got close, but never found a solution that was monotone for all n.
What we did find, however, was a smooth generative model for the standard binary code! It is very simple. The resulting distribution is the classic
1/(n*(n+1))distribution.
The string is generated from the head, extending its tail by one bit at a time. The initial number is n=1, and the probability is 1.
When in state n, the choices are:
|
This code is demonstrated by BinaryDecode.py.
The string is generated from the tail, extending its head by one bit at a time. The initial number is n=1, and length is L=0.
When in state n, the choices are:
|
This is the 'fibonacci table' algorithm. Each 0 means 'move right along the current row'; each 1 means 'change to row n'.
The initial state is (n,p)=(1,1). [p denotes 'predecessor'.]
|
The string is created from the tail. The procedure follows the colour table Y,Z given earlier.
We make use of the standard fibonacci sequence F(0) = 1; F(1) = 1; F(2)=2; F(3)=3; F(4)=5...
The initial state is the integer to be encoded, n. The algorithm is given in Encode2.py.
|
The string is generated from the tail, extending its head by one bit at a time. The initial number is n=1, and length is L=0. This generator makes use of the standard fibonacci sequence F[0] = 1; F[1] = 1; F[2]=2; F[3]=3; F[4]=5...
When in state n, the choices are:
|