• Support PF! Buy your school textbooks, materials and every day products Here!

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

  • Thread starter Arman777
  • Start date
  • #1
1,735
138

Homework Statement


https://projecteuler.net/problem=58

Homework Equations




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:

Answers and Replies

  • #2
34,060
9,937
Where does 13296 come from? That gives you a side length of 13296*2-1.
 
  • #3
1,735
138
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)
 
  • #4
34,060
9,937
((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.
 
  • #5
1,735
138
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
 
  • #6
34,060
9,937
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.
 

Related Threads on Project Euler Question 58 -- ratio of primes along both diagonals of a spiral...

  • Last Post
Replies
5
Views
700
Replies
7
Views
735
  • Last Post
4
Replies
80
Views
4K
Replies
4
Views
6K
  • Last Post
Replies
5
Views
2K
  • Last Post
2
Replies
27
Views
1K
Replies
0
Views
3K
  • Last Post
Replies
1
Views
1K
Top