|
| |
|
|
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 A337203 A013188
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
|
| |
|
|
