// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (12 votes, average: 5.00 out of 5)
Loading...

Project Euler Solutions

Project Euler 242 Solution

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.
sierpinski

Project Euler 242 Solution

Runs < 0.001 seconds in Python 2.7.
download arrowUse this link to get the Project Euler 242 Solution Python 2.7 source.

Afterthoughts

    No afterthoughts yet.
Project Euler 242 Solution last updated

Discussion

No comments yet.

Post a comment