# Project Euler Question 58 -- ratio of primes along both diagonals of a spiral...

Gold Member

## Homework Statement

https://projecteuler.net/problem=58

## The Attempt at a Solution

Python:
def prime(N):
if N == 1:
return False
y = int(N**0.5)
for i in range(2,y+1):
if N%i == 0:
return False
return True

def finder(N):
L = len(N)
count = 0
for i in N:
if prime(i) == True:
count += 1
return count

J = 13296
D1 = [(2*n+1)**2 for n in range(1,J)]    #diagonal 1
D2 = [4*n**2+1 for n in range(1,J)]       #diagonal 2
D3 = [4*n**2+2*n+1 for n in range(1,J)]    #diagonal 3
D4 = [(4*n**2)-(2*n)+1 for n in range(1,J)]   #diagonal 4
f = finder(D1) + finder(D2) + finder(D3) + finder(D4)    #sum of primes in the diagonals
d = f/((J-1)*4+1)     #sum of primes divided by lenght of the diagonals
if d < 0.10:   #percent thing
print(d)     #the percantage
print((J-1)*2+1)   #side lenght of the square

Well I know this is not a great solution because I tried to find it with trial and error method.

At trial 13296 I should have the correct result but it seems wrong I dont know why
İf you put J = 4 you ll get the result as the question does

Last edited by a moderator:

mfb
Mentor
Where does 13296 come from? That gives you a side length of 13296*2-1.

Gold Member
Where does 13296 come from?
By trial and error. It wasnt so hard to find that if you put one lower number its more then 0.1 and one less number well thats not the answer.
Side lenght shold be 25691 from my calculations.
That gives you a side length of 13296*2-1.
I dont think so.

I think it should be like ((J-1)*2+1)

mfb
Mentor
((J-1)*2+1) = J*2-1.

You simply missed an earlier place where it drops below 10%.
Code:
def findprimes(N):
...   count=0
...   if prime(4*N*N+4*N+1):
...     count+=1
...   if prime(4*N*N+1):
...     count+=1
...   if prime(4*N*N+2*N+1):
...     count+=1
...   if prime(4*N*N-2*N+1):
...     count+=1
...   return count

>>> J=1
>>> primes=3
>>> while primes*1./(4*J+1)>0.1:
...   J+=1
...   primes+=findprimes(J)
...
>>> J
13120
>>> primes
5248
Note that I defined J a bit different.

Arman777
Gold Member
whats j or primes in here ?

At first my code was something like
Python:
def prime(N):
if N == 1:
return False
y = int(N**0.5)
for i in range(2,y+1):
if N%i == 0:
return False
return True

def finder(N):
L = len(N)
count = 0
for i in N:
if prime(i) == True:
count += 1
return count

for J in range(2,30000):
D1 = [(2*n+1)**2 for n in range(1,J)]
D2 = [4*n**2+1 for n in range(1,J)]
D3 = [4*n**2+2*n+1 for n in range(1,J)]
D4 = [(4*n**2)-(2*n)+1 for n in range(1,J)]
f = finder(D1) + finder(D2) + finder(D3) + finder(D4)
d = f/((J-1)*4+1)
if d < 0.10:
print(d)
print((J-1)*2+1)
or this was my idea but then it just dont work fast enough

I guess you are checking for each number rather then putting them into the array and check them one by one. Definitly much faster algorithm

mfb
Mentor
My J is the length of a diagonal half without the center, primes is the number of primes corresponding to it. My code adds another side everywhere step by step and checks the 10% condition each time, keeping track of the primes found so far.

Checking each J without remembering the previous result runs in O(J2), or ~150 million steps to reach 13,000. That takes a long time.
The code I posted takes a few seconds.

Arman777