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

[Arman777]

Homework Statement

https://projecteuler.net/problem=58

Homework Equations

The Attempt at a Solution

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 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

 

[mfb]

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

 

[Arman777]

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.

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)

 

[mfb]

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

You simply missed an earlier place where it drops below 10%.

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

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 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

 

[mfb]

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(J²), or ~150 million steps to reach 13,000. That takes a long time.
The code I posted takes a few seconds.