Number representations

The sequence of 1's and 0's representing a number n are obtained as follows:

(a) *Unary.* Table[0, {n}]. (Not self-delimited.)

(b) *Ordinary base 2.* IntegerDigits[n, 2]. (Not self-delimited.)

(c) *Length prefixed.* Starting with an ordinary base 2 digit sequence, one prepends a unary specification of its length, then a specification of that length specification, and so on:

(Flatten[{Sign[-Range[1 - Length[#], 0]], #}] &)[Map[Rest, IntegerDigits[Rest[Reverse[NestWhileList[Floor[Log[2, #] &, n + 1, # > 1 &]]],2]]]

(d) *Binary-coded base 3.* One takes base 3 representation, then converts each digit to a pair of base 2 digits, handling the beginning and end of the sequence in a special way.

Flatten[IntegerDigits[Append[2 - With[{w = Floor[Log[3, 2n]]}, IntegerDigits[n - (3^{w + 1} - 1)/2, 3, w]], 3], 2, 2]]

(e) *Fibonacci encoding.* Instead of decomposing a number into a sum of powers of an integer base, one decomposes it into a sum of Fibonacci numbers (see page 902). This decomposition becomes unique when one requires that no pair of 1's appear together.

Apply[Take, RealDigits[(N[#, N[Log[10, #] + 3]] &)[n √5/GoldenRatio^{2} + 1/2], GoldenRatio]]

The representations of all the first Fibonacci[n] - 1 numbers can be obtained from (the version in the main text has Rest[RotateLeft[Join[#, {0, 1}]]] & applied)

Apply[Join, Map[Last, NestList[{#〚2〛], Join[Map[Join[{1, 0}, Rest[#]] & , #〚2〛], Map[Join[{1, 0}, #] &, #〚1〛]]} &, {{}, {{1}}}, n-3]]]