A318921 - OEIS

%I #83 Dec 14 2024 07:18:23

%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..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..2^(k+1)-1} (f(4i) + f(4i+1) + f(4i+2) + f(4i+3)) = Sum_{i=2^k..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,changed

%O 0,8

%A _N. J. A. Sloane_, Sep 08 2018