A377475 a(n) is the Even-Rodeh encoding of n as an integer.

0, 1, 2, 3, 8, 10, 12, 14, 144, 146, 148, 150, 152, 154, 156, 158, 352, 354, 356, 358, 360, 362, 364, 366, 368, 370, 372, 374, 376, 378, 380, 382, 832, 834, 836, 838, 840, 842, 844, 846, 848, 850, 852, 854, 856, 858, 860, 862, 864, 866, 868, 870, 872, 874, 876, 878, 880, 882, 884, 886, 888, 890, 892

Offset

0,3

Comments

Runtime complexity is O(log log n).

For n < 4 leading zeros are omitted.

For n >=4 all terms are even.

Links

Table of n, a(n) for n=0..62.

Wikipedia, Even-Rodeh coding.

Formula

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

Example

For n = 2761, a(2761) = 628114 because in binary
  n    =          101011001001
  a(n) = 100 1100 101011001001 0
         \-/ \--/ \----------/
          4   12        n
n has a 0 appended, then binary 12 prepended since the bit length of n is 12, and then binary 4 prepended since the bit length of 12 is 4, and stop there since 4 is 3 bits long.
Decoding is the reverse: 3 most significant bits are value 4, next 4 bits are value 12, next 12 bits are n, and the bit after is 0 so stop.

Prog

(Python)
def a(n):
    if n <= 3: return n
    enc, s, v = 0, 0, n
    while v > 3:
        enc |= v << s
        v = v.bit_length()
        s += v
    return enc << 1
print([a(n) for n in range(63)])
(PARI) a(n) = if (n <= 3, return(n), enc=0; s=0; v=n; while(v >3, enc=bitor(enc, (v << s)); v = #binary(v); s += v; )); return(enc << 1)

Crossrefs

Cf. A070939.

Sequence in context: A097053 A190668 A387151 * A250037 A360940 A132327

Adjacent sequences: A377472 A377473 A377474 * A377476 A377477 A377478

Keyword

nonn,base,easy

Author

Darío Clavijo, Jan 08 2025

Status

approved