Exponential prime search

[grandpascorpion]

Thanks. I used quadratic curve fitting based on sets of 4 primes. I did a brute force search of primes in ascending order through 1000.

10-sequence found with: a=1/140, b=-104/35, c=85859/140

Rational Length=10: 173,313,383,523,1013,4933,159773,181864513,236247324522683
398662845314482982048429773

As you can see, this one sequence grows quite slowly due to the small a.

I found a few more integral solutions of length 7 but no 8's yet.

[Citrix]

Originally Posted by grandpascorpion

Thanks. I used quadratic curve fitting based on sets of 4 primes. I did a brute force search of primes in ascending order through 1000.

10-sequence found with: a=1/140, b=-104/35, c=85859/140

Rational Length=10: 173,313,383,523,1013,4933,159773,181864513,236247324522683
398662845314482982048429773

As you can see, this one sequence grows quite slowly due to the small a.

I found a few more integral solutions of length 7 but no 8's yet.

Interesting idea. Im trying to read up on quadratic curve fitting, I have never heard of it before.

Citrix

[grandpascorpion]

Actually, it's just a set of simultaneous equations in 3 variables (you are solving for the coefficients of the quadratic: a, b, and c). You probably did that in algebra II class (or similar) in high school. So, this way you can fit the curve to the first 4 primes in your sequence. I have to think of a way to make a more efficient choice (sieve?) of the four primes.

So, (depend on the primes you pick), you could get a sequence of N primes if you can fit a curve to a polynomial of N-2. But there wouldn't be much point to that. It would be relatively difficult to find additional terms in the sequence, because the function would grow so much faster than a quadratic.

It might be worthwhile check cubic curve fitting but again they grow faster than quadratics.

[Jens K Andersen]

a=1, b=9598, c=-553430002
Gives 9 primes from 19211. I found hundreds of 8's with integer coefficients.

[grandpascorpion]

Any insight would be much appreciated.

[Jens K Andersen]

I used a C program calling the GMP library for prp testing.
I didn't bother to write a sieve although that's usually my specialty.
It was pretty brute force instead and took 12 hours at 1.33 GHz.

I chose a=1 in all cases. p1 is the first prime. p2 is the second.
For small known prime pairs (p1,p2) with p1<p2, I tried b from 0 to p1. I stopped at p1 to limit the size of the numbers.
c was then chosen to satisfy p2 = p1^2 + b*p1 + c.
I used a precomputed bitmap of primes below 10^9 to quickly look up whether p3 happened to be prime.
If it was then I prp tested p4 and so on until a composite was found.

Here are a few of the cases with 8 primes (I haven't checked them):

p1 p2 b c
---- ----- --- --------
1289 10267 702 -2556132
1381 11197 1312 -3707836
2707 19477 1226 -10627154
2753 18443 1065 -10492511
2789 17123 773 -9917295
3019 13099 1471 -13542211
3061 21737 2199 -16079123
3163 18059 2198 -16938784
3319 17137 44 -11144660
3389 10529 1878 -17839334
3499 10939 2266 -20160796
3623 12907 3474 -25699524
3673 13187 3506 -26355280
3793 17093 2081 -22262989
4021 10949 3266 -29290078
4099 16831 3445 -30906025
4129 19403 2409 -26975999
4283 21191 1778 -25938072
4373 12149 2556 -30288368
4409 13807 3353 -34208851

This gave 9 primes:
19211 19697 9598 -553430002
The prp's were proved with the GMP library.

I found tens of thousands with 7 primes.

[grandpascorpion]

Thanks Jens. I have to start using GMP. Based on how quickly you came up with these results, my PARI script must be hundreds of times slower.

[grandpascorpion]

In the meantime, I have been checking for primality rather than pseudo-primality. It makes a lot more sense performance-wise to check for pseudoprimes and then to check primality if you have a long enough sequence.

[grandpascorpion]

I found a much better method albeit still with PARI.

Using 3 consecutive primes, p1,p2,p3, fit a quadratic curve to those 3 plus a p4 < 2*p3. Since they are so close, you are more likely to find a quadratic with integer coefficients:

I found numerous 8-sequences (psuedo-primes anyways) and
I found a sequence of 9 from a curve fitted to 301753,301759,301789 and 304099

with a=2, b=-1207019, c=182112160048

These have been verified prime. The last number in the sequence above is only 117 digits.

[grandpascorpion]

I modified my PARI code to search only for integral solutions by picking three primes (call them p1, p2 and p3) such that p2 -p1 < 150 and p3-p2 < 500.

It's possible at this step to weed out many prime trios because they can not produce an integral "a" in a fitted quadratic curve.

If that stage is passed, we then step through values of a fourth number (call it n4) to coax an integral "a" coefficient in the quadratic. For numbers in this range, I'm checking for 1<=a<=1000. If n4 is not a prime, we skip to the next a.

Incidentally, the increment for n4 is: - determinant ([p1*p1, p1, 1], [p2*p2, p2, 1], [p3*p3, p3, 1])/(p2-p1). This could definitely be made more efficient too.

The determinant comes from Cramer's rule for simultaneous equations.

Anyways, here's the 10 sequence:

For f(0) = 1110521, f(x+1) = 123*f(x)^2 - 273188214*f(x) + 151690652062774,

there's a sequence of 10 primes:

1110521
,
1110523
,
1110919
,
20575111
,
46601041522586503
,
267113819719018404164952034722575239
,
8776024500240764626064775870716136905341939293166364446665954421585605511
,
94732885415456179892482716760249436029192875488074811514416110177309669373
92425291682366874591314317539209437548632902013727921655196512484162663303
,
11038413082339678742545658840838856049341594386599717750157950650334741940
38769025358889561508083079724087819936963215237732260339416520595733397335530363
89176019442219800506828499549555512160578454712610829192869739545311998976200455
28245602513600142402416171746987496375165513769808514876995138439
,
14987127295293235374812946333352947977094388256771554321323922612297207722
13541683562586039322395062731155640266056133808830068696301189378789695809407311
64533680855056404179477947846363365345373850728326993799197912891745371955269216
31668953636982877455636742744320549676548830266068639320129878517602791869497221
50886945477742567694082312973707667127719855493208941104089378605519875394181003
58633872667642385189414897209921793504196066736702478830988249928962332843419042
21000983002597247024229450779845967441030119464304989017920422982128315125056905
066220639386769164550638430854349949187781511

(The last one is 599 digits and had to be verified by Primo. The others were verified in PARI)

I have found another 60-odd sequences of length 9, but none of them have a smaller final term than the one I found in the previous post.

[Jens K Andersen]

Nice 10 sequence.