A320037 Write n in binary, then modify each run of 0's by appending one 1, and modify each run of 1's by appending one 0. a(n) is the decimal equivalent of the result.

2, 9, 6, 17, 38, 25, 14, 33, 70, 153, 78, 49, 102, 57, 30, 65, 134, 281, 142, 305, 614, 313, 158, 97, 198, 409, 206, 113, 230, 121, 62, 129, 262, 537, 270, 561, 1126, 569, 286, 609, 1222, 2457, 1230, 625, 1254, 633, 318, 193, 390, 793, 398, 817, 1638, 825, 414

Offset: 1

Author

Chai Wah Wu, Oct 04 2018

Keywords

• nonn
• base

Comments

A variation of A175046. Indices of record values are given by A319423.

From Chai Wah Wu, Nov 21 2018: (Start)

Let f(k) = Sum_{i=2^k..2^(k+1)-1} a(i), i.e., the sum ranges over all numbers with a (k+1)-bit binary expansion. Thus f(0) = a(1) = 2 and f(1) = a(2) + a(3) = 15.

Then f(k) = 16*6^(k-1) - 2^(k-1) for k > 0.

Proof: looking at the last 2 bits of n, it is easy to see that a(4n) = 2a(2n)-1, a(4n+1) = 4a(2n)+2, a(4n+2) = 4a(2n+1)+1 and a(4n+3) = 2a(2n+1)+2. By summing over the recurrence relations for a(n), we get f(k+2) = Sum_{i=2^k..2^(k+1)-1} (f(4i) + f(4i+1) + f(4i+2) + f(4i+3)) = Sum_{i=2^k..2^(k+1)-1} (6a(2i) + 6a(2i+1) + 4) = 6*f(k+1) + 2^(k+2). Solving this first order recurrence relation with the initial condition f(1) = 15 shows that f(k) = 16*6^(k-1) - 2^(k-1) for k > 0.

(End)

Examples

			6 in binary is 110. Modify each run by appending the opposite digit to get 11001, which is 25 in decimal. So a(6) = 25.
		

Links

• Chai Wah Wu, Table of n, a(n) for n = 1..10000
• Chai Wah Wu, Record values in appending and prepending bitstrings to runs of binary digits, arXiv:1810.02293 [math.NT], 2018.

Crossrefs

Cf. A175046, A319423, A320038.

Programs

Python

from re import split
def A320037(n):
    return int(''.join(d+'0' if '1' in d else d+'1' for d in split('(0+)|(1+)',bin(n)[2:]) if d != '' and d != None),2)

Formula

a(4n) = 2a(2n)-1, a(4n+1) = 4a(2n)+2, a(4n+2) = 4a(2n+1)+1 and a(4n+3) = 2a(2n+1)+2. - Chai Wah Wu, Nov 21 2018