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

Comments

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).

Links

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.

Formula

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.

Example

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

Prog

(Python)
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)<nb:
........sp=("0"*(nb-len(sp)))+sp
....return fp+sp

Crossrefs

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

Sequence in context: A063010 A215022 A094027 * A204582 A204583 A092633

Adjacent sequences: A281146 A281147 A281148 * A281150 A281151 A281152

Keyword

nonn,base

Author

Indranil Ghosh, Jan 16 2017

Status

approved