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

3, 13, 7, 25, 55, 29, 15, 49, 103, 221, 111, 57, 119, 61, 31, 97, 199, 413, 207, 441, 887, 445, 223, 113, 231, 477, 239, 121, 247, 125, 63, 193, 391, 797, 399, 825, 1655, 829, 415, 881, 1767, 3549, 1775, 889, 1783, 893, 447, 225, 455, 925, 463, 953, 1911, 957

Offset: 1

Author

Chai Wah Wu, Oct 05 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) = 3 and f(1) = a(2) + a(3) = 20.

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

Proof: the equation for f is true for k = 0. Looking at the last 2 bits of n, it is easy to see that a(4n) = 2*a(2n)-1, a(4n+1) = 4*a(2n)+3, a(4n+2) = 4*a(2n+1)+1 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) = 20 shows that f(k) = 21*6^(k-1) - 2^(k-1) for k > 0.

(End)

Examples

			6 in binary is 110. Modify each run by appending a 1 to get 11101, which is 29 in decimal. So a(6) = 29.
		

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

Programs

Mathematica

Array[FromDigits[Flatten@ Map[Append[#, 1] &, Split@ IntegerDigits[#, 2]], 2] &, 54] (* Michael De Vlieger, Nov 23 2018 *)

Python

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

Formula

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