Project Euler Forum

I would like to make a suggestion regarding the description/wording of Problem 027:

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 think that the directions would be clearer if they were stated as "... maximum number of consecutive primes for values of n starting with n = 0." As is, I found it easy to misinterpret the objective into finding the total amount of primes in a consecutive range of n=0 to n=a. I assumed 0 to a because of the following:

"Using computers, the incredible formula n² 79n + 1601 was discovered, which produces 80 primes for the consecutive values n = 0 to 79."

So since the objective is consecutive primes, I think the description should specifically state "consecutive primes" and not consecutive values of n.

The objective is not to find a function which produces consecutive primes. It is to find a function which is prime for consecutive values of n.

Your wording would imply f(0) = 2, f(1) = 3, f(2) = 5, etc, which is not the case. It is the values of n which must be consecutive, not the primes.

1. can negative integers be prime?
2. can primes repeat? for instance x^2 - 2x + 1601 is the same prime (1601) for n = 0 and n = 2

1. By definition, primes have to be positive integers.
2. Interesting point: Technically, it should be allowed but the prime counted only once. Didn't think of it when I solved it though.

I realize this was posted a long time ago, but I thought I'd post just in case someone else had the same question.

Spura wrote:2. can primes repeat? for instance x^2 - 2x + 1601 is the same prime (1601) for n = 0 and n = 2

Yes - the given equation n^2 - 79n + 1601 produces 80 primes, 40 of which are repeats.

//Andrew

One of the Posts mentioned that by definition, a prime number must be positive. That being said, then 'b' must be a positive number. If 'n' is zero and 'b' is negative, the result will be negative. Does this make sense?

DanWebb314 wrote:One of the Posts mentioned that by definition, a prime number must be positive. That being said, then 'b' must be a positive number. If 'n' is zero and 'b' is negative, the result will be negative. Does this make sense?

Yes, it makes sense. In fact, you might say the lowest possible value of b is 2, because nothing less will yield a prime for n=0.

On the wording of the problem, "produces 80 primes for the consecutive values n = 0 to 79" is still not correct. The function produces primes for 80 consecutive values of n, but there are less than 80 primes because they are not unique. n=0 and n=79 give the same prime, for example.

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

Is this statement in the problem implying that consecutive values of n can be both increasing or decreasing sequences starting from 0?

If you feed positive numbers in the polynom n²+an+b, it is the same as feeding negative numbers in n²-an+b. So the problem won't be easier and the only change would be in the sign of the answer. Anyway you will get the correct answer for increasing numbers.

are a and b necessarily integers? Or can they be rational/irrational?

aware wrote:are a and b necessarily integers? Or can they be rational/irrational?

What does the polynomial evaluate to for n=0 and n=1?

TripleM wrote:The objective is not to find a function which produces consecutive primes. It is to find a function which is prime for consecutive values of n.

Your wording would imply f(0) = 2, f(1) = 3, f(2) = 5, etc, which is not the case. It is the values of n which must be consecutive, not the primes.

I've been working on this problem for the last two days or so and I think (REALLY BIG ASTERISK HERE) I'm close. However, I keep coming back to the quote above since I obviously haven't solved it yet. Am I looking for the product coefficient of a & b that produced the most consecutive primes? So basically if a & b produce primes from n=0 to say n=6 and that is the most consecutive primes found (7), I multiple a * b and that's the answer?

So without giving anything away (I hope):
Keeping a<10 and b<10 I get a product of the coefficients (a&b) that equals 9 for a function that produces 6 consecutive primes. Can anyone please verify if that is correct?

My function tests for prime, if its prime for current a&b it increments n until it produces a non-prime number then it resets n and increments b. It keeps up this cycle until b is 9 then increments a and resets b and n to 0, all the while keeping track of the current number of consecutive primes and the highest amount found so far.

keyth wrote:Am I looking for the product coefficient of a & b that produced the most consecutive primes? So basically if a & b produce primes from n=0 to say n=6 and that is the most consecutive primes found (7), I multiple a * b and that's the answer?

Yes.

keyth wrote:Keeping a<10 and b<10 I get a product of the coefficients (a&b) that equals 9 for a function that produces 6 consecutive primes. Can anyone please verify if that is correct?

(edit) oops, ignore previous answer, but that is not correct (for |a|<10 and |b|<10).

TripleM wrote:

keyth wrote:Am I looking for the product coefficient of a & b that produced the most consecutive primes? So basically if a & b produce primes from n=0 to say n=6 and that is the most consecutive primes found (7), I multiple a * b and that's the answer?

Yes.

keyth wrote:Keeping a<10 and b<10 I get a product of the coefficients (a&b) that equals 9 for a function that produces 6 consecutive primes. Can anyone please verify if that is correct?

(edit) oops, ignore previous answer, but that is not correct (for |a|<10 and |b|<10).

Just got it, thanks! So yeah, working on this at 4 a.m. may cause you to miss silly things like absolute value.....good grief...

The statement of the problem seems to imply that there is only one pair (a,b) that solves the problem. Indeed that appears to be the case here, but when coding my answer I didn't make that assumption.

I'm not seeing a mathematical argument that the solution is unique. Is it if |a| & |b| can be larger than 1000? Did we just get lucky with this one?

BTW, I'm running my solution again with |a| < 10,000 & |b| <= 10,000, to see if it finds more than one such pair, but that's gonna take a little while...

I made an interesting observation while solving this problem.

I tried graphing the sequence length of the consecutive primes for given (a, b) values.

Given the following color scale:
- length > 50 => RED
- length > 15 => BLUE
- length > 1 => GREEN

I obtain the following graph for a in [-100, 100] and b in [0, 2000]:


Does anyone know how to explain why a parabola appears ??
A finite one on top of that.

I may have found some elements of answer in this PDF, at section 8.4:
https://www.math.u-psud.fr/~perrin/jour ... n2311e.pdf (French)