## 15004-digit AP4

Expand Messages
• Here is a new AP4 record at 15004 digits:- (1000362700+2571033*n)*34687#+1 is prime for n=0..3 All confirmed prime with PFGW -tc Input/output statistics:-
Message 1 of 11 , Jul 28, 2010
Here is a new AP4 record at 15004 digits:-

(1000362700+2571033*n)*34687#+1 is prime for n=0..3

All confirmed prime with PFGW -tc

Input/output statistics:-
Numbers tested by NewPGen: 10^7
NewPGen reduced these (by sieving to 1.8T) to: 3.7*10^6
Numbers tested by PFGW: 1.3*10^6
PRP's found by PFGW: 2051
AP3's found: 661
AP4's found: 0

One AP4 was found by extending all the AP3's upwards.

Run-time statistics:-
NewPGen: 56.5 GHz-days
PFGW: 457 GHz-days
Pascal program to find AP's: < 1 sec

Since the main bottleneck is the PFGW run, the Pascal program was run periodically to see what AP3's turned up, these being then extended upwards to look for an AP4.

A week ago, I tried a new trick (influenced by some of Ken's reported procedures):-
as about 1/3 of the NewPGen range had been PFGW'd, with 1805 PRPs found, I wrote a program to look through the 0.5*1805^2 AP2's and output the succeding AP3 term provided that both it and the following (AP4) term were in the not-yet processed region of the NewPGen-filtered candidates (and so each was about 3 times more likely than usual to be a PRP).

This gave 105,612 candidates, which took PFGW only about a week to process, yielding 162 new PRPs, each of which was guaranteed, by construction, to produce at least one new AP3. When these PRPs were added to those already found, the number of AP3's jumped from 429 to 661, a relatively huge increase for just one week's processing.

The trick (which could have been periodically repeated of course) paid off first time.
I offer it FOC to my competitors!

-Mike Oakes
• ... Congratulations on your heavy hash consumption :-) David (looking for a bigger AP4 in a hash-free zone)
Message 2 of 11 , Jul 28, 2010
--- In primeform@yahoogroups.com,
"mikeoakes2" <mikeoakes2@...> wrote:

> Here is a new AP4 record at 15004 digits:-
> (1000362700+2571033*n)*34687#+1 is prime for n=0..3

Congratulations on your heavy hash consumption :-)

David (looking for a bigger AP4 in a hash-free zone)
• ... Congratulations! http://users.cybercity.dk/~dsl522332/math/aprecords.htm is updated. -- Jens Kruse Andersen
Message 3 of 11 , Jul 28, 2010
Mike Oakes wrote:
> Here is a new AP4 record at 15004 digits:-
>
> (1000362700+2571033*n)*34687#+1 is prime for n=0..3

Congratulations!
http://users.cybercity.dk/~dsl522332/math/aprecords.htm is updated.

--
Jens Kruse Andersen
• Congratulations Mike ... I assume you extended them downwards as well ... your welcome ... Where pfgw is the limiting factor I ve been known to perform some
Message 4 of 11 , Jul 28, 2010
Congratulations Mike
--- In primeform@yahoogroups.com, "mikeoakes2" <mikeoakes2@...> wrote:
>
> Here is a new AP4 record at 15004 digits:-
>
> (1000362700+2571033*n)*34687#+1 is prime for n=0..3
>
> All confirmed prime with PFGW -tc
>
> Input/output statistics:-
> Numbers tested by NewPGen: 10^7
> NewPGen reduced these (by sieving to 1.8T) to: 3.7*10^6
> Numbers tested by PFGW: 1.3*10^6
> PRP's found by PFGW: 2051
> AP3's found: 661
> AP4's found: 0
>
> One AP4 was found by extending all the AP3's upwards.
I assume you extended them downwards as well
>
> Run-time statistics:-
> NewPGen: 56.5 GHz-days
> PFGW: 457 GHz-days
> Pascal program to find AP's: < 1 sec
>
> Since the main bottleneck is the PFGW run, the Pascal program was run periodically to see what AP3's turned up, these being then extended upwards to look for an AP4.
>
> A week ago, I tried a new trick (influenced by some of Ken's reported procedures):-
> as about 1/3 of the NewPGen range had been PFGW'd, with 1805 PRPs found, I wrote a program to look through the 0.5*1805^2 AP2's and output the succeeding AP3 term provided that both it and the following (AP4) term were in the not-yet processed region of the NewPGen-filtered candidates (and so each was about 3 times more likely than usual to be a PRP).
Where pfgw is the limiting factor I've been known to perform some rather bizarre processes.
Once I have a reasonable number of actual prps I output all candidates that produce aps of interest (ap4s in this case) extended both up and down from a smaller length (ap2 in this case).
I then run newpgen against these numbers
Next I run an ap search again across the range of whatever prps I have but including the sieved values below and above
This time I only look for (potential) aps of the desired length.
I then pfgw those values which have not yet been done hoping to get a real ap.
>
> This gave 105,612 candidates, which took PFGW only about a week to process, yielding 162 new PRPs, each of which was guaranteed, by construction, to produce at least one new AP3. When these PRPs were added to those already found, the number of AP3's jumped from 429 to 661, a relatively huge increase for just one week's processing.
>
> The trick (which could have been periodically repeated of course) paid off first time.
> I offer it FOC to my competitors!
I tend to think of us more as collaborators in extending human knowledge ;-)
>
> -Mike Oakes
• ... How do you organise this, Ken? As I see it, NewPGen is only useful for ranges, not individual candidates. Mike
Message 5 of 11 , Jul 29, 2010
>
> Where pfgw is the limiting factor I've been known to perform some rather bizarre processes.
> Once I have a reasonable number of actual prps I output all candidates that produce aps of interest (ap4s in this case) extended both up and down from a smaller length (ap2 in this case).
> I then run newpgen against these numbers

How do you organise this, Ken?
As I see it, NewPGen is only useful for ranges, not individual candidates.

Mike
• ... Its fiddley involving multiple steps. Roughly In this case I would proceed as follows Output the candidates and differences of the potential ap3s in a
Message 6 of 11 , Jul 29, 2010
--- In primeform@yahoogroups.com, "mikeoakes2" <mikeoakes2@...> wrote:
>
>
>
> >
> > Where pfgw is the limiting factor I've been known to perform some rather bizarre processes.
> > Once I have a reasonable number of actual prps I output all candidates that produce aps of interest (ap4s in this case) extended both up and down from a smaller length (ap2 in this case).
> > I then run newpgen against these numbers
>
> How do you organise this, Ken?
> As I see it, NewPGen is only useful for ranges, not individual candidates.
Its fiddley involving multiple steps.
Roughly In this case I would proceed as follows
Output the candidates and differences of the potential ap3s in a format suitable for newpgen
After a suitable level of newpgenning I take the output, match it against the original file (with differences) to produce a second newpgen file which will now contain the potential candidates that would give the ap4s (repeat if you are after ap5s)
After newpgenning I'd end up with a file containing lots of potential ap4s (where 2 are known prps).
I then run a pfgw script which tests one of the potential prps (testing the second if the first is a prp)
The multiple newpgenning greatly reduces the candidates.
unfortunately my current (main) search is limited by my c programs ability to find aps
cheers
Ken
>
> Mike
>
• Hi Mike (and anyone else who may be interested), For your consideration. Also note that for the AP4 case each Ap2 gives you 3 chances at an Ap4. My original
Message 7 of 11 , Jul 31, 2010
Hi Mike (and anyone else who may be interested),
Also note that for the AP4 case each Ap2 gives you 3 chances at an Ap4.
My original post only deals with the up and down ap4s.
The 'spanned' chances can be got at via newpgen also.
Extend all ap2s up and down
output 2 files
one containing data suitable for newpgen
the other a csv containing the n value and the difference
run newpgen against the candidates
match the remaining candidates against the csv file.
sort the result via difference then n value (ascending)
extract first n values, of pairs of equal difference where second n value = first n value + 3*difference
output a file containing
first nvalue
difference
run pfgw script against file
if nvalue is prp then test n value +3*difference
if this is a prp then you have an ap4 of prps to prime test.
cheers
Ken

>
>
>
> --- In primeform@yahoogroups.com, "mikeoakes2" <mikeoakes2@> wrote:
> >
> >
> >
> > >
> > > Where pfgw is the limiting factor I've been known to perform some rather bizarre processes.
> > > Once I have a reasonable number of actual prps I output all candidates that produce aps of interest (ap4s in this case) extended both up and down from a smaller length (ap2 in this case).
> > > I then run newpgen against these numbers
> >
> > How do you organise this, Ken?
> > As I see it, NewPGen is only useful for ranges, not individual candidates.
> Its fiddley involving multiple steps.
> Roughly In this case I would proceed as follows
> Output the candidates and differences of the potential ap3s in a format suitable for newpgen
> After a suitable level of newpgenning I take the output, match it against the original file (with differences) to produce a second newpgen file which will now contain the potential candidates that would give the ap4s (repeat if you are after ap5s)
> After newpgenning I'd end up with a file containing lots of potential ap4s (where 2 are known prps).
> I then run a pfgw script which tests one of the potential prps (testing the second if the first is a prp)
> The multiple newpgenning greatly reduces the candidates.
> unfortunately my current (main) search is limited by my c programs ability to find aps
> cheers
> Ken
> >
> > Mike
> >
>
• ... Here, eventually, is my reply: Calling Brillhart-Lehmer-Selfridge with factored part 31.24% 3*164196977*2^80000-1631979959*2^25001-1 is Lucas PRP!
Message 8 of 11 , Oct 24, 2010
--- In primeform@yahoogroups.com,
"mikeoakes2" <mikeoakes2@...> wrote:

> Here is a new AP4 record at 15004 digits:-
> (1000362700+2571033*n)*34687#+1 is prime for n=0..3

Calling Brillhart-Lehmer-Selfridge with factored part 31.24%
3*164196977*2^80000-1631979959*2^25001-1 is Lucas PRP! (103.0930s+0.0038s)

Calling Brillhart-Lehmer-Selfridge with factored part 31.40%
164196977*2^80001-1631979959*2^25000-1 is Lucas PRP! (99.0570s+0.0044s)

Calling Brillhart-Lehmer-Selfridge with factored part 99.97%
164196977*2^80000-1 is prime! (30.1911s+0.0057s)

Calling Brillhart-Lehmer-Selfridge with factored part 99.88%
1631979959*2^25000-1 is prime! (2.4893s+0.0047s)

The two largest elements of this AP4, with 24092 and 24091 digits,
were proven prime using the method of Konyagin and Pomerance.

• ... Congratulations on a large record improvement. http://users.cybercity.dk/~dsl522332/math/aprecords.htm is updated. -- Jens Kruse Andersen
Message 9 of 11 , Oct 25, 2010
> 3*164196977*2^80000-1631979959*2^25001-1 is Lucas PRP!
> 164196977*2^80001-1631979959*2^25000-1 is Lucas PRP!
> 164196977*2^80000-1 is prime!
> 1631979959*2^25000-1 is prime!
>
> The two largest elements of this AP4, with 24092 and 24091 digits,
> were proven prime using the method of Konyagin and Pomerance.

Congratulations on a large record improvement.
http://users.cybercity.dk/~dsl522332/math/aprecords.htm is updated.

--
Jens Kruse Andersen
• ... David Many congratulations on your big new record. You don t say what effort was involved. For comparison, I ve checked what numbers my hash technology
Message 10 of 11 , Oct 30, 2010
>
> --- In primeform@yahoogroups.com,
> "mikeoakes2" <mikeoakes2@> wrote:
>
> > Here is a new AP4 record at 15004 digits:-
> > (1000362700+2571033*n)*34687#+1 is prime for n=0..3
>
> Here, eventually, is my reply:
>
> Calling Brillhart-Lehmer-Selfridge with factored part 31.24%
> 3*164196977*2^80000-1631979959*2^25001-1 is Lucas PRP! (103.0930s+0.0038s)
>
> Calling Brillhart-Lehmer-Selfridge with factored part 31.40%
> 164196977*2^80001-1631979959*2^25000-1 is Lucas PRP! (99.0570s+0.0044s)
>
> Calling Brillhart-Lehmer-Selfridge with factored part 99.97%
> 164196977*2^80000-1 is prime! (30.1911s+0.0057s)
>
> Calling Brillhart-Lehmer-Selfridge with factored part 99.88%
> 1631979959*2^25000-1 is prime! (2.4893s+0.0047s)
>
> The two largest elements of this AP4, with 24092 and 24091 digits,
> were proven prime using the method of Konyagin and Pomerance.

David
Many congratulations on your big new record.

You don't say what effort was involved.
For comparison, I've checked what numbers my "hash" technology would require for a record of this size, for a "vanilla" detection algorithm, i.e. without any Ken-type extension tricks.

k=4 q=55793
M1=19890161. M2=39780323.
digits: 24094.885
score=80.718039
PRP'ing: 15.818496 GHz-yrs (100.00000%)
APk-detection: 0.000000012682880 GHz-yrs (0.000000080177533%)
Total: 15.818496 GHz-yrs
APk counts:-
k=1 c=6980.6133
k=2 c=24364481.
k=3 c=4275.4493
k=4 c=1.0003326
k=5 c=0.00026330492

Here is the output from the same program for your AP3 record:-

k=3 q=367453
M1=4077056.1 M2=8154112.1 c=1.0000511
digits: 159381.72
score=83.853401
PRP'ing: 163.82127 GHz-yrs (100.00000%)
APk-detection: 2.2318013 E-11 GHz-yrs (1.3623391 E-11%)
Total: 163.82127 GHz-yrs
APk counts:-
k=1 c=253.59636
k=2 c=32155.557
k=3 c=1.0000511
k=4 c=0.000041469329

I wonder how those PRP'ing estimates compare with your actual figures, and in particular, whether the AP3 record was about 10 times as burdensome? (It has a considerably higher "score".)

Mike
• ... I estimated the time for a Poisson mean of 1.0 at about half of that, but I m not telling just how unlucky I was, in fact :-( Please note that the cost of
Message 11 of 11 , Oct 30, 2010
--- In primeform@yahoogroups.com,
"mikeoakes2" <mikeoakes2@...> wrote:

> For comparison, I've checked what numbers my "hash"
> technology would require for a record of this size,
> for a "vanilla" detection algorithm
> Total: 15.818496 GHz-yrs

I estimated the time for a Poisson mean of 1.0
at about half of that, but I'm not telling
just how unlucky I was, in fact :-(

Please note that the cost of my big database of 25000-bit
over several previous records, one going back to 2005:
http://primes.utm.edu/primes/page.php?id=73546
The key to my method was to recycle primes with only
31% of the digits of the largest member of the new AP4.
You can work out, from past CHG performance, how much
higher this recycling might take one :-)

> whether the AP3 record was about 10 times as burdensome?

Not for me, since here I merely stole the all the AP2s from
the public database :-)

David
Your message has been successfully submitted and would be delivered to recipients shortly.