[Methods of] encoding sequences by integers

In many constructions it is useful to be able to encode a list of integers of any length by a single integer. (See e.g. page 1127.) One way to do this is by using the Gödel number Product[Prime[i]^list〚i〛, {i, Length[list]}]. An alternative is to use the Chinese Remainder Theorem. Given p = Array[Prime, Length[list], PrimePi[Max[list]] + 1] or any list of integers that are all relatively prime and above Max[list] (the integers in list are assumed positive)

CRT[list_, p_] := With[{m = Apply[Times, p]}, Mod[Apply[Plus, MapThread[#1 (m/#2)^EulerPhi[#2] &, {list, p}]], m]]

yields a number x such that Mod[x, p]  list. Based on this

LE[list_] := Module[{n = Length[list], i = Max[MapIndexed[#1 - #2 &, PrimePi[list]]] + 1}, CRT[PadRight[list, n + i], Join[Array[Prime[i + #] &, n], Array[Prime, i]]]]

will yield a number x that can be decoded into a list of length n using essentially the so-called Gödel β function

Mod[x, Prime[Rest[NestList[NestWhile[# + 1 &, # + 1, Mod[x, Prime[#]]  0 &] &, 0, n]]]]