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

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

Links

Paolo Xausa, Table of n, a(n) for n = 1..10000

Wikipedia, Golomb coding

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.

Example

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.

Mathematica

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

Prog

(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)])

Crossrefs

Cf. A000079, A000225, A070939.

Sequence in context: A353652 A080745 A283776 * A047476 A347397 A037462

Adjacent sequences: A380291 A380292 A380293 * A380295 A380296 A380297

Keyword

nonn,base

Author

Darío Clavijo, Jan 19 2025

Status

approved