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

## 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: 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. Use 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
• Whoops! Thanks for catching that!

Posted by Mike Molony | May 16, 2016, 9:15 PM