PyPE solution to PE problem 53
The problem statement may be found here: http://
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
- Completed by
Related branches
Related bugs
Sprints
Whiteboard
Added solution module in lp:pype:4.