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,8

Links

Table of n, a(n) for n=0..83.

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

Example

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)

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 *)

Prog

(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 */

Crossrefs

Cf. A050315.

Sequence in context: A174433 A174624 A029358 * A094921 A246522 A140166

Adjacent sequences: A088509 A088510 A088511 * A088513 A088514 A088515

Keyword

easy,nonn,base

Author

Naohiro Nomoto, Nov 14 2003

Status

approved