PyPE solution to PE problem 2

Registered by Scott Armitage

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

Sprints

Whiteboard

    ProjectEuler.net problem 2
    ==========================

    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.fibonacci).
    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-high upper-bound for n, in this case the
    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

(?)

Work Items

This blueprint contains Public information 
Everyone can see this information.

Subscribers

No subscribers.