login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A175046 Write n in binary, then increase each run of 0's by one 0, and increase each run of 1's by one 1. a(n) is the decimal equivalent of the result. 29
3, 12, 7, 24, 51, 28, 15, 48, 99, 204, 103, 56, 115, 60, 31, 96, 195, 396, 199, 408, 819, 412, 207, 112, 227, 460, 231, 120, 243, 124, 63, 192, 387, 780, 391, 792, 1587, 796, 399, 816, 1635, 3276, 1639, 824, 1651, 828, 415, 224, 451, 908, 455, 920, 1843, 924 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

A318921 expands the runs in a similar way, and A318921(a(n)) = A001477(n). - Andrew Weimholt, Sep 08 2018

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

Let f(k) = Sum_{i=2^k)}^{i=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) = 19.

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

Proof: by summing over the recurrence relations for a(n) (see formula section), we get f(k+2) = Sum_{i=2^k}^{i=2^(k+1)-1} (f(4i) + f(4i+1) + f(4i+2) + f(4i+3)) =  Sum_{i=2^k}^{i=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) = 19 shows that f(k) = 20*6^(k-1)-2^(k-1) for k > 0.

(End)

LINKS

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

N. J. A. Sloane, Coordination Sequences, Planing Numbers, and Other Recent Sequences (II), Experimental Mathematics Seminar, Rutgers University, Jan 31 2019, Part I, Part 2, Slides. (Mentions this sequence)

Chai Wah Wu, Record values in appending and prepending bitstrings to runs of binary digits, arXiv:1810.02293 [math.NT], 2018.

FORMULA

2n+1 <= a(n) < 2*(n+1/n)^2; a(n) mod 4 = 3*(n mod 2), where 'mod' is the remainder operator. - M. F. Hasler, Sep 08 2018

a(n) <= (9*n^2+12*n)/5, with equality iff n = (2/3)*(4^k-1) = A182512(k) for some k, i.e., n = 10101...10 in binary. - Conjectured by N. J. A. Sloane, Sep 09 2018, proved by M. F. Hasler, Sep 12 2018

From M. F. Hasler, Sep 12 2018: (Start)

Proof of N. J. A. Sloane's formula: For given (binary) length L(n) = [log2(n)+1], the length of a(n) is maximal, L(a(n)) = 2*L(n), if and only if n's bits are alternating, i.e., n in A020988 (if even) or in A002450 (if odd).

For n = A020988(k) (= k times '10' in base 2) = (4^k - 1)*2/3, one has a(n) = A108020(k) (= k times '1100' in base 2) = (16^k - 1)*4/5. This yields a(n)/n = (4^k + 1)*6/5 = (n*9 + 12)/5, i.e., the given upper bound.

For n = A002450(k) = (4^k - 1)/3, one gets a(n) = A182512(k) = (16^k - 1)/5, whence a(n)/n = (4^k + 1)*3/5 = (n*9 + 6)/5, smaller than the bound.

If L(a(n)) < 2 L(n) - 1, then log2(a(n)) < [log2(a(n))+1] = L(a(n)) <= 2*L(n) - 2 = 2*[log2(n)+1]-2 = 2*[log2(n)] <= 2 log2(n), whence a(n) < n^2.

It remains to consider the case L(a(n)) = 2 L(n) - 1. There are two possibilities:

If n = 10...[2], then n >= 2^(L(n)-1) and a(n) = 1100...[2] < 1101[2]*2^(L(a(n))-4) = 13*2^(2 L(n)-5), so a(n)/n^2 < 13*2^(-5+2) = 13/8 = 1.625 < 9/5 = 1.8.

If n = 11...[2], then n >= 3*2^(L(n)-2) and a(n) = 111...[2] < 2^L(a(n)) = 2^(2 L(n)-1), so a(n)/n^2 < 2^(-1+4)/9 = 8/9 < 1 < 9/5.

This shows that always a(n)/n^2 <= 9/5 + 12/5n, with equality iff n is in A020988; and a(n)/n^2 < 13/8 if n is not in A020988 or A002450. (End)

From M. F. Hasler, Sep 10 2018: (Start)

Right inverse of A318921: A318921 o A175046 = id (= A001477).

a(A020988(k)) = A108020(k); a(A002450(k)) = A182512(k); a(A000225(k)) = A000225(k+1) (achieves the lower bound a(n) >= 2n + 1) for all k >= 0. (End)

From David A. Corneth, Sep 20 2018: (Start)

a(4*k)   = 2*a(2*k).

a(4*k+1) = 4*a(2*k) + 3.

a(4*k+2) = 4*a(2*k+1).

a(4*k+3) = 2*a(2*k+1) + 1. (End)

EXAMPLE

6 in binary is 110. Increase each run by one digit to get 11100, which is 28 in decimal. So a(6) = 28.

MATHEMATICA

a[n_] := (Append[#, #[[1]]]& /@ Split[IntegerDigits[n, 2]]) // Flatten // FromDigits[#, 2]&;

Array[a, 60] (* Jean-Fran├žois Alcover, Nov 12 2018 *)

PROG

(Haskell)

import Data.List (group)

a175046 = foldr (\b v -> 2 * v + b) 0 .

          concatMap (\bs@(b:_) -> b : bs) . group . a030308_row

-- Reinhard Zumkeller, Jul 05 2013

(PARI) A175046(n)={for(i=2, #n=binary (n*2+bittest (n, 0)), n[i]!=n[i-1]&&n[i-1]*=[1, 1]); fromdigits(concat(n), 2)} \\ M. F. Hasler, Sep 08 2018

(Python)

from re import split

def A175046(n):

    return int(''.join(d+'1' if '1' in d else d+'0' for d in split('(0+)|(1+)', bin(n)[2:]) if d != '' and d != None), 2) # Chai Wah Wu, Sep 24 2018

CROSSREFS

Cf. A175047, A175048, A324127 (partial sums).

Cf. also A030308, A007088, A182512, A318921.

For records see A319422, A319423, A319424.

Sequence in context: A307027 A304566 A291156 * A093855 A013188 A234947

Adjacent sequences:  A175043 A175044 A175045 * A175047 A175048 A175049

KEYWORD

base,nonn

AUTHOR

Leroy Quet, Dec 02 2009

EXTENSIONS

Extended by Ray Chandler, Dec 18 2009

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 14 12:38 EST 2019. Contains 329114 sequences. (Running on oeis4.)