|
%I #80 Mar 09 2024 11:17:08
%S 3,12,7,24,51,28,15,48,99,204,103,56,115,60,31,96,195,396,199,408,819,
%T 412,207,112,227,460,231,120,243,124,63,192,387,780,391,792,1587,796,
%U 399,816,1635,3276,1639,824,1651,828,415,224,451,908,455,920,1843,924
%N 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.
%C A318921 expands the runs in a similar way, and A318921(a(n)) = A001477(n). - _Andrew Weimholt_, Sep 08 2018
%C From _Chai Wah Wu_, Nov 18 2018: (Start)
%C 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.
%C Then f(k) = 20*6^(k-1) - 2^(k-1) for k > 0.
%C 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.
%C (End)
%H Reinhard Zumkeller, <a href="/A175046/b175046.txt">Table of n, a(n) for n = 1..10000</a>
%H N. J. A. Sloane, Coordination Sequences, Planing Numbers, and Other Recent Sequences (II), Experimental Mathematics Seminar, Rutgers University, Jan 31 2019, <a href="https://vimeo.com/314786942">Part I</a>, <a href="https://vimeo.com/314790822">Part 2</a>, <a href="https://oeis.org/A320487/a320487.pdf">Slides.</a> (Mentions this sequence)
%H Chai Wah Wu, <a href="https://arxiv.org/abs/1810.02293">Record values in appending and prepending bitstrings to runs of binary digits</a>, arXiv:1810.02293 [math.NT], 2018.
%F 2n+1 <= a(n) < 2*(n+1/n)^2; a(n) mod 4 = 3*(n mod 2). - _M. F. Hasler_, Sep 08 2018
%F 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
%F From _M. F. Hasler_, Sep 12 2018: (Start)
%F 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).
%F 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.
%F 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.
%F 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.
%F It remains to consider the case L(a(n)) = 2 L(n) - 1. There are two possibilities:
%F 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.
%F 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.
%F 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)
%F From _M. F. Hasler_, Sep 10 2018: (Start)
%F Right inverse of A318921: A318921 o A175046 = id (= A001477).
%F 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)
%F From _David A. Corneth_, Sep 20 2018: (Start)
%F a(4*k) = 2*a(2*k).
%F a(4*k+1) = 4*a(2*k) + 3.
%F a(4*k+2) = 4*a(2*k+1).
%F a(4*k+3) = 2*a(2*k+1) + 1. (End)
%e 6 in binary is 110. Increase each run by one digit to get 11100, which is 28 in decimal. So a(6) = 28.
%t a[n_] := (Append[#, #[[1]]]& /@ Split[IntegerDigits[n, 2]]) // Flatten // FromDigits[#, 2]&;
%t Array[a, 60] (* _Jean-François Alcover_, Nov 12 2018 *)
%o (Haskell)
%o import Data.List (group)
%o a175046 = foldr (\b v -> 2 * v + b) 0 .
%o concatMap (\bs@(b:_) -> b : bs) . group . a030308_row
%o -- _Reinhard Zumkeller_, Jul 05 2013
%o (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
%o (Python)
%o from re import split
%o def A175046(n):
%o 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
%o (Python)
%o def a(n):
%o b = bin(n)[2:]
%o return int(b.replace("01", "001").replace("10", "110") + b[-1], 2)
%o print([a(n) for n in range(1, 55)]) # _Michael S. Branicky_, Dec 07 2021
%Y Cf. A175047, A175048, A324127 (partial sums).
%Y Cf. also A030308, A007088, A182512, A318921.
%Y For records see A319422, A319423, A319424.
%K base,nonn
%O 1,1
%A _Leroy Quet_, Dec 02 2009
%E Extended by _Ray Chandler_, Dec 18 2009
| 