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

3, 14, 7, 28, 59, 30, 15, 56, 115, 238, 119, 60, 123, 62, 31, 112, 227, 462, 231, 476, 955, 478, 239, 120, 243, 494, 247, 124, 251, 126, 63, 224, 451, 910, 455, 924, 1851, 926, 463, 952, 1907, 3822, 1911, 956, 1915, 958, 479, 240, 483, 974, 487, 988, 1979, 990

Offset: 1

Author

Chai Wah Wu, Oct 08 2018

Keywords

• nonn
• base

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) = 3 and f(1) = a(2) + a(3) = 21, and f(2) = a(4)+a(5)+a(6)+a(7) = 132.

Then f(k) = 135*6^(k-2) - 3*2^(k-2) for k >= 0.

Proof: the formula is true for k = 0. 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)+3, 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) + 6) = 6*f(k+1) + 3*2^(k+1). Solving this first-order recurrence relation with the initial condition f(1) = 21 shows that f(k) = 135*6^(k-2) - 3*2^(k-2) for k > 0.

(End)

Examples

			6 in binary is 110. Modify each run by prepending a 1 to get 11110, which is 30 in decimal. So a(6) = 30.
		

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

Programs

Mathematica

Table[FromDigits[Flatten[Join[{1},#]&/@Split[IntegerDigits[n,2]]],2],{n,60}] (* Harvey P. Dale, Apr 26 2019 *)

Python

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

Formula

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