PyPE solution to PE problem 53

Registered by Scott Armitage

The problem statement may be found here: http://projecteuler.net/index.php?section=problems&id=53
In summary, the goal is to determine how many values of `n choose r`, for 1<=n<=100, are greater than 10^6.

The PyPE solution to this problem uses the relation between Pascal's Triangle and binomial coefficients; namely, that nCr is equal to the rth entry in the nth row of Pascal's triangle, where indexing is from zero. The general approach is to test all of the centre values of the triangle -- as these are the largest in a given row -- until one is found that is greater than the desired limit. If it is an even row, then there are two centre elements, but luckily they will be identical, so we need only test for one.

Once the first entry has been found, we simply calculate the number of nodes in Pascal's Triangle that are children of this node, noting that they must all also be greater than the limit value. For an even row, we add the number of rows remaining (n_max-n+1) to the total number of found nodes. We then proceed backwards across this row checking the entries to see if they are also greater than the limit value -- if they are, we add the number of remaining rows (n_max-n+1) and continue; if they are not, then we increment the row -- keeping the entry r the same -- and continue our search.

This method means that for the majority of rows, only one nCr calculation must be performed, as the result will often be less than the limit and we can simply proceed to the next row.

Blueprint information

Status:
Started
Approver:
Scott Armitage
Priority:
Undefined
Drafter:
Scott Armitage
Direction:
Needs approval
Assignee:
Scott Armitage
Definition:
Approved
Series goal:
Accepted for trunk
Implementation:
Beta Available
Milestone target:
None
Started by
Scott Armitage

Related branches

Sprints

Whiteboard

Added solution module in lp:pype:4.

(?)

Work Items

This blueprint contains Public information 
Everyone can see this information.

Subscribers

No subscribers.