Problem Description

The binomial coefficients ⁿC_k 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 squarefree 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 squarefree.
The sum of the distinct squarefree numbers in the first eight rows is 105.

Find the sum of the distinct squarefree numbers in the first 51 rows of Pascal’s triangle.

Analysis

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

So we fill a hash’s keys with unique numbers from Pascal’s triangle and iterate through the 589 binomial coefficients and track which ones are squarefree, sum them up and print the results.

Solution

Runs < 1 second in Perl.

@primes = (2, 3, 5, 7, 11, 13, 17, 19);
$rows = 51; #more rows means more primes
$s = 0;
 
#use a hash, b, to select the distinct binomial coefficients from Pascal's triangle
while((@_=(1,map$_[$_-1]+$_[$_],1..@_))<=$rows){ grep $b{$_}++, @_}
 
for $x (keys %b) {
  $s+=$x if sqf($x);
}
print "Answer to PE203 = $s";
 
sub sqf { return ! grep @_[0]%($_*$_)==0, @primes }

Comments

Wanton use of grep and map.