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

Author

Rémy Sigrist, Apr 02 2022

Keywords

• nonn
• base

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.

Examples

			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.
		

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

Crossrefs

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

Programs

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 }

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.