I've written a Python solution for Euler Project problem 27. It works, but is geologically slow (1765 seconds to find the correct result of -59,231). To speed things up, I would like to replace the mammoth 2D list "box" with a 1D list? My question is, how do I do that? Here's the problem: And here's my code:
import time
from sympy import isprime
start_time = time.time()
a_lower_limit = -999
a_upper_limit = 1000
b_lower_limit = 0
b_upper_limit = 1001
a1 = abs(a_lower_limit)
a2 = a_upper_limit - a_lower_limit
b2 = b_upper_limit - b_lower_limit
# 2d list of primes for permutations of a, b
box = [[] for j in range(a2 * b2)]
# 2d list of a*b for each a, b permutation
box_ab = [[] for j in range(a2 * b2)]
for a in range(a_lower_limit, a_upper_limit):
for b in range(b_lower_limit, b_upper_limit):
a_prime = a + a1
for n in range(0, b_upper_limit):
num = n**2 + a*n + b
if isprime(num):
box[(a_prime * b2) + b].append(num)
box_ab[(a_prime * b2) + b].append(a*b)
# Define a function that finds the longest sub-list in "box"
def max_length_list(box):
max_length = max(len(x) for x in box)
max_list = max(box, key=len)
return (max_list)
# Find index of max_length_list in box
x = box.index(max_length_list(box))
# Product of coefficients a and b that produce the longest sub-list in "box"
print((box_ab[x])[0])
print(f"Run time: {(time.time() - start_time):.2f} seconds")
For each permutation of a and b, the code finds the number of primes generated for consecutive values of n, starting with n = 0. These are then stored in different sub-lists in the 2D list “box”. I would like to replace this 2D “box” with a list: box = [] and a variable max_number_primes, initially set to zero. For each permutation of a and b, the generated primes need to be stored in the list “box”. After each permutation, I would then like to compare len(box) with max_number_primes. If len(box) > max_number_primes, then max_number_primes = len(box). Eventually, I will get the largest possible max_number_primes. I can then try to find the corresponding a*b.
This (and variations on this) is what I've tried. But I can't get it to work.
a_lower_limit = -999
a_upper_limit = 1000
b_lower_limit = 0 # for now, always set to zero
b_upper_limit = 1001
a1 = abs(a_lower_limit)
b1 = abs(b_lower_limit) # don't need this if b_lower_limit set to zero
a2 = a_upper_limit - a_lower_limit
b2 = b_upper_limit - b_lower_limit
box = [] # list of primes
max_number_primes = 0
for a in range(a_lower_limit, a_upper_limit):
for b in range(b_lower_limit, b_upper_limit):
if a_lower_limit < 0:
a_prime = a + a1
else:
a_prime = a - a_lower_limit
for n in range(0, b_upper_limit):
num = n**2 + a*n + b
if isprime(num):
box.append(num)
if len(box) > max_number_primes:
max_number_primes = len(box)
box.clear
I've written a Python solution for Euler Project problem 27. It works, but is geologically slow (1765 seconds to find the correct result of -59,231). To speed things up, I would like to replace the mammoth 2D list "box" with a 1D list? My question is, how do I do that? Here's the problem: And here's my code:
import time
from sympy import isprime
start_time = time.time()
a_lower_limit = -999
a_upper_limit = 1000
b_lower_limit = 0
b_upper_limit = 1001
a1 = abs(a_lower_limit)
a2 = a_upper_limit - a_lower_limit
b2 = b_upper_limit - b_lower_limit
# 2d list of primes for permutations of a, b
box = [[] for j in range(a2 * b2)]
# 2d list of a*b for each a, b permutation
box_ab = [[] for j in range(a2 * b2)]
for a in range(a_lower_limit, a_upper_limit):
for b in range(b_lower_limit, b_upper_limit):
a_prime = a + a1
for n in range(0, b_upper_limit):
num = n**2 + a*n + b
if isprime(num):
box[(a_prime * b2) + b].append(num)
box_ab[(a_prime * b2) + b].append(a*b)
# Define a function that finds the longest sub-list in "box"
def max_length_list(box):
max_length = max(len(x) for x in box)
max_list = max(box, key=len)
return (max_list)
# Find index of max_length_list in box
x = box.index(max_length_list(box))
# Product of coefficients a and b that produce the longest sub-list in "box"
print((box_ab[x])[0])
print(f"Run time: {(time.time() - start_time):.2f} seconds")
For each permutation of a and b, the code finds the number of primes generated for consecutive values of n, starting with n = 0. These are then stored in different sub-lists in the 2D list “box”. I would like to replace this 2D “box” with a list: box = [] and a variable max_number_primes, initially set to zero. For each permutation of a and b, the generated primes need to be stored in the list “box”. After each permutation, I would then like to compare len(box) with max_number_primes. If len(box) > max_number_primes, then max_number_primes = len(box). Eventually, I will get the largest possible max_number_primes. I can then try to find the corresponding a*b.
This (and variations on this) is what I've tried. But I can't get it to work.
a_lower_limit = -999
a_upper_limit = 1000
b_lower_limit = 0 # for now, always set to zero
b_upper_limit = 1001
a1 = abs(a_lower_limit)
b1 = abs(b_lower_limit) # don't need this if b_lower_limit set to zero
a2 = a_upper_limit - a_lower_limit
b2 = b_upper_limit - b_lower_limit
box = [] # list of primes
max_number_primes = 0
for a in range(a_lower_limit, a_upper_limit):
for b in range(b_lower_limit, b_upper_limit):
if a_lower_limit < 0:
a_prime = a + a1
else:
a_prime = a - a_lower_limit
for n in range(0, b_upper_limit):
num = n**2 + a*n + b
if isprime(num):
box.append(num)
if len(box) > max_number_primes:
max_number_primes = len(box)
box.clear
There may be some shortcuts to this (I'm not a mathematician) but I find simple nested loops to be efficient in this case:
import sympy
import time
from functools import cache
from collections.abc import Iterator
@cache
def isprime(p: int) -> bool:
return sympy.isprime(p)
# Sieve of Eratosthenes
# CREDIT: David Eppstein, UC Irvine, 28 Feb 2002
def sieve() -> Iterator[int]:
D = {}
q = 2
while True:
if q not in D:
yield q
D[q * q] = [q]
else:
for p in D[q]:
D.setdefault(p + q, []).append(p)
del D[q]
q += 1
def genprimes(limit: int) -> Iterator[int]:
for p in sieve():
if p > limit:
break
yield p
if __name__ == "__main__":
A = B = m = 0
start = time.perf_counter()
primes = list(genprimes(1000))
for a in range(-999, 1000, 2):
for b in primes:
n = 1
while isprime(n * n + a * n + b):
n += 1
if n > m:
A, B = a, b
m = n
duration = time.perf_counter() - start
print(f"{A=:,d} {B=:,d} C={A*B:,d} {m=:,d} {duration=:.4f}s")
Output:
A=-61 B=971 C=-59,231 m=71 duration=0.0305s