     (12 votes, average: 5.00 out of 5) Loading...

## Project Euler 242 Solution ## 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 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 ≤ 1012 ?

#### 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.
Project Euler 242 Solution last updated