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

Author

Indranil Ghosh, Jan 16 2017

Keywords

• nonn
• base

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

Examples

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

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.

Crossrefs

Cf. A140341, A281149.

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

Programs

Python

import math
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)
				

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