A140341 The number of bits needed to write the universal code for an Elias delta coding, the simplest asymptotically optimal code.

1, 4, 4, 5, 5, 5, 5, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11

Offset: 1

Author

David A. Scott (biject.bwts(AT)gmail.com), May 29 2008

Keywords

• nonn
• easy

Comments

A129972 is the number of bits for Elias gamma coding 1, 3, 3, 5 and A130233 is the number of bits for Fibonacci coding of integers 2, 3, 4, 4, 5, But Elias gamma and Fibonacci coding are not asymptotically optimal.

Examples

			The Elias Delta Code for 10 is '11000010', having 8 bits. So, a(10) = 8. - _Indranil Ghosh_, Jan 17 2017
		

References

• David Salomon, Variable-length Codes for Data Compression, Springer Verlag, 2007, 191 pp.

Links

• Indranil Ghosh, Table of n, a(n) for n = 1..10000
• Debra A. Lelewer and Daniel S. Hirschberg, Data Compression. See Section 3, Elias Delta.
• Hugh E. Williams and Justin Zobel, Compressing integers for fast file access, The Computer Journal 42 (1999), pp. 193-201.

Crossrefs

Cf. A281150 - Indranil Ghosh, Jan 17 2017

Programs

PARI

a(n)=my(b=log(n+.5)\log(2));b+log(b+1.5)\log(2)*2+1 \\ Charles R Greathouse IV, Mar 21 2012