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

Answer

Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.
|34029210557338|

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