Project Euler 242

プロジェクトオイラー
http://projecteuler.net/

Q242.
集合{1,2,...,n}の部分集合を考える。要素数kの部分集合で総和が奇数のものの個数をf(n,k)とする。
n,k,f(n,k)がともに奇数のとき、odd-tripletと呼ぶ。n ≤ 1012でodd-tripletはいくつあるか。

ほぼ、数学だけで解ける。
以下、剰余は2で考える。
nkは奇数以外興味がないから、

g(n,k) ≡ f(2n+1,2k+1)

とする。

g(n,n) = (2n+1)(n+1)

そうでないとき、例えば7までの集合から3個を選んで和が奇数のとき、6までから3個を選んで和が奇数の場合と、7を選んで6までから2個で和が偶数になるものを選ぶ場合があるから、

g(n,n) = f(2n,2k+1) + (2nC2k - f(2n,2k))

元の集合の要素数が偶数の場合は数えやすくて、がんばって計算すると、結局、

g(n,n) = (2n+1C2k+1 + (-1)knCk) / 2

となる。nCkでくくると、nkが共に偶数のとき以外は、2の剰余が0になり、共に偶数のときは、

g(n,n) ≡ nCk

となる。結局これを計算すればよい。
n!の2の因子の数と、k!のそれと(n-k)!のそれの和が等しければ奇数、そうでなければ偶数となる。2の因子が等しくなるは、kn-kを足して2進で繰り上がりがない、と同値。
例えば、n = 6なら、2進で最後の桁をネグって、11。繰り上がらない組合せは、n = kの場合もあわせて、各桁どちらが1を取るかで、22通り。10などもあわせると、結局、32となる。



def max_bit(n):
bit = 0
while n >> bit:
bit += 1
return bit - 1

def count_odd_triplets4(N):
n = (N - 1) / 4
s = 0
m = 0
for bit in range(max_bit(n), -1, -1):
if (n >> bit) & 1:
s += 2 ** m * 3 ** bit
m += 1
s += 2 ** m
return s

N = 10 ** 12
print count_odd_triplets4(N)