A129972 -id:A129972 - cp's OEIS frontend

A281149 Elias gamma code (EGC) for n.

1, 100, 101, 11000, 11001, 11010, 11011, 1110000, 1110001, 1110010, 1110011, 1110100, 1110101, 1110110, 1110111, 111100000, 111100001, 111100010, 111100011, 111100100, 111100101, 111100110, 111100111, 111101000, 111101001, 111101010, 111101011, 111101100, 111101101, 111101110

Offset: 1

Indranil Ghosh, Jan 16 2017

This sequence is the binary equivalent of A171885 for n>=1 and is also mentioned in the example section of the same.
The number of bits of a(n) is equal to A129972(n).
Unary(n) = A105279(n-1).

			For n = 9, first part is "1110" and the second part is "001". So, a(9) = 1110001.

Indranil Ghosh, Table of n, a(n) for n = 1..10000
J. Nelson Raja, P. Jaganathan and S. Domnic, A New Variable-Length Integer Code for Integer Representation and Its Application to Text Compression, Indian Journal of Science and Technology, Vol 8(24), September 2015.

Cf. A105279 (unary code for n), A129972, A171885.

def unary(n):
    return "1"*(n-1)+"0"
def elias_gamma(n):
    if n ==1:
        return "1"
    k=int(math.log(n,2))
    fp=unary(1+k)    #fp is the first part
    sp=n-2**(k)      #sp is the second part
    nb=k             #nb is the number of bits used to store sp in binary
    sp=bin(sp)[2:]
    if len(sp)

For a given integer n, it is stored in two parts. The first part equals 1+floor(log_2 n) and the second part equals n-2^(floor(log_2 n)). The first part is stored in unary and the second part is stored in binary using floor(log_2 n) bits. Now the first and the second parts are concatenated to give the answer.

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

Original entry on oeis.org

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

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

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.

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

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

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.

Cf. A281150 - Indranil Ghosh, Jan 17 2017

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

cp's OEIS Frontend

A281149 Elias gamma code (EGC) for n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula