cp's OEIS Frontend

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

%I A140341 #14 Aug 06 2024 10:10:09
%S A140341 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,
%T A140341 10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,
%U A140341 10,10,10,10,10,10,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11
%N A140341 The number of bits needed to write the universal code for an Elias delta coding, the simplest asymptotically optimal code.
%C A140341 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.
%D A140341 David Salomon, Variable-length Codes for Data Compression, Springer Verlag, 2007, 191 pp.
%H A140341 Indranil Ghosh, <a href="/A140341/b140341.txt">Table of n, a(n) for n = 1..10000</a>
%H A140341 Debra A. Lelewer and Daniel S. Hirschberg, <a href="http://www.ics.uci.edu/~dan/pubs/DataCompression.html">Data Compression</a>. See Section 3, <a href="http://www.ics.uci.edu/~dan/pubs/DC-Sec3.html">Elias Delta</a>.
%H A140341 Hugh E. Williams and Justin Zobel, <a href="https://citeseerx.ist.psu.edu/pdf/bb198575b767145597e99c9e6781aebc7532f987">Compressing integers for fast file access</a>, The Computer Journal 42 (1999), pp. 193-201.
%e A140341 The Elias Delta Code for 10 is '11000010', having 8 bits. So, a(10) = 8. - _Indranil Ghosh_, Jan 17 2017
%o A140341 (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
%Y A140341 Cf. A281150 - _Indranil Ghosh_, Jan 17 2017
%K A140341 nonn,easy
%O A140341 1,2
%A A140341 David A. Scott (biject.bwts(AT)gmail.com), May 29 2008