Problem 27 Project Euler Solution with python

Quadratic primes

Euler discovered the remarkable quadratic formula:

n² + n + 41

It turns out that the formula will produce 40 primes for the consecutive values n = 0 to 39. However, when n = 40, 40² + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when n = 41, 41² + 41 + 41 is clearly divisible by 41.

The incredible formula n² − 79n + 1601 was discovered, which produces 80 primes for the consecutive values n = 0 to 79. The product of the coefficients, −79 and 1601, is −126479.

Considering quadratics of the form:

n² + an + b, where |a| < 1000 and |b| < 1000

where |n| is the modulus/absolute value of n
e.g. |11| = 11 and |−4| = 4

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.

Before I start solving this problem, I would like to apologize for not posting the solution for these many days. I will try to post a solution every day, but I had some other work and couldn't post any.

This problem was pretty easy, but to solve this problem you will have to make some observations. Okay lets first see the observations and then we can write the program.

Let us consider the equation as ƒ(n) = n²+an+b, for ƒ(0) to be prime the value of b should be prime. So we can eliminate all the composite numbers. Now for selecting the value of 'a' consider the following equations:

ƒ₁(n) = n²+n+13
ƒ₂(n) = n²+2n+13
ƒ₃(n) = n²+3n+13
ƒ₄(n) = n²+4n+13
ƒ₅(n) = n²+5n+13

or choose any number of equations you want, but make sure that the value of b is a prime number(it is better that all the equations have same value of b to make observations), the value of 'a' should be a mix of both composite and prime numbers as shown.

Number of iterations after which the equations above don't produce a prime number is

ƒ₁(n) → n = 0
ƒ₂(n) → n = 0
ƒ₃(n) → n = 0, 1, 2, 3, 4, 5, 6, 7, 8
ƒ₄(n) → n = 0
ƒ₅(n) → n = 0, 1

If you have observed the equations which had 'a' with prime numbers had more iterations when compared to the composite numbers. Also you should have observed that when composite numbers are used the values of 'n' don't go a long way as the prime number do.

This proves that you can eliminate all the composite numbers for 'a'. This works for all the value of negative 'a' also but not negative 'b', because we cannot have prime numbers which are less than 0.

So you can finally just use prime numbers below 1000 for both 'a' and 'b' in the quadratic equation.

Now we know the forms that quadratic equation takes, but we don't know the maximum value the quadratic can produce, but checking each and every number for Primality will be inefficient. So the best way is that we will use the primes upto 1000 which we have already generated for 'a', 'b' and any new prime number created greater than 1000 will be checked for Primality and will be appended to a primes list so that we can eliminate extra iterations.

That's it, as simple as that. Now go ahead and see the program line by line and I am sure you will understand it easily.

Program

File: pep27.py ------------------------- #http://radiusofcircle.blogspot.com #time module for calculating execution time import time #time at the start of execution start = time.time() #sieve of Eratosthenes #https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes #used from problem 7 solution #http://bit.ly/24bPJV6 def sieve(n): is_prime = [True]*n is_prime[0] = False is_prime[1] = False for i in xrange(2,int(n**0.5+1)): index = i*2 while index < n: is_prime[index] = False index = index+i prime = [] for i in xrange(n): if is_prime[i] == True: prime.append(i) return prime def is_prime(n): """function to check if the number is prime or not""" for i in xrange(2,int(abs(n)**0.5)+1): if n%i == 0: return False return True #primes below 1000 primes1000 = sieve(1000) #copy of primes1000 variable primes = primes1000[:] #assume the largest value is 0 at start largest = 0 #looping through a quadratic equation for b in primes1000: for a in primes1000: i = 0 #positive a and b while True: quadratic = i**2+a*i+b if quadratic not in primes: if is_prime(quadratic): primes.append(quadratic) else: if i-1 > largest: largest = i-1 axb = a*b break i += 1 i = 0 #negative a and positive b while True: quadratic = i**2-a*i+b if quadratic not in primes: if is_prime(quadratic) and quadratic>0: primes.append(quadratic) else: if i-1 > largest: largest = i-1 axb = -1*a*b break i += 1 #printing the largest value of a*b print axb #printing the total time of execution print time.time() - start

The code is well commented . I have already explained the algorithm behind this code above.

Seive of Eratosthenes function has been used from problem 7 solution with python.

[:] list slicing has been used to make a copy of the list. If we had not copied the list and just made use of the same list then as we keep on appending a new prime to primes the value also gets appended to prime1000 also and this will become an infinite loop. For example:

>>> list1 = [1,2,3]
>>> list2 = list1
>>> for i in list1:
 list2.append(i)
 print list1

 
[1, 2, 3, 1]
[1, 2, 3, 1, 2]
[1, 2, 3, 1, 2, 3]
[1, 2, 3, 1, 2, 3, 1]
.............................. this continues forever!

In the above example even though I have appended the value to list2 the value also got appended to list1 making the for loop to be infinite.

Solution is to make a copy of the list and not just use the same list. You can copy list in many ways.
How to clone or copy a list in python?

>>> list1 = [1,2,3]
>>> list2 = list1[:] #fastest
>>> list2 = list(list1) 
>>> import copy #not fast
>>> list2 = copy.copy(list1)
>>> list2 = copy.deepcopy(list1)
>>>

If you want you can download the source code from github gist pep27.py

Output

Summary

I didn't knew how to prove that 'a' takes prime numbers as values, but finally I took an example and have proved it to you. This problem is a direct programming of the question and there is no need for any new mathematical concept.

I have tried my level best to explain each and every part in this post clearly. But if you haven't understood anything or have any doubt then please do comment in the comment box below and I will be glad to help you.

Please don't hesitate to comment if you have found any typo or any mistake in any part of this website, so that I can rectify the mistake at earliest. Please do share your code in the comment box below even if it runs slower than above code.

You can also contact me.

Thank you. Have a nice day😄.

RADIUS OF CIRCLE

Search This Blog