PyPE solution to PE problem 58
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
Related bugs
Sprints
Whiteboard
ProjectEule
===
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