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.
Answer
Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.Afterthoughts

No afterthoughts yet.
Discussion
No comments yet.