login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A318921 In binary expansion of n, delete one symbol from each run. Set a(n)=0 if the result is the empty string. 50
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, 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, 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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,8

COMMENTS

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.

Lenormand refers to this operation as planing ("raboter") the runs (or blocks) of the binary expansion.

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

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

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

From Chai Wah Wu, Nov 18 2018: (Start)

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.

(End)

LINKS

N. J. A. Sloane, Table of n, a(n) for n = 0..16384

Yonah Biers-Ariel, A Generalization of the 'Raboter' Operation, arXiv:1902.06354 [math.CO], 2019.

Claude Lenormand, Deux transformations sur les mots, Preprint, 5 pages, Nov 17 2003. Apparently unpublished. This is a scanned copy of the version that the author sent to me in 2003.

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.

Doron Zeilberger, Proof of a Conjecture of Neil Sloane Concerning Claude Lenormand's ``Raboter" Operation (OEIS sequence A318921), Nov 16 2018

FORMULA

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

EXAMPLE

      n / "planed" string / a(n)

      0   e 0 (e = empty string)

      1   e 0

     10   e 0

     11   1 1

    100   0 0

    101   e 0

    110   1 1

    111  11 3

   1000  00 0

   1001   0 0

   1010   e 0

   1011   1 1

   1100  10 2

   1101   1 1

   1110  11 3

   1111 111 7

  10000 000 0

  ...

MAPLE

r:=proc(n) local t1, t2, L1, len, i, j, k, b1;

if n <= 2 then return(0); fi;

b1:=[]; t1:=convert(n, base, 2); L1:=nops(t1); p:=1; len:=1;

for i from 2 to L1 do

t2:=t1[L1+1-i];

if (t2=p) and (i<L1) then len:=len+1;

else # run ended

   if (i = L1) and (t2=p) then len:=len+1; fi;

   if len>1 then for j from 1 to len-1 do b1:=[op(b1), p]; od: fi;

   p:=t2; len:=1;

fi;               od;

if nops(b1)=0 then return(0);

else k:=b1[1];

for i from 2 to nops(b1) do k:=2*k+b1[i]; od;

return(k);

fi;

end;

[seq(r(n), n=0..120)];

MATHEMATICA

a[n_] := FromDigits[Flatten[Rest /@ Split[IntegerDigits[n, 2]]], 2];

Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Sep 10 2018 *)

PROG

(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

(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

(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

CROSSREFS

Cf. A027649 (average value), A175046, A319419 (a version where a(n)=-1 if the result is the empty string).

See also A319416.

Sequence in context: A089313 A052998 A290174 * A114516 A218788 A328969

Adjacent sequences:  A318918 A318919 A318920 * A318922 A318923 A318924

KEYWORD

nonn,base,hear

AUTHOR

N. J. A. Sloane, Sep 08 2018

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 28 11:24 EDT 2020. Contains 337393 sequences. (Running on oeis4.)