题目242：奇数三元组

欧拉计划

Odd Triplets

Given the set {1,2,...,n}, we define f(n,k) as the number of its k-element subsets with an odd sum of elements. For example, f(5,3) = 4, since the set {1,2,3,4,5} has four 3-element subsets having an odd sum of elements, i.e.: {1,2,4}, {1,3,5}, {2,3,4} and {2,4,5}.

When all three values n, k and f(n,k) are odd, we say that they make
an odd-triplet [n,k,f(n,k)].

There are exactly five odd-triplets with n ≤ 10, namely:
[1,1,f(1,1) = 1], [5,1,f(5,1) = 3], [5,5,f(5,5) = 1], [9,1,f(9,1) = 5] and [9,9,f(9,9) = 1].

How many odd-triplets are there with n ≤ 10¹² ?

题目：

给定集合 {1,2,...,n}，定义 f(n,k) 为其元素和为奇数的 k 元子集的数目。例如，f(5,3)  = 4，因为集合 {1,2,3,4,5} 有 4 个元素和为奇数的 3 元子集：{1,2,4}, {1,3,5}, {2,3,4} 和 {2,4,5}。

当 n, k 和 f(n,k) 的值均为奇数时，我们称它们构成奇数三元组 [n,k,f(n,k)]。

当 n ≤ 10 时有 5 个奇数三元组，也就是：
[1,1,f(1,1) = 1]，[5,1,f(5,1) = 3，[5,5,f(5,5) = 1]，[9,1,f(9,1) = 5] 和 [9,9,f(9,9) = 1]。

当 n ≤ 10¹² 时有多少个奇数三元组？