A088512 Number of partitions of n into two parts whose xor-sum is n.

0, 0, 0, 1, 0, 1, 1, 3, 0, 1, 1, 3, 1, 3, 3, 7, 0, 1, 1, 3, 1, 3, 3, 7, 1, 3, 3, 7, 3, 7, 7, 15, 0, 1, 1, 3, 1, 3, 3, 7, 1, 3, 3, 7, 3, 7, 7, 15, 1, 3, 3, 7, 3, 7, 7, 15, 3, 7, 7, 15, 7, 15, 15, 31, 0, 1, 1, 3, 1, 3, 3, 7, 1, 3, 3, 7, 3, 7, 7, 15, 1, 3, 3, 7

Offset: 0

Author

Naohiro Nomoto, Nov 14 2003

Keywords

• easy
• nonn
• base

Examples

			G.f. = x^3 + x^5 + x^6 + 3*x^7 + x^9 + x^10 + 3*x^11 + x^12 + 3*x^13 + 3*x^14 + ...
From _Emmanuele Villa_, Nov 19 2016: (Start)
For n = 47, the highest power of 2 less than n is 32, so a(47) = A001316(47-32) - 1 = A001316(15) - 1 = 16 - 1 = 15.
For n = 63, the highest power of 2 less than n is 32, so a(63) = A001316(63-32) - 1 = A001316(31) - 1 = 32 - 1 = 31. (End)
		

Crossrefs

Cf. A050315.

Programs

Mathematica

Table[2^DigitCount[# - 2^(Floor@ Log2@ # - Boole@ IntegerQ@ Log2@ #) - 1 + Boole[# == 1]/2, 2, 1] - 1 &[n + 1], {n, 0, 72}] (* Michael De Vlieger, Nov 18 2016 *)
a[ n_] := Which[ n < 3, 0, EvenQ[n], a @ Quotient[n, 2], True, a[ Quotient[n, 2]] 2 + 1]; (* Michael Somos, Dec 04 2016 *)

PARI

a(n) = sum(m=1, n\2, bitxor(m,n-m)==n); \\ Michel Marcus, Dec 03 2016

PARI

{a(n) = if( n<3, 0, n%2, a(n\2)*2 + 1, a(n\2))}; /* Michael Somos, Dec 04 2016 */

Formula

a(0) = 0, a(n) = A001316(n-m)-1, where m is the highest power of 2 less than n. - Emmanuele Villa, Nov 19 2016

a(2*n) = a(n), a(2*n + 1) = 2*a(n) + 1. - Michael Somos, Dec 04 2016