Project Euler 242: Odd triplets in Pascal's triangle
Problem Description
Given the set {1,2,…,n}, we define f(n,k) as the number of its kelement subsets with an odd sum of elements. For example, f(5,3) = 4, since the set {1,2,3,4,5} has four 3element 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 oddtriplet [n,k,f(n,k)].
There are exactly five oddtriplets 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 oddtriplets are there with n ≤ 10^{12} ?
Analysis
It turns out that the “odd triplet” is simply part of the Sierpinski triangle with a formula to calculate the number of triplets less than a given n.
Another way to create the Sierpinski triangle is via Pascals triangle. If you color the odd numbers in Pascal’s triangle and shade out all the other spaces, you will see Sierpinski’s triangle.
Project Euler 242 Solution
Runs < 0.001 seconds in Python 2.7.Use this link to get the Project Euler 242 Solution Python 2.7 source.
Afterthoughts

No afterthoughts yet.
Discussion
No comments yet.