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 ≤ 10¹² ?

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

Afterthoughts

No afterthoughts yet.