|
|
A318921
|
|
In binary expansion of n, delete one symbol from each run. Set a(n)=0 if the result is the empty string.
|
|
53
|
|
|
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.
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
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
|
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)
|
|
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];
|
|
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
|
|
CROSSREFS
|
Cf. A027649 (average value), A175046, A319419 (a version where a(n)=-1 if the result is the empty string).
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|