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

1, 6, 3, 12, 25, 14, 7, 24, 49, 102, 51, 28, 57, 30, 15, 48, 97, 198, 99, 204, 409, 206, 103, 56, 113, 230, 115, 60, 121, 62, 31, 96, 193, 390, 195, 396, 793, 398, 199, 408, 817, 1638, 819, 412, 825, 414, 207, 112, 225, 454, 227, 460, 921, 462, 231, 120, 241

Offset: 1

Author

Chai Wah Wu, Oct 04 2018

Keywords

• nonn

Comments

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

From Chai Wah Wu, Nov 25 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) = 1 and f(1) = a(2) + a(3) = 9.

Then f(k) = 10*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) = 2*a(2n), a(4n+1) = 4*a(2n)+1, a(4n+2) = 4*a(2n+1)+2 and a(4n+3) = 2*a(2n+1)+1. 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) = 9 shows that f(k) = 10*6^(k-1) - 2^(k-1) for k > 0.

(End)

Examples

			6 in binary is 110. Modify each run by prepending the opposite digit to get 01110, which is 14 in decimal. So a(6) = 14.
		

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, A320037.

Programs

Mathematica

a[n_] := Split[IntegerDigits[n, 2]] /. {a0:{(0)...} :> Prepend[a0, 1], a1:{(1)...} :> Prepend[a1, 0]} // Flatten // FromDigits[#, 2]&;
Array[a, 60] (* Jean-François Alcover, Dec 02 2018 *)

Python

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

Formula

a(n) = floor(A175046(n)/2).

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