A063694 Remove odd-positioned bits from the binary expansion of n.

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

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

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000

Ralf Stephan, Some divide-and-conquer sequences ...

Ralf Stephan, Table of generating functions

Formula

a(n) = Sum_{k>=0} (-1)^k*2^k*floor(n/2^k).

a(n) + A063695(n) = n.

a(n) = n - 2*a(floor(n/2)). - Vladeta Jovovic, Feb 23 2003

G.f.: 1/(1-x) * Sum_{k>=0} (-2)^k*x^2^k/(1-x^2^k). - Ralf Stephan, May 05 2003

a(n) = 4*a(floor(n/4)) + (n mod 4) mod 2. - Reinhard Zumkeller, Sep 26 2015

a(n) = Sum_{k>=0} A030308(n,k)*A199572(k). - Philippe Deléham, Jan 12 2023

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
-- Reinhard Zumkeller, Sep 26 2015
(Magma)
function A063694(n)
  if n le 1 then return n;
  else return 4*A063694(Floor(n/4)) + ((n mod 4) mod 2);
  end if; return A063694;
end function;
[A063694(n): n in [0..120]]; // G. C. Greubel, Dec 05 2022
(SageMath)
def A063694(n):
    if (n<2): return n
    else: return 4*A063694(floor(n/4)) + ((n%4)%2)
[A063694(n) for n in range(121)] # G. C. Greubel, Dec 05 2022
(Python)
def A063694(n): return n&((1<<(m:=n.bit_length())+(m&1))-1)//3 # Chai Wah Wu, Jan 30 2023

Crossrefs

Cf. A004514, A063695 (remove even-positioned bits), A088442.

Sequence in context: A125583 A196619 A343954 * A242624 A068901 A010710

Adjacent sequences: A063691 A063692 A063693 * A063695 A063696 A063697

Keyword

nonn,base,easy

Author

Antti Karttunen, Aug 03 2001

Status

approved