# When Does the Prime Ratio of Spiral Diagonals Drop Below 10%?

• Arman777
In summary, the conversation revolved around finding the side length of a square where the percentage of primes in its diagonals is less than 10%. The participants discussed various solutions, including using a trial and error method and checking each number individually, but eventually settled on a more efficient algorithm that involves checking the 10% condition each time and keeping track of the number of primes found.
Arman777
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 countJ = 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 length of the diagonals
if d < 0.10:   #percent thing
print(d)     #the percantage
print((J-1)*2+1)   #side length 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 don't know why
İf you put J = 4 you ll get the result as the question does

Last edited by a moderator:
Where does 13296 come from? That gives you a side length of 13296*2-1.

mfb said:
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 that's not the answer.
Side length shold be 25691 from my calculations.
mfb said:
That gives you a side length of 13296*2-1.
I don't think so.

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

((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
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 countfor 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 don't 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

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

## 1. What is the purpose of Project Euler Question 58?

Project Euler Question 58 is a mathematical programming problem designed to challenge and improve problem-solving skills. It involves finding the ratio of prime numbers along the diagonals of a spiral formed by consecutive numbers.

## 2. How do I approach solving Project Euler Question 58?

The best approach for solving Project Euler Question 58 is to break down the problem into smaller parts and use mathematical concepts and algorithms to find the solution. It is also helpful to have a good understanding of prime numbers and how they behave.

## 3. What is the significance of finding the ratio of primes along the diagonals?

The ratio of primes along the diagonals of the spiral in Project Euler Question 58 is a measure of how "dense" the primes are in the spiral. It can also reveal patterns and relationships between prime numbers and consecutive numbers.

## 4. How can I optimize my code for Project Euler Question 58?

There are various ways to optimize the code for Project Euler Question 58, such as using efficient algorithms, reducing the number of calculations, and using data structures to store and retrieve information. It is also important to analyze and improve the code as you solve more Project Euler problems.

## 5. Are there any resources to help with solving Project Euler Question 58?

Yes, there are many online resources and forums where you can find discussions and solutions for Project Euler problems. It is also helpful to refer to mathematical and programming textbooks and practice solving similar problems to improve your skills.

• Engineering and Comp Sci Homework Help
Replies
80
Views
8K
• Engineering and Comp Sci Homework Help
Replies
10
Views
1K
• Programming and Computer Science
Replies
97
Views
7K
• Programming and Computer Science
Replies
5
Views
4K
• Programming and Computer Science
Replies
5
Views
1K
• Programming and Computer Science
Replies
4
Views
2K
• Programming and Computer Science
Replies
4
Views
1K
• Programming and Computer Science
Replies
1
Views
3K
• Engineering and Comp Sci Homework Help
Replies
9
Views
2K
• General Math
Replies
4
Views
2K