cp's OEIS Frontend

A281150 Elias delta code for n.

%I A281150 #17 May 05 2025 14:17:45
%S A281150 1,1000,1001,10100,10101,10110,10111,11000000,11000001,11000010,
%T A281150 11000011,11000100,11000101,11000110,11000111,110010000,110010001,
%U A281150 110010010,110010011,110010100,110010101,110010110,110010111,110011000,110011001,110011010
%N A281150 Elias delta code for n.
%C A281150 The number of bits in a(n) is equal to A140341(n).
%C A281150 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
%D A281150 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
%H A281150 Indranil Ghosh, <a href="/A281150/b281150.txt">Table of n, a(n) for n = 1..10000</a>
%H A281150 J. Nelson Raja, P. Jaganathan and S. Domnic, <a href="http://dx.doi.org/10.17485/ijst/2015/v8i24/80242">A New Variable-Length Integer Code for Integer Representation and Its Application to Text Compression</a>, Indian Journal of Science and Technology, Vol 8(24), September 2015.
%F A281150 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).
%e A281150 For n = 9, the first part is "11000" and the second part is "001". So a(9) = 11000001.
%o A281150 (Python)
%o A281150 import math
%o A281150 def unary(n):
%o A281150     return "1"*(n-1)+"0"
%o A281150 def elias_gamma(n):
%o A281150     if n==1:
%o A281150         return "1"
%o A281150     k=int(math.log(n, 2))
%o A281150     fp=unary(1+k)    #fp is the first part
%o A281150     sp=n-2**(k)      #sp is the second part
%o A281150     nb=k             #nb is the number of bits used to store sp in binary
%o A281150     sp=bin(sp)[2:]
%o A281150     if len(sp)<nb:
%o A281150         sp=("0"*(nb-len(sp)))+sp
%o A281150     return fp+sp
%o A281150 def elias_delta(n):
%o A281150     if n==1:
%o A281150         return "1"
%o A281150     k=int(math.log(n, 2))
%o A281150     fp=elias_gamma(1+k)#fp is the first part
%o A281150     sp=n-2**(k)        #sp is the second part
%o A281150     nb=k               #nb is the number of bits used to store sp in binary
%o A281150     sp=bin(sp)[2:]
%o A281150     if len(sp)<nb:
%o A281150         sp=("0"*(nb-len(sp)))+sp
%o A281150     return fp+sp
%Y A281150 Cf. A140341, A281149.
%Y A281150 Unary(n) = A105279(n-1).
%K A281150 nonn,base
%O A281150 1,2
%A A281150 _Indranil Ghosh_, Jan 16 2017