A281150 Elias delta code for n.

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

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

Cf. A140341, A281149.

Unary(n) = A105279(n-1).

Sequence in context: A169732 A169734 A213317 * A069746 A291346 A191753

Adjacent sequences: A281147 A281148 A281149 * A281151 A281152 A281153

Keyword

nonn,base

Author

Indranil Ghosh, Jan 16 2017

Status

approved