Euler Solution 58

From ProgSoc Wiki

Jump to: navigation, search

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)
Personal tools