## Prime Generating Polynomial contest

Expand Messages
• \$250 and numerous smaller prizes will go to the best prime generating polynomials, in the latest Al Zimmermann programming contest. Details at
Message 1 of 23 , Mar 14, 2006
• 0 Attachment
\$250 and numerous smaller prizes will go to the best prime generating
polynomials, in the latest Al Zimmermann programming contest.

Details at
http://recmath.org/contest/description.php

Ed Pegg Jr
• ... Can you tell us how you discovered that polynomial? The discriminant is very smooth, being 5^3*11^2, and I suspect that that s an essential ingredient to a
Message 2 of 23 , Mar 14, 2006
• 0 Attachment
--- aldrich617 <aldrich617@...> wrote:
> I am searching for a way to prove the following Theorem:
>
> For any integer 'B', the value 'A' of the equation
> A = 5B^4 -10B^3 + 20B^2 -15B +11 will have as factors only
> integers that end in a one, excluding all others.
>
> This seems to be true at least up to 10^18. I think that proving
> it could give us new insights into primality testing,
> and factoring. Moreover there are similar equations, vast in
> number, apparently with the same property, that could then probably
> be verified to be similar threads of pure one. Together these
> would form an infinite interconnecting web.

Can you tell us how you discovered that polynomial?
The discriminant is very smooth, being 5^3*11^2, and I suspect that that's an
essential ingredient to a proof.

It seems that if p== +/-1 mod 10, then your polynomial splits at least into 2
quadratics, and if p== +1 mod 10, then at least one of those quadratics splits.

This property should be easily explainable, but alas it's late and my brain's
on holiday. (I wrote this last night, but forgot to send).

> Also, I am looking for a good factorizing program.

Dario Alpern's Java ECM/QS Applet is hard to beat, and very convenient.
For tougher nuts, GMP-ECM and Jason Papadopoulos' msieve are pretty much
impossible to beat.

() ASCII ribbon campaign () Hopeless ribbon campaign
/\ against HTML mail /\ against gratuitous bloodshed

[stolen with permission from Daniel B. Cristofani]

__________________________________________________
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
http://mail.yahoo.com
• ... It can also be rewritten as: A = (((B*2-1)^2+5)^2*5-4)/16 Solving for A == 0 (modulo p), we can easily eliminate p == 2 and p == 5 directly from the
Message 3 of 23 , Mar 15, 2006
• 0 Attachment
Phil Carmody wrote:
>>
>>For any integer 'B', the value 'A' of the equation
>>A = 5B^4 -10B^3 + 20B^2 -15B +11 will have as factors only
>>integers that end in a one, excluding all others.
>
>
> Can you tell us how you discovered that polynomial?
> The discriminant is very smooth, being 5^3*11^2, and I suspect that that's an
> essential ingredient to a proof.
>

It can also be rewritten as:

A = (((B*2-1)^2+5)^2*5-4)/16

Solving for A == 0 (modulo p), we can easily eliminate p == 2
and p == 5 directly from the original expression of A. Then
you get:

(((B*2-1)^2+5)^2*5-4)/16 == 0 (modulo p)

Multiply through by 16 (permissible because we eliminated p == 2),
and rearrange slightly:

((B*2-1)^2+5)^2*5 == 4 (modulo p)

In order for this to have solutions, 5 must be a quadratic
residue modulo p, which eliminates primes p ending in 3 or 7.

All that remains is to show that this last equation has no
solutions when p is a prime ending in 9. I couldn't see any
immediate way to do that, although I'm convinced that it's
true.
• To get those creative juices flowing, here s a reminder of some *really* simple (two term) prime generating polynomials :) 6x^2 + 17 is prime from x=0 to x=16
Message 4 of 23 , Mar 15, 2006
• 0 Attachment
To get those creative juices flowing, here's a reminder of some
*really* simple (two term) prime generating polynomials :)

6x^2 + 17 is prime from x=0 to x=16

10x^2 + 19 is prime from x=0 to x=18.

2x^2 + 29 is prime from x=0 to x=28.

(notice that the coefficients in each sum to a prime :) )

Mark

--- In primenumbers@yahoogroups.com, Ed Pegg Jr <ed@...> wrote:
>
> \$250 and numerous smaller prizes will go to the best prime
generating
> polynomials, in the latest Al Zimmermann programming contest.
>
> Details at
> http://recmath.org/contest/description.php
>
> Ed Pegg Jr
>
• You know Euler s x^2 + x + 41 prime from x=0 to 40 ? or: x^2 - 79x + 1601 prime from x=0 to 79 ? Werner
Message 5 of 23 , Mar 16, 2006
• 0 Attachment
You know Euler's

x^2 + x + 41 prime from x=0 to 40 ?

or:

x^2 - 79x + 1601 prime from x=0 to 79 ?

Werner

<mark.underwood@...> wrote:
>
>
> To get those creative juices flowing, here's a reminder of some
> *really* simple (two term) prime generating polynomials :)
>
> 6x^2 + 17 is prime from x=0 to x=16
>
> 10x^2 + 19 is prime from x=0 to x=18.
>
> 2x^2 + 29 is prime from x=0 to x=28.
>
> (notice that the coefficients in each sum to a prime :) )
>
> Mark
>
>
>
> --- In primenumbers@yahoogroups.com, Ed Pegg Jr <ed@> wrote:
> >
> > \$250 and numerous smaller prizes will go to the best prime
> generating
> > polynomials, in the latest Al Zimmermann programming contest.
> >
> > Details at
> > http://recmath.org/contest/description.php
> >
> > Ed Pegg Jr
> >
>
• * You know Euler s ... Or all these previously found http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html [Non-text portions of this message have
Message 6 of 23 , Mar 16, 2006
• 0 Attachment
* You know Euler's
>
> x^2 + x + 41 prime from x=0 to 40 ?
>
> or:
>
> x^2 - 79x + 1601 prime from x=0 to 79 ?
>
> Werner

Or all these previously found

http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html

[Non-text portions of this message have been removed]
• Oh yes. I was thinking about polynomials with just two terms. Speaking of which, 2x^2 - 181 is prime from x=0 to x=28. (Not bad for being plagued with factors
Message 7 of 23 , Mar 16, 2006
• 0 Attachment
Oh yes. I was thinking about polynomials with just two terms.

Speaking of which, 2x^2 - 181 is prime from x=0 to x=28.

(Not bad for being plagued with factors of 19!)

Also, from x=0 to 1000 it is prime 525 times. (The amazing x^2+x+41
is prime 582 times.)

Mark

--- In primenumbers@yahoogroups.com, "Lelio sknet" <lelio@...> wrote:
>
>
>
> * You know Euler's
> >
> > x^2 + x + 41 prime from x=0 to 40 ?
> >
> > or:
> >
> > x^2 - 79x + 1601 prime from x=0 to 79 ?
> >
> > Werner
>
>
>
> Or all these previously found
>
> http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html
>
>
>
>
>
>
>
>
>
>
>
> [Non-text portions of this message have been removed]
>
• Oops, I meant 2x^2 - 181 is prime from x=0 to x=27.
Message 8 of 23 , Mar 16, 2006
• 0 Attachment
Oops, I meant 2x^2 - 181 is prime from x=0 to x=27.

<mark.underwood@...> wrote:
>
>
> Oh yes. I was thinking about polynomials with just two terms.
>
> Speaking of which, 2x^2 - 181 is prime from x=0 to x=28.
>
> (Not bad for being plagued with factors of 19!)
>
> Also, from x=0 to 1000 it is prime 525 times. (The amazing x^2+x+41
> is prime 582 times.)
>
>
> Mark
>
>
• ... Fine site, thanks.
Message 9 of 23 , Mar 16, 2006
• 0 Attachment
--- In primenumbers@yahoogroups.com, "Lelio sknet" <lelio@...> wrote:
>
>
>
> * You know Euler's
> >
> > x^2 + x + 41 prime from x=0 to 40 ?
> >
> > or:
> >
> > x^2 - 79x + 1601 prime from x=0 to 79 ?
> >
> > Werner
>
>
>
> Or all these previously found
>
> http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html
>
>
>
>
>
>
>
>
>
>
>
> [Non-text portions of this message have been removed]
>

Fine site, thanks.
• ... * You can submit your binomial 2 x^2 – 181 to Eric Weisstein in the site bellow. He knows about only 12 better than yours and that includes Euler and
Message 10 of 23 , Mar 16, 2006
• 0 Attachment
> Oh yes. I was thinking about polynomials with just two terms.
>
> Speaking of which, 2x^2 - 181 is prime from x=0 to x=28.
>
> Mark
>

*

You can submit your binomial 2 x^2  181 to Eric Weisstein in the site
bellow.

He knows about only 12 better than yours and that includes Euler and
Legendre.

http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html

Lélio

[Non-text portions of this message have been removed]
• Just checked the prime sequence for 2x^2 - 181 at Encylopedia of Integer Sequences and it isn t there. And a google didn t find anything. I *assumed* it has
Message 11 of 23 , Mar 17, 2006
• 0 Attachment
Just checked the prime sequence for 2x^2 - 181 at Encylopedia of
Integer Sequences and it isn't there. And a google didn't find
anything. I *assumed* it has been known for a long time...but who
knows? So maybe I will submit it to Mr. Weisstein. I wonder if there
is a site which has a more or less comprehensive listing of prime
generating polynomials.

Mark

--- In primenumbers@yahoogroups.com, "Lelio sknet" <lelio@...> wrote:
>
> > Oh yes. I was thinking about polynomials with just two terms.
> >
> > Speaking of which, 2x^2 - 181 is prime from x=0 to x=28.
> >
> > Mark
> >
>
> *
>
>
> You can submit your binomial 2 x^2  181 to Eric Weisstein in the
site
> bellow.
>
> He knows about only 12 better than yours and that includes Euler and
> Legendre.
>
>
>
> http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html
>
>
>
>
>
>
> Lélio
>
>
>
>
>
> [Non-text portions of this message have been removed]
>
• ... that that s an ... Why? ((2*B - 1)^2 + 5)^2*5 = 4 (mod p) === ((2*B - 1)^2 + 5)^2 = 4*5^(-1) (mod p) Then 4*5^(-1) must be a quadratic residue modulo p,
Message 12 of 23 , Mar 17, 2006
• 0 Attachment
--- In primenumbers@yahoogroups.com, Jack Brennen <jb@...> wrote:
>
> Phil Carmody wrote:
> >>
> >>For any integer 'B', the value 'A' of the equation
> >>A = 5B^4 -10B^3 + 20B^2 -15B +11 will have as factors only
> >>integers that end in a one, excluding all others.
> >
> >
> > Can you tell us how you discovered that polynomial?
> > The discriminant is very smooth, being 5^3*11^2, and I suspect
that that's an
> > essential ingredient to a proof.
> >
>
> It can also be rewritten as:
>
> A = (((B*2-1)^2+5)^2*5-4)/16
>
>
> Solving for A == 0 (modulo p), we can easily eliminate p == 2
> and p == 5 directly from the original expression of A. Then
> you get:
>
> (((B*2-1)^2+5)^2*5-4)/16 == 0 (modulo p)
>
> Multiply through by 16 (permissible because we eliminated p == 2),
> and rearrange slightly:
>
> ((B*2-1)^2+5)^2*5 == 4 (modulo p)
>
> In order for this to have solutions, 5 must be a quadratic
> residue modulo p, which eliminates primes p ending in 3 or 7.

Why?

((2*B - 1)^2 + 5)^2*5 = 4 (mod p) ===>

((2*B - 1)^2 + 5)^2 = 4*5^(-1) (mod p)

Then 4*5^(-1) must be a quadratic residue modulo p, no?

Best regards,

Ignacio Larrosa Cañestro
A Coruña (España)
ilarrosa@...
• ... Good question... ... To which you give the correct answer. See Riesel s appendices, or use QR. Phil () ASCII ribbon campaign () Hopeless ribbon
Message 13 of 23 , Mar 17, 2006
• 0 Attachment
--- Ignacio Larrosa Cañestro <ilarrosa@...> wrote:
> --- In primenumbers@yahoogroups.com, Jack Brennen <jb@...> wrote:
> > It can also be rewritten as:
> >
> > A = (((B*2-1)^2+5)^2*5-4)/16
> >
> >
> > Solving for A == 0 (modulo p), we can easily eliminate p == 2
> > and p == 5 directly from the original expression of A. Then
> > you get:
> >
> > (((B*2-1)^2+5)^2*5-4)/16 == 0 (modulo p)
> >
> > Multiply through by 16 (permissible because we eliminated p == 2),
> > and rearrange slightly:
> >
> > ((B*2-1)^2+5)^2*5 == 4 (modulo p)
> >
> > In order for this to have solutions, 5 must be a quadratic
> > residue modulo p, which eliminates primes p ending in 3 or 7.
>
> Why?

Good question...

> ((2*B - 1)^2 + 5)^2*5 = 4 (mod p) ===>
>
> ((2*B - 1)^2 + 5)^2 = 4*5^(-1) (mod p)
>
> Then 4*5^(-1) must be a quadratic residue modulo p, no?

To which you give the correct answer.

See Riesel's appendices, or use QR.

Phil

() ASCII ribbon campaign () Hopeless ribbon campaign
/\ against HTML mail /\ against gratuitous bloodshed

[stolen with permission from Daniel B. Cristofani]

__________________________________________________
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
http://mail.yahoo.com
• Talk about wonders never ceasing. Here s another 40 prime sequence I just stumbled across 10 minutes ago: 4x^2 -158x + 1601 is prime from x=0 to x=39, no
Message 14 of 23 , Mar 17, 2006
• 0 Attachment
Talk about wonders never ceasing. Here's another 40 prime sequence I
just stumbled across 10 minutes ago:

4x^2 -158x + 1601

is prime from x=0 to x=39, no repeats, all positive. This one has the
lovely feature of it's near symmetry: It starts at prime 1601, then
halfway at x=20 reaches a low at prime 41, then it swings back up
again to attain prime 1847 at x=39. It's four middle and lowest
primes are 53,43,41 and 47, four consecutive primes.

The sequence is bounded by
41*43 at x=-1
41*41 at x=40.
How close can you get!

Notice that the 40 prime polys thus far all have a starting
coefficient which is a square (1,4,9) :

1x^2 - x + 41
4x^2 - 158x + 1601
9x^2 - 231x + 1523

Have submitted to Mathworld. (None were in the Encyclopedia of
Integer Sequences.)

Mark

--- In primenumbers@yahoogroups.com, "Lelio sknet" <lelio@...> wrote:
>
> >BUT here's one I'd like to introduce with 40 consecutive primes,
all
> >positive and non repeating (!) :
> >
> >9x^2 -231x + 1523
> >
> >This sequence starts at prime 1523 and decreases to a low of 41
(at
> >x=13), then swings back up to finish off at prime 6203 at x=39.
> >
> >Wonders never cease!
> >
> >Mark
>
>
>
> So it is as good as Euler's
>
> Congratulations
>
> Next step you should submit it to Eric
>
> Lélio
>
>
>
>
>
>
>
>
> _____
>
>
>
> [Non-text portions of this message have been removed]
>
• ... Two other little observations : 1. 41, 1601 and 1523 are prime numbers. 2. 1 - 1 + 41 = 41, which is prime. 4 - 158 + 1601 = 1447, which is prime. 9 - 231
Message 15 of 23 , Mar 18, 2006
• 0 Attachment
<mark.underwood@...> wrote:

> Notice that the 40 prime polys thus far all have a starting
> coefficient which is a square (1,4,9) :
>
> 1x^2 - x + 41
> 4x^2 - 158x + 1601
> 9x^2 - 231x + 1523
-----------------------------------------------------------

Two other little observations :
1. 41, 1601 and 1523 are prime numbers.
2. 1 - 1 + 41 = 41, which is prime.
4 - 158 + 1601 = 1447, which is prime.
9 - 231 + 1523 = 1301, which is prime.

Regards,
Patrick Capelle.
• ... ? subst(4*x^2 -158*x + 1601,x, x/2+20) x^2 + x + 41 () ASCII ribbon campaign () Hopeless ribbon campaign / against HTML mail /
Message 16 of 23 , Mar 18, 2006
• 0 Attachment
--- Mark Underwood <mark.underwood@...> wrote:
> Talk about wonders never ceasing. Here's another 40 prime sequence I
> just stumbled across 10 minutes ago:
>
> 4x^2 -158x + 1601

? subst(4*x^2 -158*x + 1601,x, x/2+20)
x^2 + x + 41

() ASCII ribbon campaign () Hopeless ribbon campaign
/\ against HTML mail /\ against gratuitous bloodshed

[stolen with permission from Daniel B. Cristofani]

__________________________________________________
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
http://mail.yahoo.com
• ... These observations are in fact trivial. I suggested to search 40 prime polys ax^2 + bx + c such that : 1. a is a square 2. b is negative and non-prime 3. c
Message 17 of 23 , Mar 18, 2006
• 0 Attachment
> <mark.underwood@> wrote:
> Notice that the 40 prime polys thus far all have a starting
> coefficient which is a square (1,4,9) :
>
> 1x^2 - x + 41
> 4x^2 - 158x + 1601
> 9x^2 - 231x + 1523

<patrick.capelle@...> wrote:
> Two other little observations :
> 1. 41, 1601 and 1523 are prime numbers.
> 2. 1 - 1 + 41 = 41, which is prime.
> 4 - 158 + 1601 = 1447, which is prime.
> 9 - 231 + 1523 = 1301, which is prime.
>
> Regards,
> Patrick Capelle.
------------------------------------------------------------------

These observations are in fact trivial.
I suggested to search 40 prime polys ax^2 + bx + c such that :
1. a is a square
2. b is negative and non-prime
3. c is prime
4. a+b+c is prime

But for x=0, c is always prime!
And for x=1, the result a+b+c is also prime !
Hence, my first observations are trivial.

But what could be not trivial is to search 40 prime polys n^2x^2 +
(q-p-n^2)x + p, with p,q primes and p+n^2 > q.

Patrick Capelle.
• ... wrote: But what could be not trivial is to search 40 prime polys n^2x^2 + (q-p-n^2)x + p, with p,q primes and p+n^2 q. ... n = 1 :
Message 18 of 23 , Mar 18, 2006
• 0 Attachment
<patrick.capelle@...> wrote:
But what could be not trivial is to search 40 prime polys
n^2x^2 + (q-p-n^2)x + p, with p,q primes and p+n^2 > q.
---------------------------------------------------------

n = 1 : (p,q)=(41,41)
n = 2 : (p,q)=(1601,1447)
n = 3 : (p,q)=(1523,1301)

Can someone propose a solution (p,q) for n = 4 ?

Patrick Capelle.
• ... wrote: Notice that the 40 prime polys thus far all have a starting coefficient which is a square (1,4,9) : 1x^2 - x + 41 4x^2 - 158x +
Message 19 of 23 , Mar 18, 2006
• 0 Attachment
<mark.underwood@...> wrote:
Notice that the 40 prime polys thus far all have a starting
coefficient which is a square (1,4,9) :

1x^2 - x + 41
4x^2 - 158x + 1601
9x^2 - 231x + 1523

Have submitted to Mathworld. (None were in the Encyclopedia of
Integer Sequences.)
--------------------------------------------------------------

The two last polynomials were already found in 2003.
http://www.primepuzzles.net/puzzles/puzz_232.htm

Note that the substitutions are not forbidden, if the polynomials are
able to give different sets of distinct primes when x = 0 to 39.
Some of the prime numbers given by the three polynomials above are
different ...
Note also that unfortunately x^2 - x + 41 gives twice the number 41
(it's not the case with x^2 + x + 41).

Regards,
Patrick Capelle.
• We can keep Mark s idea about squares and modify the challenge. Let s start with the six polynomials of the Carlos Rivera web site (see
Message 20 of 23 , Mar 18, 2006
• 0 Attachment
We can keep Mark's idea about squares and modify the challenge.

Let's start with the six polynomials of the Carlos Rivera web site
(see http://www.primepuzzles.net/puzzles/puzz_232.htm ):
x2 + x + 41
x2 - 79x + 1601
4x2 - 154x + 1523
4x2 - 158x + 1601
9x2 - 231x + 1523
9x2 - 471x + 6203

If we are interested by the 40 prime polynomials of the form
n^2x^2 + (q-p-n^2)x + p, with p,q primes, we will find :
For n = 1 : (p,q)=(41,43)
(p,q)=(1601,1523)
For n = 2 : (p,q)=(1523,1373)
(p,q)=(1601,1447)
For n = 3 : (p,q)=(1523,1301)
(p,q)=(6203,5741)

Can you propose two solutions for n = 4 ?

Patrick Capelle.
• Wednesday, March 15, 2006 8:11 AM [GMT+1=CET], ... Thanks to Phil and Jose, I was slightly obtuse ... But, someone could tell us how to prove that it must be p
Message 21 of 23 , Mar 19, 2006
• 0 Attachment
Wednesday, March 15, 2006 8:11 AM [GMT+1=CET],
Phil Carmody <thefatphil@...> escribió:

> --- aldrich617 <aldrich617@...> wrote:
>> I am searching for a way to prove the following Theorem:
>>
>> For any integer 'B', the value 'A' of the equation
>> A = 5B^4 -10B^3 + 20B^2 -15B +11 will have as factors only
>> integers that end in a one, excluding all others.
>>
>> This seems to be true at least up to 10^18. I think that proving
>> it could give us new insights into primality testing,
>> and factoring. Moreover there are similar equations, vast in
>> number, apparently with the same property, that could then probably
>> be verified to be similar threads of pure one. Together these
>> would form an infinite interconnecting web.
>
> Can you tell us how you discovered that polynomial?
> The discriminant is very smooth, being 5^3*11^2, and I suspect that
> that's an essential ingredient to a proof.
>
> It seems that if p== +/-1 mod 10, then your polynomial splits at
> least into 2 quadratics, and if p== +1 mod 10, then at least one of
>
> This property should be easily explainable, but alas it's late and my
> brain's on holiday. (I wrote this last night, but forgot to send).

Thanks to Phil and Jose, I was slightly obtuse ...

But, someone could tell us how to prove that it must be p = 1 (mod 10)?