cp's OEIS Frontend

A380294 The Golomb-Rice encoding of n, with M = A070939(A070939(n)).

%I A380294 #36 Feb 03 2025 21:16:06
%S A380294 1,2,3,8,9,10,11,16,17,18,19,20,21,22,23,48,49,50,51,52,53,54,55,112,
%T A380294 113,114,115,116,117,118,119,240,241,242,243,244,245,246,247,496,497,
%U A380294 498,499,500,501,502,503,1008,1009,1010,1011,1012,1013,1014,1015,2032
%N A380294 The Golomb-Rice encoding of n, with M = A070939(A070939(n)).
%C A380294 For n <= 3 leading zeros are omitted.
%C A380294 In the original Golomb-Rice algorithm, M is an arbitrary power of 2. Here, M is determined as 2^(floor(log_2(floor(log_2(n))+1))+1).
%C A380294 a(2^k) is a divisor of a(2^(k+1)).
%H A380294 Paolo Xausa, <a href="/A380294/b380294.txt">Table of n, a(n) for n = 1..10000</a>
%H A380294 Wikipedia, <a href="https://en.m.wikipedia.org/wiki/Golomb_coding">Golomb coding</a>
%F A380294 a(n) = (2^q - 1) * 2^A070939(m) + r, where m = 2^A070939(A070939(n)), q = floor(n/m) and r = n mod m.
%F A380294 a(n) = a(n-1)+1 for n odd > 1.
%F A380294 a(n) = n if n <= 3.
%e A380294 For n = 42 a(42) = 111110010_2 = 498.
%e A380294 m = 2^(floor(log_2(floor(log_2(n))+1))+1) = 8 and
%e A380294 q = floor(n / m) = 5 and
%e A380294 r = n mod m = 2 and
%e A380294 u = (2^q-1) left shifted by (2^floor(log_2(m)) + 1) = 111110000_2 = 496 and
%e A380294 u + r = 111110010_2 = 498.
%t A380294 A380294[n_] := (2^Quotient[n, #] - 1)*2^BitLength[#] + Mod[n, #] & [2^Nest[BitLength, n, 2]];
%t A380294 Array[A380294, 100] (* _Paolo Xausa_, Feb 03 2025 *)
%o A380294 (Python)
%o A380294 def a(n):
%o A380294     if n <= 3: return n
%o A380294     if n & 1: return a(n-1)+1
%o A380294     m = 1 << (n.bit_length()).bit_length()
%o A380294     q, r = divmod(n, m)
%o A380294     u = ((1 << q) - 1) << m.bit_length()
%o A380294     return u + r
%o A380294 print([a(n) for n in range(1,57)])
%Y A380294 Cf. A000079, A000225, A070939.
%K A380294 nonn,base
%O A380294 1,2
%A A380294 _Darío Clavijo_, Jan 19 2025