#
#
import fractions
import itertools

from euler_python.utils import eulerlib


# From the diagram, let's observe the four corners of an n * n square (where n is odd).
# It's not hard to convince yourself that:
# - The bottom right corner always has the value n^2.
# Working clockwise (backwards):
# - The bottom left corner has the value n^2 - (n - 1).
# - The top left corner has the value n^2 - 2(n - 1).
# - The top right has the value n^2 - 3(n - 1).
# Furthermore, the number of elements on the diagonal is 2n - 1.
def problem058():
    """


    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%?
    """
    target = fractions.Fraction(1, 10)
    numprimes = 0
    for n in itertools.count(1, 2):
        for i in range(4):
            if eulerlib.is_prime(n * n - i * (n - 1)):
                numprimes += 1
        if n > 1 and fractions.Fraction(numprimes, n * 2 - 1) < target:
            return n


if __name__ == "__main__":
    print(problem058())
