PyPE solution to PE problem 2
PyPE solution to PE problem 2
Blueprint information
- Status:
- Complete
- Approver:
- None
- Priority:
- Undefined
- Drafter:
- None
- Direction:
- Needs approval
- Assignee:
- None
- Definition:
- Approved
- Series goal:
- None
- Implementation:
- Implemented
- Milestone target:
- None
- Started by
- Scott Armitage
- Completed by
- Scott Armitage
Whiteboard
ProjectEule
===
Each new term in the Fibonacci sequence is generated by adding the
previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
Find the sum of all the even-valued terms in the sequence which do not
exceed four million.
Solution
--------
We first assume a function exists to quickly calculate Fn, the nth
Fibonacci number (indeed, such a function exists: PyPE.pemath.
Next, we notice that every thrid Fibonacci number, beginning with n = 3,
is even, hence we need only check n = 3*i, i=0,..,N.
We establish an unrealistically
limit value itself, i.e. n <= N = 4*10**6. We break out of the iteration
once the value of the Fibonacci number exceeds the limit. This is acceptable
thanks to the use of xrange, which can accept arbitrarily large limit values
without consuming additional memory or increasing the iteration time.
However, for elegance, a second upper bound on n is desired. Indeed, it is
desirable to have the loop iterate precisely the number of times required
without having to break out of it with a return statement. Some variation
of an inverse-Fibonacci function could be useful here.
Answer
------
4613732