## Re: Prime generating polynomials contest

Expand Messages
• Here s another one: 4x^2+12x-1583 is prime from x=0 to x=34, a span of 35 unique primes increasing from -1583 to 3449. It too met its end at the hands of
Message 1 of 13 , Jan 3, 2006
• 0 Attachment
Here's another one:

4x^2+12x-1583

is prime from x=0 to x=34, a span of 35 unique primes increasing
from -1583 to 3449. It too met its end at the hands of factor 37,
which is still at large.

Mark

<mark.underwood@s...> wrote:
>
>
> Here's one that won't be a winner but is fairly long. I can't find
it
> in the Integer Sequences, so maybe it's 'new':
>
> 4x^2 - 212x + 2411
>
> Generates 27 distinct primes from x=0 (p=2411) to x=26 (p=-397)
> before doubling back. So it's prime from x=0 to x=53. It met its
end
> at the hands of a factor of 37.
>
> Mark
>
>
>
> --- In primenumbers@yahoogroups.com, ed pegg <ed@m...> wrote:
> >
> > The next Al Zimmermann Programming contest might be about
> > Prime Generating Polynomials. It's currently running neck
> > and neck with Protein Folding.
> >
> > Under the rules I'm proposing for the contest, here are the
> > current known record holders for Prime Generating Polynomials,
> > orders 1 to 4. Orders 5 and up seem to be unexplored.
> >
> > 1) 44546738095860 n + 56211383760397 Score:23 n=0..22 Frind
> > 2) 36 n^2 - 810 n + 2753 Score:45 n=0..44 Ruby
> > 3) 3 n^3 - 183 n^2 + 3318 n - 18757 Score:43 n=0..46 Ruiz
> > 4) n^4 + 29 n^2 + 101 Score:20 n=0..19 Pegg
> >
> > The scoring rules:
> > 1. Polynomial f(k) must produce primes from 0 to n.
> > 2. The score will be the number of *distinct* primes
> > when |f(k)| is evaluated from 0 to n.
> > 3. In case of a tie, the lower value (tighter value) of n wins.
> > 4. In case of a tie, the product of non-zero coefficients will
> > be evaluated, and the lowest product wins.
> >
> > My own result for order-4 polynomials will likely be surpassed
> > very easily. If you would like to vote for this contest, please
> > visit http://www.recmath.com/contest/ . The winners will split
> > up \$500.
> >
> > Ed Pegg Jr
> >
>
• 36 x^2 - 666 x + 1277 is prime from x = 0 to x = 42 . (different values) Note the use of the well known numbers 666 and 42 . JT 0 1277 1 647 2
Message 2 of 13 , Jan 4, 2006
• 0 Attachment
36 x^2 - 666 x + 1277 is prime from x = 0 to x = 42 . (different values)

Note the use of the well known numbers '666' and '42' .

JT

0 1277
1 647
2 89
3 -397
4 -811
5 -1153
6 -1423
7 -1621
8 -1747
9 -1801
10 -1783
11 -1693
12 -1531
13 -1297
14 -991
15 -613
16 -163
17 359
18 953
19 1619
20 2357
21 3167
22 4049
23 5003
24 6029
25 7127
26 8297
27 9539
28 10853
29 12239
30 13697
31 15227
32 16829
33 18503
34 20249
35 22067
36 23957
37 25919
38 27953
39 30059
40 32237
41 34487
42 36809
43 197*199

------------------------------------
http://www.echolalie.com
• ... values) ... What a beastly formula, Jacques! It is actually prime from x=-2 to 42, making 45 distinct prime values! For x=0 to x=44 your formula would
Message 3 of 13 , Jan 6, 2006
• 0 Attachment
<jacques.tramu@e...> wrote:
>
> 36 x^2 - 666 x + 1277 is prime from x = 0 to x = 42 . (different
values)
>
> Note the use of the well known numbers '666' and '42' .
>(snip)
> JT

What a 'beastly' formula, Jacques! It is actually prime from x=-2 to
42, making 45 distinct prime values! For x=0 to x=44 your formula
would become

36x^2 - 810 + 2753

which would not make the devil happy ;) Incredibly your expression
never yields prime factors below 59.

Mark
• Thx Mark. Halas, after checking http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html I found, and you can see that 36x^2 - 810 + 2753 is an already
Message 4 of 13 , Jan 6, 2006
• 0 Attachment
Thx Mark.

Halas, after checking
http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html

I found, and you can see that
36x^2 - 810 + 2753 is an already known record (Fung and Ruby)

(Sloane sequence : A060268)

So, it appears that I discovered the '666' version of it , without knowing
A060268.
Sorry,
Jacques.

----- Original Message -----
From: "Mark Underwood" <mark.underwood@...>
"
> <jacques.tramu@e...> wrote:
>>
>> 36 x^2 - 666 x + 1277 is prime from x = 0 to x = 42 . (different
> values)
>>
> What a 'beastly' formula, Jacques! It is actually prime from x=-2 to
> 42, making 45 distinct prime values! For x=0 to x=44 your formula
> would become
>
> 36x^2 - 810 + 2753
>
> which would not make the devil happy ;) Incredibly your expression
> never yields prime factors below 59.
>
> Mark
>
------------------------------------
http://www.echolalie.com
• ... A quadratic expression that yields no prime factors less than a given value is easy to generate arbitrarily. Start with any integer valued f(x)=ax^2+bx+c
Message 5 of 13 , Jan 6, 2006
• 0 Attachment
<mark.underwood@s...> wrote:

> which would not make the devil happy ;) Incredibly your expression
> never yields prime factors below 59.

A quadratic expression that yields no prime factors less than a given
value is easy to generate arbitrarily.

common factor. Let's say f(d) is odd and f(d+1) is even, then take
the three seed values f(d), f(d+2),f(d+4) and solve for the
coefficients of the new quadratic, f'(x) (you have 3 eqs, 3 unknowns,
so this can always be done).

If 3 appears as a factor of f'(x), only 2 of 3 consecutive solutions
of f'(x) can possibly be divisible by 3. Choose one that is not, say
it is f'(e), then take 3 consecutive values f'(e),f'(e+3),f'(e+6) and
solve for the quadratic f''(x). Continue as high as you please. Any
prime factor q, will appear at most twice within q consecutive values
of the quadratic progression, so there are always at least q-2
"paralell" quadratic progressions where q cannot be a divisor of the

-Dick Boland
• ... Here s another approach that yields the same result more directly, but causes the quadratic to grow large more quickly. Choose your threshold prime, say
Message 6 of 13 , Jan 6, 2006
• 0 Attachment
--- In primenumbers@yahoogroups.com, "Dick" <richard042@y...> wrote:
> A quadratic expression that yields no prime factors less than a given
> value is easy to generate arbitrarily.

Here's another approach that yields the same result more directly, but
causes the quadratic to grow large more quickly. Choose your
threshold prime, say p(a), then take any three integers, t,u,v where
each is co-prime to all primes<p(a+1), for example t=p(a+1), u=p(a+2),
v=p(a+3) then solve for the coefficients of quadratic f(x) given by 3
seed values f(0)=t, f(1)=u, f(2)=v. Now solve for the quadratic f'(x)
given by 3 seed values f(a#),f(2a#),f(3a#). f'(x) will then have no
prime divisors <p(a+1).

-Dick Boland
• ... Of course, it would only be necessary that t have no prime divisors
Message 7 of 13 , Jan 6, 2006
• 0 Attachment
--- In primenumbers@yahoogroups.com, "Dick" <richard042@y...> wrote:
> --- In primenumbers@yahoogroups.com, "Dick" <richard042@y...> wrote:

> threshold prime, say p(a), then take any three integers, t,u,v where
> each is co-prime to all primes<p(a+1), for example t=p(a+1), u=p(a+2),
> v=p(a+3) then solve for the coefficients of quadratic f(x) given by 3
> seed values f(0)=t, f(1)=u, f(2)=v. Now solve for the quadratic f'(x)
> given by 3 seed values f(a#),f(2a#),f(3a#). f'(x) will then have no
> prime divisors <p(a+1).

Of course, it would only be necessary that t have no prime
divisors<p(a+1) in order for f'(x) to also have this property.

-Dick Boland
• ... No probs Jacques. I did a retake of Ed Pegg s post which originated this thread, and there was Ruby s expression! But a guru has just informed me that
Message 8 of 13 , Jan 6, 2006
• 0 Attachment
<jacques.tramu@e...> wrote:
>
> Thx Mark.
>
> Halas, after checking
> http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html
>
> I found, and you can see that
> 36x^2 - 810 + 2753 is an already known record (Fung and Ruby)
>
> (Sloane sequence : A060268)

No probs Jacques. I did a retake of Ed Pegg's post which originated
this thread, and there was Ruby's expression!

But a guru has just informed me that Ruby's expression is no longer a
record - it now might be held by Dror Speiser who has 46 different
primes in the expression

103x^2 - 4707x + 50383

from x=0 to x=45. (!) See
http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0506&L=NMBRTHRY&P=R260

This expression as well as Ruby's generates no prime factors below 59.

I just stumbled across one that has no prime factors below 61 :
x^2 - 479x +3851
but it generates only 21 consecutive primes.

Mark
• It appears there has been a retraction and the expression 103x^2 - 4707x + 50383 is prime for only 43 primes. It is apparently tied for second place to
Message 9 of 13 , Jan 6, 2006
• 0 Attachment
It appears there has been a retraction and the expression
103x^2 - 4707x + 50383
is prime for only 43 primes. It is apparently tied for second
place to
47x^2-1701x+10181,
yet another one discovered by Ruby and Fung.

It's nice to see that I'm not the only one who can look at data and
miss what I don't want to see (ie, a composite). ;)

Mark

<mark.underwood@s...> wrote:
>
> --- In primenumbers@yahoogroups.com, "Jacques Tramu"
> <jacques.tramu@e...> wrote:
> >
> > Thx Mark.
> >
> > Halas, after checking
> > http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html
> >
> > I found, and you can see that
> > 36x^2 - 810 + 2753 is an already known record (Fung and Ruby)
> >
> > (Sloane sequence : A060268)
>
> No probs Jacques. I did a retake of Ed Pegg's post which originated
> this thread, and there was Ruby's expression!
>
> But a guru has just informed me that Ruby's expression is no longer
a
> record - it now might be held by Dror Speiser who has 46 different
> primes in the expression
>
> 103x^2 - 4707x + 50383
>
> from x=0 to x=45. (!) See
> http://listserv.nodak.edu/cgi-bin/wa.exe?
A2=ind0506&L=NMBRTHRY&P=R260
>
> This expression as well as Ruby's generates no prime factors below
59.
>
> I just stumbled across one that has no prime factors below 61 :
> x^2 - 479x +3851
> but it generates only 21 consecutive primes.
>
> Mark
>
• ... Yes. Here is PARI/GP code: f(n)=local(c,p,i,r);c=1;r=2;forprime(p=3,n,i=1; while(issquare(Mod(i,p)),i++);c+=lift((Mod(1-i,p)/4-c)/r)*r;r*=p);c x^2+x+f(n)
Message 10 of 13 , Jan 6, 2006
• 0 Attachment
Dick wrote:

> A quadratic expression that yields no prime factors less than a given
> value is easy to generate arbitrarily.

Yes. Here is PARI/GP code:

f(n)=local(c,p,i,r);c=1;r=2;forprime(p=3,n,i=1;
while(issquare(Mod(i,p)),i++);c+=lift((Mod(1-i,p)/4-c)/r)*r;r*=p);c

x^2+x+f(n) never has a factor <= n.
f(n) is a little below n# (which is near e^n).
f(277) has 113 digits:
52211040781253690937101509813868236062339335365181118768\
264647548098518281973426206257327260311399656484832821211

f(100000) is computed in 2 seconds and has 43293 digits.
It is far harder to find the smallest constants to avoid
all small factors in x^2+x+A.
http://www.primepuzzles.net/conjectures/conj_017.htm lists that.
The record is A=2457080965043150051 which gives 281 as smallest factor.

--
Jens Kruse Andersen
Your message has been successfully submitted and would be delivered to recipients shortly.