login
A281149
Elias gamma code (EGC) for n.
6
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
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
KEYWORD
nonn,base
AUTHOR
Indranil Ghosh, Jan 16 2017
STATUS
approved