Variable-length integer codes based on the Goldbach conjecture, and other additive codes
Peter M. Fenwick · IEEE Transactions on Information Theory · 2002
This article introduces a new family of variable-length codes for the integers, initially based on the Goldbach conjecture that every even integer is the sum of two primes. For an even integer we decompose the value into its two constituent primes and encode the ordinal numbers of those primes with an Elias (1975) /spl gamma/ code. The method is then elaborated to handle odd integers. The article then develops a more general method of encoding any integer as the sum of two integers and developing suitable basis sets of integers. Although the codes which are generated by these methods are characterized by widely varying and unpredictable lengths, they are over some ranges shorter than most other variable-length codes.