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.
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 PMWhoops! Thanks for catching that!
Posted by Mike Molony | May 16, 2016, 9:15 PM