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

1, 2, 3, 8, 9, 10, 11, 16, 17, 18, 19, 20, 21, 22, 23, 48, 49, 50, 51, 52, 53, 54, 55, 112, 113, 114, 115, 116, 117, 118, 119, 240, 241, 242, 243, 244, 245, 246, 247, 496, 497, 498, 499, 500, 501, 502, 503, 1008, 1009, 1010, 1011, 1012, 1013, 1014, 1015, 2032

Offset: 1

Author

Darío Clavijo, Jan 19 2025

Keywords

• nonn
• base

Comments

For n <= 3 leading zeros are omitted.

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

a(2^k) is a divisor of a(2^(k+1)).

Examples

			For n = 42 a(42) = 111110010_2 = 498.
m = 2^(floor(log_2(floor(log_2(n))+1))+1) = 8 and
q = floor(n / m) = 5 and
r = n mod m = 2 and
u = (2^q-1) left shifted by (2^floor(log_2(m)) + 1) = 111110000_2 = 496 and
u + r = 111110010_2 = 498.
		

Links

• Paolo Xausa, Table of n, a(n) for n = 1..10000
• Wikipedia, Golomb coding

Crossrefs

Cf. A000079, A000225, A070939.

Programs

Mathematica

A380294[n_] := (2^Quotient[n, #] - 1)*2^BitLength[#] + Mod[n, #] & [2^Nest[BitLength, n, 2]];
Array[A380294, 100] (* Paolo Xausa, Feb 03 2025 *)

Python

def a(n):
    if n <= 3: return n
    if n & 1: return a(n-1)+1
    m = 1 << (n.bit_length()).bit_length()
    q, r = divmod(n, m)
    u = ((1 << q) - 1) << m.bit_length()
    return u + r
print([a(n) for n in range(1,57)])

Formula

a(n) = (2^q - 1) * 2^A070939(m) + r, where m = 2^A070939(A070939(n)), q = floor(n/m) and r = n mod m.

a(n) = a(n-1)+1 for n odd > 1.

a(n) = n if n <= 3.