Prime numbers and primality testing is a Restricted Group with 1114 members.
 Prime numbers and primality testing

 Restricted Group,
 1114 members
Primary Navigation
Prime Generating Polynomial contest
Expand Messages
 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 0 Attachment
 aldrich617 <aldrich617@...> wrote:> I am searching for a way to prove the following Theorem:
Can you tell us how you discovered that polynomial?
>
> 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.
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, GMPECM 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 0 Attachment
Phil Carmody wrote:>>
It can also be rewritten as:
>>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.
>
A = (((B*21)^2+5)^2*54)/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*21)^2+5)^2*54)/16 == 0 (modulo p)
Multiply through by 16 (permissible because we eliminated p == 2),
and rearrange slightly:
((B*21)^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. 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
> 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
 In primenumbers@yahoogroups.com, "Mark Underwood"
<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
> >
> 0 Attachment
* You know Euler's>
Or all these previously found
> x^2 + x + 41 prime from x=0 to 40 ?
>
> or:
>
> x^2  79x + 1601 prime from x=0 to 79 ?
>
> Werner
http://mathworld.wolfram.com/PrimeGeneratingPolynomial.html
[Nontext portions of this message have been removed] 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/PrimeGeneratingPolynomial.html
>
>
>
>
>
>
>
>
>
>
>
> [Nontext portions of this message have been removed]
> 0 Attachment
Oops, I meant 2x^2  181 is prime from x=0 to x=27.
 In primenumbers@yahoogroups.com, "Mark Underwood"
<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
>
> 0 Attachment
 In primenumbers@yahoogroups.com, "Lelio sknet" <lelio@...> wrote:>
Fine site, thanks.
>
>
> * 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/PrimeGeneratingPolynomial.html
>
>
>
>
>
>
>
>
>
>
>
> [Nontext portions of this message have been removed]
>
 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/PrimeGeneratingPolynomial.html
Lélio
[Nontext portions of this message have been removed] 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/PrimeGeneratingPolynomial.html
>
>
>
>
>
>
> Lélio
>
>
>
>
>
> [Nontext portions of this message have been removed]
> 0 Attachment
 In primenumbers@yahoogroups.com, Jack Brennen <jb@...> wrote:>
that that's an
> 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
> > essential ingredient to a proof.
Why?
> >
>
> It can also be rewritten as:
>
> A = (((B*21)^2+5)^2*54)/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*21)^2+5)^2*54)/16 == 0 (modulo p)
>
> Multiply through by 16 (permissible because we eliminated p == 2),
> and rearrange slightly:
>
> ((B*21)^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.
((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@... 0 Attachment
 Ignacio Larrosa Cañestro <ilarrosa@...> wrote:>  In primenumbers@yahoogroups.com, Jack Brennen <jb@...> wrote:
Good question...
> > It can also be rewritten as:
> >
> > A = (((B*21)^2+5)^2*54)/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*21)^2+5)^2*54)/16 == 0 (modulo p)
> >
> > Multiply through by 16 (permissible because we eliminated p == 2),
> > and rearrange slightly:
> >
> > ((B*21)^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) ===>
To which you give the correct answer.
>
> ((2*B  1)^2 + 5)^2 = 4*5^(1) (mod p)
>
> Then 4*5^(1) must be a quadratic residue modulo p, no?
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 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
>
>
>
>
>
>
>
>
> _____
>
>
>
> [Nontext portions of this message have been removed]
> 0 Attachment
 In primenumbers@yahoogroups.com, "Mark Underwood"
<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. 0 Attachment
 Mark Underwood <mark.underwood@...> wrote:> Talk about wonders never ceasing. Here's another 40 prime sequence I
? subst(4*x^2 158*x + 1601,x, x/2+20)
> just stumbled across 10 minutes ago:
>
> 4x^2 158x + 1601
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 0 Attachment
 In primenumbers@yahoogroups.com, "Mark Underwood"> <mark.underwood@> wrote:
 In primenumbers@yahoogroups.com, "Patrick Capelle"
> 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 nonprime
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 +
(qpn^2)x + p, with p,q primes and p+n^2 > q.
Patrick Capelle. 0 Attachment
 In primenumbers@yahoogroups.com, "Patrick Capelle"
<patrick.capelle@...> wrote:
But what could be not trivial is to search 40 prime polys
n^2x^2 + (qpn^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. 0 Attachment
 In primenumbers@yahoogroups.com, "Mark Underwood"
<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.
More informations here :
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. 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 + (qpn^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. 0 Attachment
Wednesday, March 15, 2006 8:11 AM [GMT+1=CET],
Phil Carmody <thefatphil@...> escribió:
>  aldrich617 <aldrich617@...> wrote:
Thanks to Phil and Jose, I was slightly obtuse ...
>> 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).
But, someone could tell us how to prove that it must be p = 1 (mod 10)?
Thanks in advance,
Ignacio Larrosa Cañestro
A Coruña (España)
ilarrosa@...
Your message has been successfully submitted and would be delivered to recipients shortly.