|
%I #80 Mar 30 2021 14:57:32
%S 0,0,0,1,0,0,1,3,0,0,0,1,2,1,3,7,0,0,0,1,0,0,1,3,4,2,1,3,6,3,7,15,0,0,
%T 0,1,0,0,1,3,0,0,0,1,2,1,3,7,8,4,2,5,2,1,3,7,12,6,3,7,14,7,15,31,0,0,
%U 0,1,0,0,1,3,0,0,0,1,2,1,3,7,0,0,0,1,0,0,1,3,4,2,1,3,6,3,7,15,16
%N In binary expansion of n, delete one symbol from each run. Set a(n)=0 if the result is the empty string.
%C If the binary expansion of n is 1^b 0^c 1^d 0^e ..., then a(n) is the number whose binary expansion is 1^(b-1) 0^(c-1) 1^(d-1) 0^(e-1) .... Leading 0's are omitted, and if the result is the empty string, here we set a(n) = 0. See A319419 for a version which represents the empty string by -1.
%C Lenormand refers to this operation as planing ("raboter") the runs (or blocks) of the binary expansion.
%C A175046 expands the runs in a similar way, and a(A175046(n)) = A001477(n). - _Andrew Weimholt_, Sep 08 2018. In other words, this is a left inverse to A175046: A318921 o A175046 = A001477 = id on [0..oo). - _M. F. Hasler_, Sep 10 2018
%C Conjecture: For n in the range 2^k, ..., 2^(k+1)-1, the total value of a(n) appears to be 2*3^(k-1) - 2^(k-1) (see A027649), and so the average value of a(n) appears to be (3/2)^(k-1) - 1/2. - _N. J. A. Sloane_, Sep 25 2018
%C The above conjecture was proved by _Doron Zeilberger_ on Nov 16 2018 (see link) and independently by _Chai Wah Wu_ on Nov 18 2018 (see below). - _N. J. A. Sloane_, Nov 20 2018
%C From _Chai Wah Wu_, Nov 18 2018: (Start)
%C Conjecture is correct for k > 0. Proof: looking at the least significant 2 bits of n, it is easy to see that a(4n) = 2a(2n), a(4n+1) = a(2n), a(4n+2) = a(2n+1) and a(4n+3) = 2a(2n+1)+1. Define 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) = 0 and f(1) = a(2)+a(3) = 1. By summing over the recurrence relations for a(n), 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} (3a(2i) + 3a(2i+1) + 1) = 3*f(k+1) + 2^k. Solving this first order recurrence relation with the initial condition f(1) = 1 shows that f(k) = 2*3^(k-1)-2^(k-1) for k > 0.
%C (End)
%H N. J. A. Sloane, <a href="/A318921/b318921.txt">Table of n, a(n) for n = 0..16384</a>
%H Yonah Biers-Ariel, <a href="https://arxiv.org/abs/1902.06354">A Generalization of the 'Raboter' Operation</a>, arXiv:1902.06354 [math.CO], 2019.
%H Claude Lenormand, <a href="/A318921/a318921.pdf">Deux transformations sur les mots</a>, Preprint, 5 pages, Nov 17 2003. Apparently unpublished. This is a scanned copy of the version that the author sent to me in 2003.
%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.
%H Doron Zeilberger, <a href="http://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/rabot.html">Proof of a Conjecture of Neil Sloane Concerning Claude Lenormand's ``Raboter" Operation (OEIS sequence A318921)</a>, Nov 16 2018; <a href="/A318921/a318921_1.pdf">Local copy, pdf file only, no active links</a>
%F a(4n) = 2a(2n), a(4n+1) = a(2n), a(4n+2) = a(2n+1) and a(4n+3) = 2a(2n+1)+1. - _Chai Wah Wu_, Nov 18 2018
%e n / "planed" string / a(n)
%e 0 e 0 (e = empty string)
%e 1 e 0
%e 10 e 0
%e 11 1 1
%e 100 0 0
%e 101 e 0
%e 110 1 1
%e 111 11 3
%e 1000 00 0
%e 1001 0 0
%e 1010 e 0
%e 1011 1 1
%e 1100 10 2
%e 1101 1 1
%e 1110 11 3
%e 1111 111 7
%e 10000 000 0
%e ...
%p r:=proc(n) local t1,t2,L1,len,i,j,k,b1;
%p if n <= 2 then return(0); fi;
%p b1:=[]; t1:=convert(n,base,2); L1:=nops(t1); p:=1; len:=1;
%p for i from 2 to L1 do
%p t2:=t1[L1+1-i];
%p if (t2=p) and (i<L1) then len:=len+1;
%p else # run ended
%p if (i = L1) and (t2=p) then len:=len+1; fi;
%p if len>1 then for j from 1 to len-1 do b1:=[op(b1),p]; od: fi;
%p p:=t2; len:=1;
%p fi; od;
%p if nops(b1)=0 then return(0);
%p else k:=b1[1];
%p for i from 2 to nops(b1) do k:=2*k+b1[i]; od;
%p return(k);
%p fi;
%p end;
%p [seq(r(n),n=0..120)];
%t a[n_] := FromDigits[Flatten[Rest /@ Split[IntegerDigits[n, 2]]], 2];
%t Table[a[n], {n, 0, 100}] (* _Jean-François Alcover_, Sep 10 2018 *)
%o (PARI) a(n) = if (n==0, 0, n%2==0, my (z=valuation(n,2)); a(n/2^z) * 2^(z-1), my (o=valuation(n+1,2)); (a(n\2^o)+1) * 2^(o-1)-1) \\ _Rémy Sigrist_, Sep 09 2018
%o (PARI) a(n)={forstep(i=#n=binary(n+!n),2,-1,n[i-1]!=n[i] && n=n[^i]); fromdigits(n[^1],2)} \\ For illustration purpose. - _M. F. Hasler_, Sep 10 2018
%o (PARI) A318921(n)=if(n<3, 0, bittest(n, 0), (A318921(n>>n=valuation(n+1, 2))+1)<<(n-1)-1, A318921(n>>n=valuation(n, 2))<<(n-1)) \\ _M. F. Hasler_, Sep 11 2018
%Y Cf. A027649 (average value), A175046, A319419 (a version where a(n)=-1 if the result is the empty string).
%Y See also A319416.
%K nonn,base,hear
%O 0,8
%A _N. J. A. Sloane_, Sep 08 2018
|
