login
A281150
Elias delta code for n.
6
1, 1000, 1001, 10100, 10101, 10110, 10111, 11000000, 11000001, 11000010, 11000011, 11000100, 11000101, 11000110, 11000111, 110010000, 110010001, 110010010, 110010011, 110010100, 110010101, 110010110, 110010111, 110011000, 110011001, 110011010
OFFSET
1,2
COMMENTS
The number of bits in a(n) is equal to A140341(n).
a(n) is the prefix-free encoding of n-1 defined on pages 180-181 of Shallit (2008). - N. J. A. Sloane, Mar 18 2019
REFERENCES
Shallit, Jeffrey. A second course in formal languages and automata theory. Cambridge University Press, 2008. See E(m) on page 181. - N. J. A. Sloane, Mar 18 2019
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, a(n) is composed of 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 Elias Gamma Code and the second part is stored in a binary using floor(log_2 n) bits. The first and the second parts are concatenated to give a(n).
EXAMPLE
For n = 9, the first part is "11000" and the second part is "001". So a(9) = 11000001.
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
def elias_delta(n):
....if n==1:
........return "1"
....k=int(math.log(n, 2))
....fp=elias_gamma(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
Unary(n) = A105279(n-1).
Sequence in context: A169732 A169734 A213317 * A069746 A291346 A191753
KEYWORD
nonn,base
AUTHOR
Indranil Ghosh, Jan 16 2017
STATUS
approved