|
| |
|
|
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
|
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) = 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..2^(k+1)-1} (f(4i) + f(4i+1) + f(4i+2) + f(4i+3)) = Sum_{i=2^k..2^(k+1)-1} (6*a(2i) + 6*a(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
|
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)
|
|
|
FORMULA
|
2n+1 <= a(n) < 2*(n+1/n)^2; a(n) mod 4 = 3*(n mod 2). - 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
Proof of N. J. A. Sloane's formula: For given (binary) length L(n) = floor(log_2(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 log_2(a(n)) < floor(log_2(a(n))+1) = L(a(n)) <= 2*L(n) - 2 = 2*floor(log_2(n)+1)-2 = 2*floor(log_2(n)) <= 2*log_2(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 a(n)/n^2 <= 9/5 + 12/(5*n) always holds, with equality iff n is in A020988; and a(n)/n^2 < 13/8 if n is not in A020988 or A002450. (End)
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]&;
|
|
|
PROG
|
(Haskell)
import Data.List (group)
a175046 = foldr (\b v -> 2 * v + b) 0 .
concatMap (\bs@(b:_) -> b : bs) . group . a030308_row
(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
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
(Python)
def a(n):
b = bin(n)[2:]
return int(b.replace("01", "001").replace("10", "110") + b[-1], 2)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
base,nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
