As one example, consider looking for runs of m equally spaced squares of the same color embedded in sequences of black and white squares of length n . … For n < 9 there are always some sequences in which no runs of length 3 exist. But it turns out that for n ≥ 9 every single possible sequence contains at least one run of length 3.

Then—somewhat in analogy to retrieving closest memories—one can take a sequence of length n that one receives and find the codeword that differs from it in the fewest elements. … Defining PM[s_] := IntegerDigits[Range[2 s - 1], 2, s] blocks of data of length m can be encoded with Join[data, Mod[data . Select[PM[s], Count[#, 1] > 1 &], 2]] while blocks of length n (and at most one error) can be decoded with Drop[(If[#  0, data, MapAt[1 - # &, data, #]] &)[ FromDigits[Mod[data .

(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.

And as Claude Shannon argued in the 1940s, the length of message needed to be reasonably certain that only one key will satisfy this criterion is equal to the length of the key divided by the redundancy of the language in which the message is written—equal to about 0.5 for English (see below ). In a cryptographic system with keys of length n there will typically be a total of k n possible keys.

For any sequence s this can be done using Module[{c, m = 0}, Map[c[#] = {m, m += Count[s, #]/Length[s]} &, Union[s]]; Function[x, (First[RealDigits[2 # Ceiling[2 -# Min[x]], 2, -#, -1]] &)[Floor[Log[2, Max[x] - Min[x]]]]][ Fold[(Max[#1] - Min[#1]) c[#2] + Min[#1] &, {0, 1}, s]]] Huffman coding of a sequence containing a single 0 block together with n 1 blocks will yield output of length about n ; arithmetic coding will yield length about Log[n] .

Block frequencies [in sequences] In any repetitive sequence the number of distinct blocks of length m must become constant with m for sufficiently large m . … Pictures (b), (c) and (d) show the simplest cases where this occurs (for length 3 {1  {1, 1, 1, 0, 0, 0}, 0  {1, 0}} also works). … In both cases equal frequencies of blocks are obtained only for sequences of length exactly 2 j .

The maximal length turns out always to be realized for the simple parity function Xor , as well as its negation. … (Other functions with maximal length are never additive, at least for n ≤ 4 .)

Cyclic tag systems which allow any value for each element can be obtained by adding the rule CTStep[{{r_, s___}, {n_, a___}}] := {{s, r}, Flatten[{a, Table[r, {n}]}]} The leading elements in this case can be obtained using CTListStep[{rules_, list_}] := {RotateLeft[rules, Length[list]], With[{n = Length[rules]}, Flatten[Apply[Table[#1, {#2}] &, Map[Transpose[ {rules, #}] &, Partition[list, n, n, 1, 0]], {2}]]]}

Runs of digits [in numbers] One can consider any base 2 digit sequence as consisting of successive runs of 0's and 1's, constructed from the list of run lengths by Fold[Join[#1, Table[1 - Last[#1], {#2}]] &, {0}, list] This representation is related to so-called surreal numbers (though with the first few digits different). The number with run lengths corresponding to successive integers (so that the n th digit is Mod[Floor[1/2 + Sqrt[2n]], 2] ) turns out to be (1 - 2 1/4 EllipticTheta[2, 0, 1/2] + EllipticTheta[3, 0, 1/2])/2 , and appears at least not to be algebraic.

With any such shift rule, all states lie on cycles, and the lengths of these cycles are the divisors of the size n . Every cycle corresponds in effect to a distinct necklace with n beads; with k colors the total number of these is Apply[Plus, (EulerPhi[n/#] k # &)[Divisors[n]]]/n The number of cycles of length exactly m is s[m, k]/m , where s[m, k] is defined on page 950 .