2^9092392+40291 is a probable prime!
 

Well guys it was nice while it lasted. Pending on more rigorous testing by Phil, we have BUSTED nummer funf.

I thought I might post this prior to more verification to let others go on to other projects on their queue.:smile:

:lock:

Nice! Congrats engracio! :bow:

Just for grins I am double-checking this (I am sure several others will be as well.) It should be done by early Wednesday afternoon.

Hopefully not everyone will switch over to other projects - we'll need help with the double-check effort now!

Awesome. Congrats to Phil and all contributors.

I'll try to get a few factors out of 2^9092392+40290 so we can make a somewhat stronger PRP test.

[CODE]
[Wed Feb 09 16:18:52 2011]
ECM found a factor in curve #1, stage #1
Sigma=7978179970243502, B1=1000, B2=100000.
UID: firejuggler, 2^29092392+40290 has a factor: 108661946
[/code]
108661946= 2*43*1263511

[QUOTE=firejuggler;251939][CODE]
[Wed Feb 09 16:18:52 2011]
ECM found a factor in curve #1, stage #1
Sigma=7978179970243502, B1=1000, B2=100000.
UID: firejuggler, 2^[B][COLOR="Red"]2[/COLOR][/B]9092392+40290 has a factor: 108661946
[/code]
108661946= 2*43*1263511[/QUOTE]

Wrong one.

shoot, wrong one.

RESPECT GUYS !!!!!:smile:

Also , today was found the first known 19-tuplet !!!

630134041802574490482213901 + [I]d[/I], [I]d[/I] = 0, 6, 10, 16, 18, 22, 28, 30, 36, 42, 46, 48, 52, 58, 60, 66, 70, 72, 76 by Raanan Chermoni & Jaroslaw Wroblewski

Wowsers! :shock: Big congratulations on what is (from what I gather) a very unexpectedly-early prime! This project has definitely had more than its share of "good luck" (statistically speaking :smile:) throughout. Makes you wonder if there's some property of these numbers that causes some conjectures to produce well above expectations (and others, well below, as we've observed at CRUS); if so, then it bodes well for Riesel base 6, which has had almost Five or Bust-like "luck" thusfar and is now down to two k's (one of which is extremely low weight and is supposed to take decades to find a prime for).

Meanwhile, though...
:party:

Awesome! Thanks for going ahead and posting this, Engracio. I am going to suggest abandoning any prp tests above this exponent. I see unconnected, paleseptember, engracio, and I have the only unfinished tests below it. Assuming that it checks out (and it almost certainly will) it would be nice to get a complete set of residues for an eventual double-check. John Blazek and Mark Rodenkirch had just set up PRPNET to start some double-checking, so this development took me by surprise. I have some strong prp tests running, and will keep you posted as they come in.

[QUOTE=engracio;251897]Well guys it was nice while it lasted. Pending on more rigorous testing by Phil, we have BUSTED nummer funf.

I thought I might post this prior to more verification to let others go on to other projects on their queue.:smile:[/QUOTE]

Congrats engracio! I grabbed the numbers before and after yours, unlucky again. :smile:

Yay, we found the last one, that is great. I will stop my clients for now as well.

As expected, my double-check came back matching!

[QUOTE]2^9092392+40291 is a probable prime! We4: 16576B3B,00000000[/QUOTE]

[QUOTE=enderak;251993]As expected, my double-check came back matching![/QUOTE]

:george:

A very nice find. Congratulations to all those involved. It is by far the largest PRP found to date. If it were proven prime it would rank [URL="http://primes.utm.edu/primes/lists/all.txt"]13th largest prime[/URL], but as it can not be (in a reasonable amount of time) it tops [URL="http://www.primenumbers.net/prptop/prptop.php"]Henri Lifchitz's PRP database[/URL] along with Five or Bust's other two Mega PRPs.

[QUOTE=enderak;251993]As expected, my double-check came back matching![/QUOTE]
[pedantic]Re: the thread title. Capt.Obvious reports that We1 (Wd4, etc) values (i.e. "We1: 16576B3B") are workunit hashes; these values will match (they are a hash of the [I]input[/I], not the [I]output[/I]) -- regardless of the test result (which in this case of course [B]did[/B] match, too; it was a 0 in all bits). [/pedantic]
Anyway, :lock::wacky::wblipp:

Congrats! Just out of curiosity, will this forum be placed in the "Archived projects" section when all doublechecks are complete?

:george:
Congratulations on (probably :wink:) proving the conjecture this project set out to prove! Next step is to wait for incredibly fast computers, or maybe quantum computer factoring for N-1/N+1, or maybe a new primality proving algorithm that makes ECPP look slow, and you can actually prove that these PRPs are all prime and that the conjecture is proven. :sleep: Well, you can always keep edging up the lower end of proving the PRPs up slowly in the mean time.

Fantastic work! I come back from holidays to find that the project has (almost certainly) been wrapped up!
My workunits have finished (no PRPs, no ninja'ing), and have just been emailed off to Phil. I had some ROUNDOFF errors, which I'll ask Phil's advice on, but once they've been cleared, I think it's only unconnected, engracio and Phil with tests below the magic number.

I have started strong probable prime tests, but I realize now that it will take me 5 weeks to finish all 20 tests on my Pentium D. Justin, how on earth did you finish your double-check so fast? I know I am running on old technology, but I did not realize that I was so out-of-date!

I am running a test on pfgw using a SCRIPT file. If anyone wants to volunteer to run some of these tests and speed up the verification, more power to you! The problem is basically to compute base^(2^9092391+20145) mod 2^9092392+40291 and see if the result is equal to 1 or -1 mod 2^9092392+40291. I am running these tests using pfgw and a SCRIPT file. The other tests have been run with all prime bases from 2 to 73, I have queued bases 2, 3, 5, and 7, but if anyone wants to run another base, post here and I can reserve it for you. I will also post my SCRIPT file tomorrow in case you want to use this method, but you may also be able to use pfgw by running an Euler test. I am not sure of what the current pfgw capabilities are.

[QUOTE=philmoore;252018]I have started strong probable prime tests, but I realize now that it will take me 5 weeks to finish all 20 tests on my Pentium D. Justin, how on earth did you finish your double-check so fast? I know I am running on old technology, but I did not realize that I was so out-of-date!

I am running a test on pfgw using a SCRIPT file. If anyone wants to volunteer to run some of these tests and speed up the verification, more power to you! The problem is basically to compute base^(2^9092393+20145) mod 2^9092394+40291 and see if the result is equal to 1 or -1 mod 2^9092394+40291. I am running these tests using pfgw and a SCRIPT file. The other tests have been run with all prime bases from 2 to 73, I have queued bases 2, 3, 5, and 7, but if anyone wants to run another base, post here and I can reserve it for you. I will also post my SCRIPT file tomorrow in case you want to use this method, but you may also be able to use pfgw by running an Euler test. I am not sure of what the current pfgw capabilities are.[/QUOTE]
What about just using:

pfgw -tc -q2^9092392+40291

That will perform a combined N-1/N+1 primality test, which of course will not totally succeed since neither N-1 or N+1 can be trivially factored, but the test still produces strong Fermat and Lucas PRP verification.

@Jeff I hear you about being lucky.:smile:

@enderak and paleseptember my rerun on a different computer for the prime won't be done until Fri morning. Several hours of power outage (only my block) did not help All other wu below the prime should be done by then too.

I am sure as others that the prime will be verified, just when.:unsure: Still happy we have found it sooner than later.:grin:

Phil, my double-check was done on an Intel i7 965 running on all 4 cores at once. If you can give me direction I would be happy to help with the pfgw tests. (Running 64-bit Windows OS)

Should I run it per mdettweiler's suggestion or can you e-mail your script file with directions to use? If the various tests can be split up, I have a few i7's available that could greatly reduce the test time. (Who ever said that patience is a virtue?)

Here's one factor of PRP-1: 2425284208751 (edit: aside from the trivial 2 and 7)

Nothing to write home about but it's a start.

[QUOTE=enderak;252026]Phil, my double-check was done on an Intel i7 965 running on all 4 cores at once. If you can give me direction I would be happy to help with the pfgw tests. (Running 64-bit Windows OS)

Should I run it per mdettweiler's suggestion or can you e-mail your script file with directions to use? If the various tests can be split up, I have a few i7's available that could greatly reduce the test time. (Who ever said that patience is a virtue?)[/QUOTE]

I was wondering how you ran that test so quickly!

I'll post a script file tomorrow and you can try it out. I really don't mind running the tests, and I really think that by the time we get three or four confirming results, we can assume that everything is good, but you may enjoy doing something different for a change, now that we are so close to the end of this project.

The problem with Max's suggestion is that according to my understanding, pfgw will use a few bases, and not necessarily the ones that we might choose. Let's try the script file.

Double-checking is a low priority, but since the queue is already set up, should I ask John Blazek if the PRPNET queue can be activated?

[QUOTE=mdettweiler;252019]pfgw -tc -q2^9092392+40291

That will perform a combined N-1/N+1 primality test, which of course will not totally succeed since neither N-1 or N+1 can be trivially factored, but the test still produces strong Fermat and Lucas PRP verification.[/QUOTE]

Where does it say about strong Fermat and Lucas PRP verification?

[QUOTE] -tc Combined N+1 and N-1 test.
When you are short of factoring N-1, or N+1, and the other
has some factors, you can try this mode to achieve a prove.
This too is NOT a probable test.
If the factored portions are F1 and F2, with F1>F2, and 3*F1+F2 is
100% or more, pfgw will be able to complete the proof. If this total
is slightly below 100%, it should still be able to force a proof
with some square tests using the -x flag.[/QUOTE]

Another factor: 76727594460993167.

I think Max (mdettweiler) is right, and this is worth a try. His suggestion was to run it with:
pfgw -tc -q2^9092392+40291
I'm thinking that maybe
pfgw -tc -l -q2^9092392+40291
will log the output. Report what bases it uses for the strong prp tests, and I'll remove them from my queue.

Here is a version of the script file:

[CODE]SCRIPT
DIMS Blankline,
DIMS Residup1, Probable_prime_residueis_plus1
DIMS Residum1, Probable_prime_residueis_minus1
DIMS Resultfails, Fails_test
DIM Base
DIM Result
DIM Resultres

SET Base,2
PRINT Base
POWMOD Result,Base,2^9092391+20145,2^9092392+40291
SET Resultres,(Result+1)%(2^9092392+40291)
IF (Resultres==0) THEN PRINT Residum1
IF (Resultres==0) THEN GOTO End_test
IF (Resultres==2) THEN PRINT Residup1
IF (Resultres==2) THEN GOTO End_test
SET Resultres,Resultres%(2^64)
PRINT Resultfails
PRINT Resultres
LABEL End_test
PRINT Blankline

END[/CODE]

Change the base from 2 to something else, save the file as, say, strongtest.txt, then run the test in pfgw with the command line "pfgw strongtest.txt -l". The -l flag will log the output to pfgw.out. For other Five or Bust finds in the past, we have run tests with all prime bases from 2 to 71. I have already queued up 2, 3, 5, and 7, so if you want to try this, post which bases you are testing below. You could modify this script file to run several bases sequentially.

The Jacobi symbol predicts whether we should find a residue of +1 or -1. The message "Fails_test" means, if that result can be verified, that the number is actually composite.

I will take 11, 13, 17, 19, 23, 29

[QUOTE]I'm thinking that maybe
pfgw -tc -l -q2^9092392+40291
will log the output. Report what bases it uses for the strong prp tests, and I'll remove them from my queue. [/QUOTE]

OK, I am running this now.

[QUOTE=enderak;252096]OK, I am running this now.[/QUOTE]
Put Alex's factors in a file, say, helperPRPm1 and run
[FONT=Fixedsys]pfgw -f1 -e999999 -tc -hhelperPRPm1 -l -q"2^9092392+40291"[/FONT]
[FONT=Fixedsys][/FONT]
There's no way to enforce the base though.
You can also add -e999999 (even less factoring) and there was some other flag that overrides the reporting frequency from 2500 iterations (but for this number it is good enough).

It appears that the first tried base will be 2 for N-1 and 1+sqrt(5) for N+1 but later the program may do other bases -- you will see.

OK, have done this. Thanks for the help - as you can tell I am new to pfgw

Serge's suggestion will save you from repeating the factoring. Thanks!

Just thought I might pile on some more on this prime. I have completed the rerun on a different computer. DUH!!! It's still a prime.:smile:

Also completed/submitted my part of wu lower than the prime to Phil.

Also taking: 31, 37, 41, 43

Fantastic result! It is great to see a project completed, well done :-)

Did 80 curves at B1=11k, not further factors found.

Edit: P-1 with B1=10^7, B2=10^9, no factor.

Five luckily busted !!!
 

Congrats to all !!! :lock::bounce wave::party:
Lucky, indeed! According to the 2008 paper (Helm et al. in Integers) written when the status was 3 down, 5 to go (compared to Samidoost website dated 2002), the odds at solving the dual Sierpinski problem were 10% at 100M, 50% at 11G and 90% at 72T. Therefore the odds were less than 1% at 9.1M !!! (I think, just 0.9% since the relationship is quasi-linear for small probabilities).

About the future: besides the direct problems (SoB, PSP, extended Sierpinski), are there searches for the prime or extended dual Sierpinski problems?
On my part I have done some personal research and I found that:
- for 78557 < k < 100000, only 2 candidates remain: 79309 (also a direct prime Sierpinski candidate) and 81919, with no PRP for n < 400000
- for k < 100000 there remain some quasi-Sierpinski dual candidates, i.e. with no prime/PRP, except for very small n (such that 2^n < or ~ k), for n < 400000:
90527 (prime for only n=1) ; 56839 and 63859 (prime for only n=2) ; 32899 and 55849 (n=10) ; 85489 (n=14) ; 383 (n=15) ; 24737 (n=17) ; 61969 (n=18).
- for the mixed Sierpinski problem in extended form (neither prime/PRP for k*2^n+1 nor 2^n+k for 78557 < k < 271129), only 2 candidates remain: 79309 (cited above) and 225931 (also a PSP candidate, no PRP for dual, though n has been explored only to 200000).

Cheers to all.:smile:

We have a winner!
 

The first two strong probable prime tests are in, with the correct residues, -1 for base 2 and +1 for base 3. I'm pretty certain now that all the other prp tests are going to confirm these, so we have a winner! Congratulations to everyone who has been involved in this project over the past 28 months. I still can't believe it was solved so quickly. Our last find had, I think, about a 17% chance of showing up with the amount of searching done from the previous find, so we were again quite lucky, especially considering that the search could have easily continued for years. So we really do have something to celebrate!

:bow wave::bow wave::bow wave:

:party::party::party::party::party:

Jeff and Justin, feel free to post any partial results from your strong tests here.

MooMoo2 asked if this project will be archived after double-checking is complete. PrimeGrid has offered to help with the double-checking and we are in the process of creating double-check files for the three unchecked sequences, 2131, 41693, and 40291 using PRPNET. Details will be forthcoming. There is no point in doing any more sieving or P-1 factoring, so that leaves the 20 largest probable primes as the only other piece of this project still unfinished. Certainly the 4 smallest could most likely be proven prime by ECPP with current programs, but two of these numbers are already larger than the largest proven ECPP prime to date, so any of these numbers would require a substantial effort. Perhaps we could just keep a stub open in case anyone wants to reserve one. But yes, most of this project will be archived. I'll go ahead and lock the reservation threads as we get things cleaned up.

Way to go! Thanks to Alex, Ben, Christian, Dmitry, Engracio, Gary, Geoff, Greg, Hadrian, Jayson, Jeff, Justin, Karsten, Kent, Lennart, Luigi, Max, Nathan, Norman, Phil, Robert, Serge, Tim, Winnie, and Yves, all of whom have contributed time either prp testing, sieving, P-1 testing, doing ECPP tests, or some combination. And thanks to the previous collaboration of 2001-2002 that narrowed the list of unfinished sequences down to eight.

Thanks also to George Woltman for the totally efficient prp testing software, to Geoff Reynolds for the awesome sieving software, to Marcel Martin for the contribution of his ECPP software, and to Mike Vang (xyzzy) for hosting a fun home for us.

:bounce wave::bounce wave::bounce wave:

[SIZE=1]Cross posting from earlier (inqusitive mids can find this somewhere else):[/SIZE]
[SIZE=1][/SIZE]
M.Martin wrote that he was in the process of developing a parallelized 64-bit linux version, and mentioned June-July for a release (things take time).
The threshold of 'possible' will be quantum-leaped right then.

Way to go Phil et al , party time.......

:bounce wave::bow wave::bounce wave::bow wave:

Great! I believe what's running on my machine now is a duplicate effort... N-1, base 2. Unless I'm mistaken I will just cancel that test.

I look forward to the double-checking!

Justin, I believe that it is also running an N+1 Lucas test as well, and it will choose other bases later, so if you haven't killed the job yet, you could let it run a bit further.

Here's what I have so far...

[QUOTE]Primality testing 2^9092392+40291 [N-1/N+1, Brillhart-Lehmer-Selfridge]
Running N-1 test using base 2[/QUOTE]
and it's only half done. with N-1, hasn't even gotten to the N+1. But if it will be useful to you I will continue to run it.

Thanks. I was tempted to kill my base=2 run originally, but I was not even certain that the script program was correct, or that the version of pfgw I was running would work without errors, so I let it finish to see what was happening. As it turned out, I did have an error in the script program (now corrected), but it would only have made a difference if the number had tested out as composite. I think it would be nice to at least run one strong Lucas test on this number.

Zuzu made some more careful calculations that I have now repeated, so I now estimate that we would have had about a 14.5% chance of finding the last prime in the range 5146295-9092394 instead of the 17% I wrote above. He also wrote on the Seventeen or Bust Forum that when this project started, at n = 1.4 million, we would have predicted a 0.9% chance of finding all the prps by 9092394. I haven't repeated that particular calculation, but it sounds like it is in the right ballpark. We have been incredibly lucky! Hopefully, some of this luck will rub off on Seventeen or Bust now.

A few other interesting tidbits:
[LIST]
The probability that a random number of this size which has passed these strong probable prime tests is actually composite: something like 1 chance in 10[SUP]1800[/SUP].[/LIST][LIST]
The estimated time to prove this number prime via ECPP: 4 trillion years (4x10[SUP]12[/SUP].)[/LIST][LIST]
The estimated time to prove this number prime via strong prp tests should the Generalized Riemann Hypothesis ever be proven: 300 billion years (3x10[SUP]11[/SUP].)[/LIST]
Fortunately, with a billion computers, this would only take 300 years, as the tests can be trivially distributed. Maybe we should start another project!

[QUOTE=philmoore;252628]Fortunately, with a billion computers, this would only take 300 years, as the tests can be trivially distributed. Maybe we should start another project![/QUOTE]
I don't suppose an ECPP proof could be distributed easily? (I know it can be distributed amongst multiple cores of the same computer, but is there any reason why they have to be on the same computer?) Because if it could be done, then that might be the next step for this project: working through the unproven PRPs from the bottom up. :smile: (Perhaps, by the time the biggest ones are reached, computers will be sufficiently faster that the proofs will be within reach by ECPP, or by some faster method if it becomes available by then.)

What are we waiting for? I am sure when our successors perfect quantum computing they will appreciate the 0.000001% head start. ;)

[QUOTE=philmoore;252628]He also wrote on the Seventeen or Bust Forum that when this project started, at n = 1.4 million, we would have predicted a 0.9% chance of finding all the prps by 9092394.[/QUOTE]

IMHO that strongly suggests something more than luck. Has anyone tested ranges to check if 2^n+k produces more primes than expected over any chosen range? It wouldn't be hard to search low n over a broad k range (even if well outside what was needed to prove the conjecture), e.g. such that you can expect 100 or more primes, and compare expected primes to observed to see if the trend holds up.

[QUOTE=Mini-Geek;252638]IMHO that strongly suggests something more than luck. Has anyone tested ranges to check if 2^n+k produces more primes than expected over any chosen range? It wouldn't be hard to search low n over a broad k range (even if well outside what was needed to prove the conjecture), e.g. such that you can expect 100 or more primes, and compare expected primes to observed to see if the trend holds up.[/QUOTE]

Sounds like a worth-while line of investigation. Fix n fairly large so that 2^n >> k, and search a range of odd k. We would expect the density of primes to be roughly 2/(n*ln(2)). Repeat for several values of n. Compare observation with expectation. Were we lucky, or could our luck have been predicted?

By the way, I added a few more names in the "thanks to ..." section of post 38. I can't believe I left out Justin (enderak), as I even mentioned him in the post! Also, Alex, Nathan, and Robert. If anyone else spots any oversights, please let me know!

[QUOTE=akruppa;251926]Awesome. Congrats to Phil and all contributors.

I'll try to get a few factors out of 2^9092392+40290 so we can make a somewhat stronger PRP test.[/QUOTE]

Congrats to the Five or Bust project!

What about finding some factors of 2^9092392+40292 ? Would that help with the PRP test for 2^9092392+40291 ? The factor DB has only 2^2*3 for it and I wouldn't know how to begin factoring such a large number.

It would help strengthen a P+1 PRP check. I've done 10 curves at B1=11000 but not found any prime factor >3 yet. I use mprime with
[CODE]ECM2=1,2,9092390,10073,11000,0,90,"3"[/CODE]

Did 90 curves at B1=11k, no factor.

[QUOTE=philmoore;252644]Sounds like a worth-while line of investigation. Fix n fairly large so that 2^n >> k, and search a range of odd k. We would expect the density of primes to be roughly 2/(n*ln(2)).[/QUOTE]

Don't you need to account for partial coverings? Some k's are much more likely than others to have primes.

[QUOTE=philmoore;252644]Sounds like a worth-while line of investigation. Fix n fairly large so that 2^n >> k, and search a range of odd k. We would expect the density of primes to be roughly 2/(n*ln(2)). Repeat for several values of n. Compare observation with expectation. Were we lucky, or could our luck have been predicted?[/QUOTE]

[QUOTE=wblipp;252690]Don't you need to account for partial coverings? Some k's are much more likely than others to have primes.[/QUOTE]

I had done a crude analysis a few years back for SR5 primes (or was it RieselSieve project?) where I calculated the correlation between the weight of a k and index of its first prime. IIRC, the correlation was something like 0.2.

My conclusion was that how many primes a series produces is only weakly predictive of where the first prime would be. So one doesn't necessarily help with the other. Of course, it wouldn't surprise me if the analysis was deeply flawed.

[QUOTE=wblipp;252690]Don't you need to account for partial coverings? Some k's are much more likely than others to have primes.[/QUOTE]

That's why I suggested fixing n and searching a range of k's, with enough k's, we would expect the weights to average out. On the other hand, maybe someone thinks that these particular k's were for some reason, more likely to yield primes at low n. That would be difficult to test, it basically would require extending this project!

I am going to search 3<=k<10K (k odd) for 10K<=n<=20K. From doing some calculations on portions of the range sieved to 1M, I expect approximately 10000 primes to be in this range. I'll have a more exact figure when sieving is complete. We'll see how it turns out. :smile: If anyone feels my bounds are a bad representation, they can search elsewhere (and, if they have a good reason why, I might be inclined to stop searching this).

Your estimate of 10000 is right. I'll be interested to hear what you find.

First report:
I have searched 10000<=n<=10100. 27373 candidates after sieving to 1001M, expected primes 145.03, observed primes 168. This is 1.91 standard deviations above the expected amount (the std dev of a [URL="http://en.wikipedia.org/wiki/Poisson_distribution"]Poisson distribution[/URL] is the square root of the expected, in this case 12.04). The chances of truly Poisson-distributed events falling within 1 [URL="http://en.wikipedia.org/wiki/Standard_deviation"]standard deviation[/URL] is 68.27%, within 2: 95.45%, within 3: 99.73%.
The expected primes for 10K-20K is 10020.86, making the standard deviation 100.10. I'd think there's something worth investigating if it's over +1.645 std devs at that point after taking away the 25 'extra' primes already observed, (sure, we observed 'extra' so far, but the expected primes remaining to be found is still about 10020.86-145.03=9875.83) which should only have a 10% chance of happening. To me, that would strongly suggest there's more here than random luck.

I just re-did the calculations from the INTEGERS paper on the probability of successfully solving this problem, and using the weights I used then, I get that we had only a 0.55% chance of solving this problem by n=9092392. I later used some of our sieving data to revise our Proth weight data, but this would have only made our chances smaller! To solve a problem that we had only a 1 chance in 180 (or worse) of solving is truly remarkable. Maybe Tim's data can shed some light on the problem, but I suspect that we were also lucky. Maybe it is time to buy a lottery ticket!?

:lock::lock::lock::lock::lock::lock::lock:

:party::party:

Second milestone:
10K-11K done, expected 1380.39 primes, found 1401, +0.55 std devs. Counting only from 10.1K-11K, it's actually a bit lower than expected: -0.06 std devs. At this point, I'd guess that there's nothing making it higher than it should be, and that this project was just extremely lucky. :smile:

Taking strong prp bases 47, 53, 59, and 61. (Only 67 and 71 are still available.)

[QUOTE=philmoore;252932]Taking strong prp bases 47, 53, 59, and 61. (Only 67 and 71 are still available.)[/QUOTE]

I will take 67 and 71 now. Here are most of my results so far:

[CODE]11
SSE2 Proth FFT: size=(1048576,17.342)
Probable_prime_residueis_plus1

13
SSE2 Proth FFT: size=(1048576,17.342)
Probable_prime_residueis_minus1

17
SSE2 Proth FFT: size=(1048576,17.342)
Probable_prime_residueis_plus1

19
SSE2 Proth FFT: size=(1048576,17.342)
Probable_prime_residueis_minus1

31
SSE2 Proth FFT: size=(1048576,17.342)
Probable_prime_residueis_plus1

37
SSE2 Proth FFT: size=(1048576,17.342)
Probable_prime_residueis_plus1

41
SSE2 Proth FFT: size=(1048576,17.342)
Probable_prime_residueis_plus1

43
SSE2 Proth FFT: size=(1048576,17.342)
Probable_prime_residueis_minus1
[/CODE]

The other two I should have in a day or so, and I will run these last two starting now.

Jeff.

I have also confirmed bases 5 and 7, both with residues -1, and am now working on 47 and 53. We are 12 for 12, I don't think there is much doubt how the other eight tests will work out! Any progress, Justin, on your tests? Jeff and I have been corresponding about pfgw, we are running an old version which seems to be faster than the newer version, surprisingly. The new version appears to be using the GMP library rather than GWNUM, but even a 6-year-old GWNUM algorithm seems to beat GMP. That could explain your slow progress, Justin; if you decide to kill it, I don't blame you. At any rate, Jeff and I have generated some good suggestions for the next version of pfgw, including an option to do strong prp tests.

Progress is slow but steady. I guess because it's only running on 1 core and unlike using your script on different bases, I don't know how I would split it across cores. It says it's using GWNUM 26.4.

This is all that is in my log file:
[QUOTE]Primality testing 2^9092392+40291 [N-1/N+1, Brillhart-Lehmer-Selfridge]
Running N-1 test using base 2
Running N+1 test using discriminant 5, base 1+sqrt(5)[/QUOTE]

The N+1 test is only about 20% done, it's still going to be at least a week for that to finish, and then hopefully I'll have at least some sort of result.

[QUOTE=philmoore;252913]I just re-did the calculations from the INTEGERS paper on the probability of successfully solving this problem, and using the weights I used then, I get that we had only a 0.55% chance of solving this problem by n=9092392. I later used some of our sieving data to revise our Proth weight data, but this would have only made our chances smaller! To solve a problem that we had only a 1 chance in 180 (or worse) of solving is truly remarkable.[/QUOTE]

So that's where my luck in finding a top-10 world-record k-tuplet has gone to... now I know.

Anyway, congrats on this remarkable find.

Two more finished.

[CODE]23
SSE2 Proth FFT: size=(1048576,17.342)
Probable_prime_residueis_plus1

29
SSE2 Proth FFT: size=(1048576,17.342)
Probable_prime_residueis_plus1
[/CODE]

I finished my search, and found 9977 primes. With 10020.86 expected, this is -0.44 std devs from the expected. In my opinion, the results couldn't be clearer: on average, dual Sierpinski numbers are no more likely to be prime than they "should" be. Now, this doesn't entirely remove the possibility that (very-)low-weight k's produce more primes than they should or that the 5 k's this project search produce more primes than they should (the latter would be quite hard to prove with any certainty). I've attached the primes. If someone calculates the weight of each k I searched and groups low weight k's together, they might be able to see if they produce as much as expected, or more or less. But take note that low weight k's tend to scatter from their expected far more than high weight k's, (if you make a scatter plot of the weight of each k vs its ratio of expected to observed primes, you'll see a funnel-like shape with the low weight k's being the large, i.e. more scattered, end of it) so a few examples in one extreme or the other mean nothing.
I still have the sieved file if someone wants it for these weight calculations. I can upload it on request. (4.70 MB zipped) If nobody else seems interested, I might do it some time.

My last two finished:

[CODE]67
SSE2 Proth FFT: size=(1048576,17.342)
Probable_prime_residueis_minus1

71
SSE2 Proth FFT: size=(1048576,17.342)
Probable_prime_residueis_plus1[/CODE]

Since I had 2 extra cores, I did two bonus bases:

[CODE]73
SSE2 Proth FFT: size=(1048576,17.342)
Probable_prime_residueis_plus1

79
SSE2 Proth FFT: size=(1048576,17.342)
Probable_prime_residueis_plus1[/CODE]

I have submitted this to the Lifchitz website.

Well this stinks - I accidentally closed the wrong cmd window (yup, the one running pfgw) and as far as I can tell it does not save progress anywhere to the hard drive. I don't know if I have it in me to start all over on this. Unless there's some way to restart the N+1 test where it left off, I'm going to abort this job.

Just say no to Windows. It is that easy. :-)

Thanks for your work on this, Justin, but I would say don't bother to restart, the progress was so excruciatingly slow. We now have 22 successful strong prp tests, I may program an N+1 test using gwnum at some point, but I'm pretty sure this one is a prime!

:party::party::party::party::party:

I'm planning a party to celebrate this on May 7th: 5/7/11. Anyone in Eugene, Oregon that day is more than welcome!

Anyfive seven elevennis? Sounds tempting...

According to Google Maps, it's about 22,000km, and will involve about two month's worth of kayaking. If I leave today I might make it ;)

My students might be a little miffed though!

[QUOTE=paleseptember;253926]According to Google Maps, it's about 22,000km, and will involve about two month's worth of kayaking. If I leave today I might make it ;)

My students might be a little miffed though![/QUOTE]

Bah, bring them along, field trip!

Hehehe!

Alright, we're going to be talking predicate logic now (paddle paddle paddle), we should be up to set theory by indonesia (paddle paddle paddle), and I think we can get through most of the section on graphs by the time we hit Japan (paddle paddle paddle.) (Internal note, this would be far easier if I'd remembered to print the notes before we left, and hadn't needed to bring the photocopier!)

It looks like LLR is adding the BPSW test:
[url]http://www.mersenneforum.org/showpost.php?p=254181&postcount=16[/url]

LLR could be used for this right? In the docs it says it is for numbers in the form N = k*b^n +/- 1 but later it also mentions k*b^n+c so

Once that is implemented it could be another PRP check to run on the non-proven exponents.

[QUOTE]2^9092392+40291 is Lucas PRP, Starting Frobenius test sequence
Using zero-padded Core2 type-3 FFT length 960K, Pass1=768, Pass2=1280, Q = 2

2^9092392+40291 is Frobenius PRP! (P = 4, Q = 2, D = 8) Time : 1037541.696 sec.[/QUOTE]

The Lucas test took around 9.8 days and Frobenius test 2.2 days on 1 core of
Core2Duo (Conroe) E6750 2.66 Ghz.

Thanks for running the Lucas test. It sounds like this should speed up once pfgw is updated to use the gwnum routines. Thanks, also, Jeff, for the LLR update. I would like to run some strong BPSW tests on all 20 of our probable primes once it is ready.

I see we are now listed on the Lifchitz page:
[url]http://www.primenumbers.net/prptop/prptop.php[/url]
Unfortunately, that web-site seems to be down about as much as up, but it now has the Five or Bust probable primes listed as #1, #2, #3, #5, and #9. Way to go! The one I discovered just 4 months before we launched Five or Bust, then #1, is now way down at #15. We have held the #1 spot since January 2009 - it will be interesting to see how long we hold on to it.

I'm running the BPSW now on the latest one 2^9092392+40291. It looks like LLR is check pointing for this as well so should be able to restart if need be.

Jeff.

This is taking quite a while, but I'm on the last of 3 tests now. It passed the Strong Fermat PRP and BPSW phases, and is now doing the final Frobenius stage.

I did the Frobenius test, but I guess it doesn't hurt to run again with the new parameters from the BPSW test, and it takes under 1/4th of the time the Lucas/BPSW test took.

Done!

[CODE]2^9092392+40291 is base 2-Strong Fermat PRP! Time : 190718.322 sec.
2^9092392+40291 is strong-Fermat and BPSW PRP, Starting Frobenius test sequence
2^9092392+40291 is strong-Fermat, BPSW and Frobenius PRP! (P = 1, Q = 3, D = -11) Time : 953429.151 sec.
[/CODE]

now, time to snooze [URL="http://ellipsa.eu/public/primo/alpha.html"]before the end of April[/URL]... :sleep:

Random idea (I haven't thought about details at all)... for numbers like these, say 2^9092392+40291, would it be possible to construct a curve with order 2^9092392? This order is certainly within the Hasse interval.

[QUOTE=Batalov;256426]now, time to snooze [URL="http://ellipsa.eu/public/primo/alpha.html"]before the end of April[/URL]... :sleep:[/QUOTE]

Oooh, very interesting. Do you have any details on what 4.x adds? Automatic support for multiple cores perhaps?

Jeff.

[QUOTE=Jeff Gilchrist;256522]Oooh, very interesting. Do you have any details on what 4.x adds? Automatic support for multiple cores perhaps?

Jeff.[/QUOTE]
Well concurrent tasks are possible so I think that probably means multiple cores.

[QUOTE=Jeff Gilchrist;256522]Oooh, very interesting. Do you have any details on what 4.x adds? Automatic support for multiple cores perhaps?

Jeff.[/QUOTE]
April came early! :-) The alpha version already exists and it looks very very neat; uses multiple cores in a way a "make -j NN" would: the main process feeds the available slots with the needed tests. Both Stage 1 and Stage 2 are parallelized and I haven't succeded in crashing his program yet. I haven't tried a larger number that would require backtracks, so I don't know if they are flawless.

A few things that he may want to add later is maybe separate virtual worker binaries to be distributable between many computers (so far it wants to be run on a single multi-core comp.), and secondly, make a command-line version (it is a GUI program now. Look and feel are just like primo.exe.).

But from the website I am not sure if Marcel wants the distribution of the alpha to be very wide. It is not on the website. Simply ask him by mail at ellipsa dot eu.

For the dual Sierpinski problem for 78557<k<271129, I found that 2^42210+91549 is (probable) prime, but I cannot find a (probable) prime for 2^n+79309, can someone find it?

Are there any other unresolved k values < 271129 for which you do not have a probable prime?

[QUOTE=sweety439;560403]For the dual Sierpinski problem for 78557<k<271129, I found that 2^42210+91549 is (probable) prime, but I cannot find a (probable) prime for 2^n+79309, can someone find it?[/QUOTE]

Not much use posting that without the search limits

[QUOTE=philmoore;560446]Are there any other unresolved k values < 271129 for which you do not have a probable prime?[/QUOTE]

[CODE]
2^unknown+79309
2^9+79817
2^42210+91549 (PRP)
2^394+131179
2^21+152267
2^1032+156511
2^57+163187
2^1038+200749
2^44+202705
2^16+209611
2^27+222113
2^unknown+225931
2^11+227723
2^3+229673
2^38+237019
2^60+238411
[/CODE]