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.
Post Reply
nxn
Posts: 1
Joined: Sun Dec 05, 2010 7:41 am

Problem 027

Post by nxn » Sun Dec 12, 2010 7:34 am

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 2:31 am

Re: Problem 027

Post by TripleM » Sun Dec 12, 2010 8:47 am

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 3:49 pm

Re: Problem 027

Post by Spura » Fri Jun 17, 2011 9:29 am

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 12:14 pm
Contact:

Re: Problem 027

Post by GenePeer » Fri Jun 17, 2011 5:40 pm

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 » Sat Feb 04, 2012 2:41 am

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: Thu Jun 06, 2013 11:13 pm

Re: Problem 027

Post by DanWebb314 » Thu Jun 06, 2013 11:27 pm

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 9:01 am

Re: Problem 027

Post by thundre » Thu Jun 06, 2013 11:55 pm

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 » Wed Nov 06, 2013 5:39 pm

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 » Wed Nov 06, 2013 6:36 pm

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 » Wed Dec 31, 2014 12:58 am

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

User avatar
jaap
Posts: 533
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Problem 027

Post by jaap » Wed Dec 31, 2014 9:15 am

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 6:53 am

Re: Problem 027

Post by keyth » Wed Jul 29, 2015 7:17 am

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 2:31 am

Re: Problem 027

Post by TripleM » Wed Jul 29, 2015 8:00 am

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 6:53 am

Re: Problem 027

Post by keyth » Wed Jul 29, 2015 8:51 am

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 » Thu Jan 03, 2019 8:10 am

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: 113
Joined: Mon Feb 19, 2018 3:05 am
Location: Oregon, USA

Re: Problem 027

Post by kenbrooker » Thu Jan 03, 2019 9:01 am

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

Post Reply