Problem 027

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.

This forum is NOT meant to discuss solution methods for a problem.

In particular don't post any code fragments or results.

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
nxn
Posts: 1
Joined: Sun Dec 05, 2010 7:41 am

Problem 027

Post by nxn »

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.
TripleM
Posts: 382
Joined: Fri Sep 12, 2008 3:31 am

Re: Problem 027

Post by TripleM »

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.
Spura
Posts: 8
Joined: Mon May 16, 2011 4:49 pm

Re: Problem 027

Post by Spura »

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
User avatar
GenePeer
Posts: 112
Joined: Sat Apr 03, 2010 1:14 pm
Contact:

Re: Problem 027

Post by GenePeer »

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.
Image
anorton
Posts: 4
Joined: Wed Nov 09, 2011 2:07 am

Re: Problem 027

Post by anorton »

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
Image
DanWebb314
Posts: 1
Joined: Fri Jun 07, 2013 12:13 am

Re: Problem 027

Post by DanWebb314 »

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?
thundre
Posts: 356
Joined: Sun Mar 27, 2011 10:01 am

Re: Problem 027

Post by thundre »

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.
Image
math_noob
Posts: 1
Joined: Wed Nov 06, 2013 5:21 pm

Re: Problem 027

Post by math_noob »

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?
User avatar
TheEvil
Posts: 84
Joined: Sun Nov 13, 2011 10:38 am
Location: Szeged, Hungary

Re: Problem 027

Post by TheEvil »

If you feed positive numbers in the polynom n2+an+b, it is the same as feeding negative numbers in n2-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.
Image
aware
Posts: 4
Joined: Sun Dec 28, 2014 11:11 pm

Re: Problem 027

Post by aware »

are a and b necessarily integers? Or can they be rational/irrational?
User avatar
jaap
Posts: 553
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Problem 027

Post by jaap »

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?
keyth
Posts: 2
Joined: Wed Jul 29, 2015 7:53 am

Re: Problem 027

Post by keyth »

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.
TripleM
Posts: 382
Joined: Fri Sep 12, 2008 3:31 am

Re: Problem 027

Post by TripleM »

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).
keyth
Posts: 2
Joined: Wed Jul 29, 2015 7:53 am

Re: Problem 027

Post by keyth »

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...
ksbeattie
Posts: 1
Joined: Thu Jan 03, 2019 7:46 am

Re: Problem 027

Post by ksbeattie »

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...
User avatar
kenbrooker
Posts: 187
Joined: Mon Feb 19, 2018 3:05 am
Location: Northern California, USA

Re: Problem 027

Post by kenbrooker »

If I understand your question, I know proof by example is not a proof but
I, for one, only find one solution for |a| < 1000 and |b| <= 1000
(in 8 seconds)... Hope that helps...
"Good Judgment comes from Experience;
Experience comes from Bad Judgment
..."
Image
Lucas-C
Posts: 2
Joined: Thu Nov 14, 2019 2:05 pm

Re: Problem 027

Post by Lucas-C »

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]:
Image

Does anyone know how to explain why a parabola appears ??
A finite one on top of that.
Lucas-C
Posts: 2
Joined: Thu Nov 14, 2019 2:05 pm

Re: Problem 027

Post by Lucas-C »

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)
User avatar
kenbrooker
Posts: 187
Joined: Mon Feb 19, 2018 3:05 am
Location: Northern California, USA

Re: Problem 027

Post by kenbrooker »

As you said --

Cet exemple est int´eressant...
"Good Judgment comes from Experience;
Experience comes from Bad Judgment
..."
Image
User avatar
kenbrooker
Posts: 187
Joined: Mon Feb 19, 2018 3:05 am
Location: Northern California, USA

Re: Problem 027

Post by kenbrooker »

philiplu et al

Accurate and precise as you are,
I wish you might take up
Lucas-C's challenge...

Respectfully,
glasshopper
"Good Judgment comes from Experience;
Experience comes from Bad Judgment
..."
Image
Post Reply