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,2

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.

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.

Example

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

Prog

(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

Crossrefs

Cf. A281150 - Indranil Ghosh, Jan 17 2017

Sequence in context: A167770 A080800 A253443 * A332609 A244234 A237449

Adjacent sequences: A140338 A140339 A140340 * A140342 A140343 A140344

Keyword

nonn,easy

Author

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

Status

approved