Problem Twenty Seven

18 Nov

Here’s problem twenty seven:

Question: Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n = 0.

I’m not exactly sure why, but this was a pretty fun problem to do. Basically I just had to brute force my way through this problem, and it actually ran much faster than I anticipated.

Take a look:

def isPrime(x): 
	divisor = 3 
	limit = int(x**0.5) + 1

	while divisor < limit:
		if x % divisor == 0:
			return False
		else:
			divisor += 2 

	return True

result = [0, 0, 0] # a, b, counter

for a in range(-999, 1000):
	for b in range(-999, 1000):
		n = 0
		while True:
			x = n*n + a*n + b
			if x > 0 and isPrime(x):
				n += 1	
			else:
				if n > result[2]:
					result = [a, b, n]
				break

print(result[0]*result[1])

As you can see, I reused the ever-so-popular isPrime() function for this problem. We use two for loops to test every combination of coefficients, and initialize n, the independent variable of the quadratic, to 0. We then continue to generate values of the quadratic until we reach one that isn’t prime. The length of the chain generated is tested to see if it’s greater then the previous longest chain, and if it is we overwrite the variable result.

Answer: -59231

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: