A048735 a(n) = (n AND floor(n/2)), where AND is bitwise and-operator (A004198).

0, 0, 0, 1, 0, 0, 2, 3, 0, 0, 0, 1, 4, 4, 6, 7, 0, 0, 0, 1, 0, 0, 2, 3, 8, 8, 8, 9, 12, 12, 14, 15, 0, 0, 0, 1, 0, 0, 2, 3, 0, 0, 0, 1, 4, 4, 6, 7, 16, 16, 16, 17, 16, 16, 18, 19, 24, 24, 24, 25, 28, 28, 30, 31, 0, 0, 0, 1, 0, 0, 2, 3, 0, 0, 0, 1, 4, 4, 6, 7, 0

Offset: 0

Author

Antti Karttunen, Apr 26 1999

Keywords

• nonn
• base

Comments

To prove that (n AND floor(n/2)) = (3n-(n XOR 2n))/4 (= A048728(n)/4), we first multiply both sides by 4, to get 2*(n AND 2n) = (3n - (n XOR 2n)) and then rearrange terms: 3n = (n XOR 2n) + 2*(n AND 2n), which fits perfectly to the identity A+B = (A XOR B) + 2*(A AND B) (given by Schroeppel in HAKMEM link).

The number of 1's through 4*2^n appears to yield A000045(n+1). - Ben Burns, Jun 12 2017

Links

• T. D. Noe, Table of n, a(n) for n = 0..1023
• Beeler, M., Gosper, R. W. and Schroeppel, R., HAKMEM, ITEM 23 (Schroeppel)

Crossrefs

Cf. A003714 (positions of zeros), A003188, A050600.

Programs

Maple

seq(Bits:-And(n,floor(n/2)), n=0..200); # Robert Israel, Feb 29 2016

Mathematica

Table[BitAnd[n, Floor[n/2]], {n, 0, 127}] (* T. D. Noe, Aug 13 2012 *)

PARI

a(n) = bitand(n, n\2); \\ Michel Marcus, Feb 29 2016

Python

def a(n): return n&int(n/2) # Indranil Ghosh, Jun 13 2017

Formula

a(n) = A048728(n)/4. (This was the original definition. AND-formula found Jan 01 2007).

Extensions

New formula and more terms added by Antti Karttunen, Jan 01 2007