PyPE solution to PE problem 58

Registered by Scott Armitage

PyPE solution to PE problem 58

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

Related branches

Sprints

Whiteboard

    ProjectEuler.net problem 58
    ===========================

    Starting with 1 and spiralling anticlockwise in the following way, a square
    spiral with side length 7 is formed.

        37 36 35 34 33 32 31
        38 17 16 15 14 13 30
        39 18 5 4 3 12 29
        40 19 6 1 2 11 28
        41 20 7 8 9 10 27
        42 21 22 23 24 25 26
        43 44 45 46 47 48 49

    It is interesting to note that the odd squares lie along the bottom right
    diagonal, but what is more interesting is that 8 out of the 13 numbers lying
    along both diagonals are prime; that is, a ratio of 8/13 ~= 62%.

    If one complete new layer is wrapped around the spiral above, a square spiral
    with side length 9 will be formed. If this process is continued, what is the
    side length of the square spiral for which the ratio of primes along both
    diagonals first falls below 10%?

    Solution
    --------

    The spiral in this problem is closely related to the spiral formed in
    problem 28, except the opposite direction.

    We notice that in an n x n grid created by an anticlockwise sprial as
    described in the problem statement, the lower-right diagonal value is n^2.
    Working back clockwise on the same radial coordinate, we see that the three
    other diagonals are given by:

        n^2-2n+1 n^2-3n+3

        n^2-n+1 n^2

    We can use this to easily calculate the diagonal numbers at a given radial
    coordinate, and then test each one for primality, noting in particular that
    n^2 is never prime.

    NOTE: In Python, at length of side 26241, the calculated percentage of primes
    is exactly 10%, i.e. it has /reached/ the limit but not /passed/ it, and so
    the proper answer should be 26243. However, PE disagrees, and so a "<=" test
    is used instead of "<", in order to force the proper answer to be returned
    by this module.

    Answer
    ------

    26241

(?)

Work Items

This blueprint contains Public information 
Everyone can see this information.

Subscribers

No subscribers.