Notes

Section 5: Data Compression

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]],#}]&[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.

Take @@ RealDigits[(N[#,N[Log[10, #] + 3]] & )[n Sqrt[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)

Join@@Last/@NestList[{#[[2]], Join[Join[{1,0},Rest@#]& /@#[[2]],Join[{1,0},#]&/@#[[1]]]}&,{{},{{1}}},n-3]

From Stephen Wolfram: A New Kind of Science [citation]