|
|
A063694
|
|
Remove odd-positioned bits from the binary expansion of n.
|
|
11
|
|
|
0, 1, 0, 1, 4, 5, 4, 5, 0, 1, 0, 1, 4, 5, 4, 5, 16, 17, 16, 17, 20, 21, 20, 21, 16, 17, 16, 17, 20, 21, 20, 21, 0, 1, 0, 1, 4, 5, 4, 5, 0, 1, 0, 1, 4, 5, 4, 5, 16, 17, 16, 17, 20, 21, 20, 21, 16, 17, 16, 17, 20, 21, 20, 21, 64, 65, 64, 65, 68, 69, 68, 69, 64, 65, 64, 65, 68, 69, 68
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,5
|
|
COMMENTS
|
a(n) is the formal derivative of x*n (evaluated at x=2 after being lifted to Z[x]) where n is interpreted as a polynomial in GF(2)[x] via its binary expansion. - Keith J. Bauer, Mar 17 2024
|
|
LINKS
|
|
|
FORMULA
|
a(n) = Sum_{k>=0} (-1)^k*2^k*floor(n/2^k).
G.f.: 1/(1-x) * Sum_{k>=0} (-2)^k*x^2^k/(1-x^2^k). - Ralf Stephan, May 05 2003
|
|
EXAMPLE
|
a(25) = 17 because 25 = 11001 in binary and when we AND this with 10101 we are left with 10001 = 17.
|
|
MAPLE
|
every_other_pos := proc(nn, x, w) local n, i, s; n := nn; i := 0; s := 0; while(n > 0) do if((i mod 2) = w) then s := s + ((x^i)*(n mod x)); fi; n := floor(n/x); i := i+1; od; RETURN(s); end: [seq(every_other_pos(j, 2, 0), j=0..120)];
|
|
MATHEMATICA
|
a[n_] := BitAnd[n, Sum[2^k, {k, 0, Log[2, n] // Floor, 2}]]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Feb 28 2016 *)
|
|
PROG
|
(PARI) a(n)=sum(k=0, n, (-1)^k*2^k*floor(n/2^k)) /* since n> ceil(log(n)/log(2)) */
(PARI) a(n)=if(n<0, 0, sum(k=0, n, (-1)^k*2^k*floor(n/2^k))) /* since n> ceil(log(n)/log(2)) */
(Haskell)
a063694 0 = 0
a063694 n = 4 * a063694 n' + mod q 2
where (n', q) = divMod n 4
(Magma)
if n le 1 then return n;
else return 4*A063694(Floor(n/4)) + ((n mod 4) mod 2);
end function;
(SageMath)
if (n<2): return n
else: return 4*A063694(floor(n/4)) + ((n%4)%2)
(Python)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,base,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|