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

Project Euler Solutions

Project Euler 203 Solution

Project Euler 203 Solution

Project Euler 203: Find the sum of the distinct square-free numbers in Pascal's triangle.


Problem Description

The binomial coefficients nCk can be arranged in triangular form, Pascal’s triangle, like this:

Eight rows of Pascal's Triangle

It can be seen that the first eight rows of Pascal’s triangle contain twelve distinct numbers: 1, 2, 3, 4, 5, 6, 7, 10, 15, 20, 21 and 35.

A positive integer n is called square-free if no square of a prime divides n.
Of the twelve distinct numbers in the first eight rows of Pascal’s triangle, all except 4 and 20 are square-free.
The sum of the distinct square-free numbers in the first eight rows is 105.

Find the sum of the distinct square-free numbers in the first 51 rows of Pascal’s triangle.

Analysis

Only a few primes are required. For example, 51! is the biggest numerator (nCk = n! / k! (n-k)! ) and the largest prime factor required is ≤ √51 which is 7. You can add a few more to try bigger problems.

So we fill a set with distinct numbers from Pascal's triangle and iterate through the 614 binomial coefficients and track which ones are square-free, sum them up and print the results. I only wish my biometrics problems were this obvious.

Project Euler 203 Solution

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

Afterthoughts

    No afterthoughts yet.
Project Euler 203 Solution last updated

Discussion

2 Responses to “Project Euler 203 Solution”

  1. I think the number of binomial coefficients for 51 rows is 614, not 589. 589 would be the correct amount for 50 rows.
    Nice solution apart from that.

    Posted by fish | May 1, 2016, 7:28 PM

Post a comment