Prime generating polynomials that stop? - Page 2

jinydu · 2005-09-13, 00:55

Hmm, we still haven't answered the question of whether or not:

$\displaystyle{n^2+n+41}$

generates infinitely many primes (presumably for non-negative values of n).

Clearly, though, it is not prime for any multiple of n = 41:

Let x = 41k

$\displaystyle{x^2+x+41}$

$\displaystyle{=41^2k^2+41k+41}$

$\displaystyle{=41(41k^2+k+1)}$

Orgasmic Troll · 2005-09-13, 03:47

Quote:

Originally Posted by R.D. Silverman

How about a polynomial that produces NO primes? There are, of course
infinitely many examples of this type.

f(x) = (x-1) (x-6) or f(x) = (x-3)(x-2)(x-5)(x-7) etc.

Perhaps it's an unclear assumption, but I don't think a polynomial can *stop* generating primes if it never starts

Orgasmic Troll · 2005-09-13, 03:54

Quote:

Originally Posted by Ken_g6

I'm assuming you're looking for f(x), where for x any nonnegative integer, there are only N>1 cases where f(x) is prime?

Okay, try this on for size

:

f(x) = 3-x

f(0) = 3, Prime!
f(1) = 2, Prime!
f(2) = 1, not prime!
f(3) = 0, not prime!
for x>=4, f(x) < 0; therefore f(x) is not prime!

Actually, I wasn't thinking of restricting x to be nonnegative, instead looking at the nonnegative outputs, in which case, 3 -x produces an infinite number of primes

Numbers · 2005-09-13, 06:45

The formula n^2 + n + 41 generates primes for n = 0 - 39

In the 1970's some tests were run on a computer called Maniac II for values of n up to 10 million. It will generate pimes 47.5% of the time but there are no further sequences of primes in that range.

xilman · 2005-09-13, 08:53

Quote:

Originally Posted by Ken_g6

I'm assuming you're looking for f(x), where for x any nonnegative integer, there are only N>1 cases where f(x) is prime?

Okay, try this on for size

:

f(x) = 3-x

f(0) = 3, Prime!
f(1) = 2, Prime!
f(2) = 1, not prime!
f(3) = 0, not prime!
for x>=4, f(x) < 0; therefore f(x) is not prime!

By any reasonable definition of "prime", if x is prime, so is -x.

Thus -2, -3, -5, ... are all primes and your polynomial generates them.

Paul

Numbers · 2005-09-13, 09:02

By �reasonable� definition do you mean �a number that is only divisible by itself and 1�?

By this criteria �5 is not prime since �1 | -5, etc.

R.D. Silverman · 2005-09-13, 10:10

Quote:

Originally Posted by jinydu

Hmm, we still haven't answered the question of whether or not:

$\displaystyle{n^2+n+41}$

generates infinitely many primes (presumably for non-negative values of n).

Clearly, though, it is not prime for any multiple of n = 41:

Let x = 41k

$\displaystyle{x^2+x+41}$

$\displaystyle{=41^2k^2+41k+41}$

$\displaystyle{=41(41k^2+k+1)}$

The answer is yes. It produces infinitely many primes.
Any non-constant irreducible polynomial does.

A proof, however, is lacking. We have not proof, for example, that
x^2 + 1 is prime i.o.

R.D. Silverman · 2005-09-13, 10:13

Quote:

Originally Posted by Numbers

By �reasonable� definition do you mean �a number that is only divisible by itself and 1�?

By this criteria �5 is not prime since �1 | -5, etc.

Typical newbie crank response: Open mouth and display ignorance.

-5 is prime. It differs from +5 only by multiplication by a UNIT.

You might understand this if you ever bothered to STUDY this subject.

jinydu · 2005-09-13, 11:38

Quote:

Originally Posted by R.D. Silverman

The answer is yes. It produces infinitely many primes.
Any non-constant irreducible polynomial does.

A proof, however, is lacking. We have not proof, for example, that
x^2 + 1 is prime i.o.

Hmm... How do we know that it produces infinitely many primes if we don't have a proof?

Quote:

Originally Posted by Numbers

The formula n^2 + n + 41 generates primes for n = 0 - 39

In the 1970's some tests were run on a computer called Maniac II for values of n up to 10 million. It will generate pimes 47.5% of the time but there are no further sequences of primes in that range.

Interesting. But if those tests were run in the 1970s, it should be easy to run tests to far larger values of n using today's computers. Do you have any more information?

cheesehead · 2005-09-13, 12:10

Quote:

Originally Posted by jinydu

Hmm... How do we know that it produces infinitely many primes if we don't have a proof?

It is conjectured that it produces infinitely many primes.

Some folks use know when they would mean, if they were in a mood to be more precise, have a conjecture for which there is so great an amount of confirming data that I am convinced it's true.

R.D. Silverman · 2005-09-13, 12:16

Quote:

Originally Posted by jinydu

Hmm... How do we know that it produces infinitely many primes if we don't have a proof?

Interesting. But if those tests were run in the 1970s, it should be easy to run tests to far larger values of n using today's computers. Do you have any more information?

Do a web search on Schinzel's Conjecture.
Do a web search on the "Bateman-Horn" conjecture.

These are extensions of, e.g. the twin prime conjecture.

The k-tuples conjecture states that not only are p, p+2 both prime i.o.,
but that any permissible set of linear polynomials will be simultaneously
prime i.o. Permissible has a technical definition, but roughly means "has
no common factor". For example, p, p+2, p+4 is not permissible because
one of these must be divisible by 3. However, p, p+2, p+6 is permissible.

Schninzel's conjecture extends this to include non-linear polynomials.

Bateman-Horn gives explicit analytic estimates for the *frequency* with
which a collection is simultaneously prime.

The evidence (supported by probabilistic heuristics) is overwhelming that
an irreducible polynomial is prime i.o. Certain technical obstacles have
prevented a proof so far [the parity problem in sieve methods]

Running further numerical 'tests' is pointless. It would add no new insight.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Error generating or reading NFS polynomials	Brownfox	Msieve	7	2018-04-06 16:24
Prime generating series	Citrix	Open Projects	18	2013-08-24 05:24
when does prime seach stop?	Unregistered	Information & Answers	5	2011-08-10 01:38
LLR 3.8.2: more flexible stop-on-prime option	mdettweiler	Conjectures 'R Us	21	2010-10-03 13:38
Prime-generating polynomials	Orgasmic Troll	Math	28	2004-12-02 16:37

2005-09-13, 00:55	#12
jinydu Dec 2003 Hopefully Near M48 6DE₁₆ Posts	Hmm, we still haven't answered the question of whether or not: $\displaystyle{n^2+n+41}$ generates infinitely many primes (presumably for non-negative values of n). Clearly, though, it is not prime for any multiple of n = 41: Let x = 41k $\displaystyle{x^2+x+41}$ $\displaystyle{=41^2k^2+41k+41}$ $\displaystyle{=41(41k^2+k+1)}$

2005-09-13, 06:45	#15
Numbers Jun 2005 Near Beetlegeuse 604₈ Posts	The formula n^2 + n + 41 generates primes for n = 0 - 39 In the 1970's some tests were run on a computer called Maniac II for values of n up to 10 million. It will generate pimes 47.5% of the time but there are no further sequences of primes in that range.

2005-09-13, 09:02	#17
Numbers Jun 2005 Near Beetlegeuse 184₁₆ Posts	By �reasonable� definition do you mean �a number that is only divisible by itself and 1�? By this criteria �5 is not prime since �1 \| -5, etc.