A352782 The binary expansion of a(n) encodes the runs of consecutive 1's in the binary expansion of n (see Comments section for precise definition).

0, 1, 2, 4, 8, 3, 16, 32, 64, 5, 6, 12, 128, 9, 256, 512, 1024, 17, 10, 20, 24, 7, 48, 96, 2048, 33, 18, 36, 4096, 65, 8192, 16384, 32768, 129, 34, 68, 40, 11, 80, 160, 192, 13, 14, 28, 384, 25, 768, 1536, 65536, 257, 66, 132, 72, 19, 144, 288, 131072, 513

Offset

0,3

Comments

For any nonnegative integer n:

- the binary expansion of n can be uniquely expressed as the concatenation of k = A069010(n) positive terms of A023758 separated by 0's:

n = A023758(m_k+1) | 0 | A023758(m_{k-1}+1) | 0 | ... | 0 | A023758(m_1+1)

(where | denotes binary concatenation)

- a(n) = ( Sum_{i = 1..k} 2^Sum_{j = 1..i} m_j ) / 2.

This sequence is a permutation of the nonnegative integers, with inverse A352783.

Links

Rémy Sigrist, Table of n, a(n) for n = 0..8192

Rémy Sigrist, Colored logarithmic scatterplot of the first 2^20 terms (where the color is function of A069010(n))

Index entries for sequences related to binary expansion of n

Index entries for sequences that are permutations of the natural numbers

Formula

a(4*n+1) = 2*a(n)+1.

A000120(a(n)) = A069010(n).

a(A023758(k+1)) = 2^k for any k >= 0.

a(2^k) = A006125(k+1) for any k >= 0.

a(2^k-1) = A036442(k+1) for any k >= 0.

a(n) = n iff n = 0 or n belongs to A131865 or n/2 belongs to A131865.

Example

For n = 89:
- the binary expansion of 89 is "1011001",
- "1011001" = "1" | 0 | "110" | 0 | "1"
            = A023758(1+1) | 0 | A023758(5+1) | 0 | A023758(1+1)
- so 2*a(89) = 2^(1+5+1) + 2^(5+1) + 2^1 = 194,
- and a(89) = 97.

Prog

(PARI) a(n) = { my (v=0, s=-1, z, o, i); while (n, n\=2^z=valuation(n, 2); n\=2^o=valuation(n+1, 2); n\=2; i=(o+z)*(o+z-1)/2 + o; v+=2^s+=i); v }

Crossrefs

Cf. A000120, A006125, A023758, A036442, A069010, A131865, A352783 (inverse).

Sequence in context: A317503 A243505 A243065 * A289271 A354169 A341811

Adjacent sequences: A352779 A352780 A352781 * A352783 A352784 A352785

Keyword

nonn,base

Author

Rémy Sigrist, Apr 02 2022

Status

approved