# Euler Solution 58

### From ProgSoc Wiki

# Solutions for 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%?

## Python by Althalus

Runtime: 41 seconds

import math #Same as problem 28. #It can be seen in the 5x5 grid, that there are 5 numbers in each diagonal. # :. in a 1001 by 1001 grid, there will be 101 numbers in the diagonal. #1. It can be seen in the 5x5 grid, that after 1, diagonal down to the right are #odd squares (3x3, 5x5) - There will be no prime numbers here. #2. It can be seen that the bottom left diagonal are even squares +1 #3. Top left = n*(n+1)+1,(n+2)*(n+3)+1....(2*3)+1,(4*5)+1,(6*7)+1 #4. Bottom right = (1*2)+1,(3*4)+1,(5*6)+1,(7*8)+1,(9*10)+1 #Function to determine if a number is prime def isPrime(num): for i in range(2,int(math.sqrt(num))+1): if (num%i) == 0: return False return True #Function that finds the prime numbers for the outermost ring of the given side length. #The 3 checks below correspond to the patterns I noticed above, but are expanded on to include #The pattern's relationship to the side length. def getPrimes(k): list = [] num = ((k-1)**2)+1 if isPrime(num):list.append(num) num = (k*(k-1))+1 if isPrime(num):list.append(num) num = ((k-2)*(k-1))+1 if isPrime(num):list.append(num) #lif i%2 != 0: return list side_length = 3 num_primes = 3 #Number in each diagonal is equal to side length. They share a number in the middle. while num_primes/(side_length*2-1) >= 0.1: #while side_length <=9: side_length+=2 #print('side_length = ',side_length) #print(getPrimes(side_length)) num_primes += len(getPrimes(side_length)) # print(num_primes) #print(side_length*2-1,', ',num_primes) print(side_length) print(num_primes) run_time = time.time() - start_time print (run_time)