Update on dual prime verification

[philmoore]

Louie suggested that this would be a good way to keep people updated on the status of the verification of the dual prime 67607 + 2^16389. This is part of Payam Samidoost's dual Sierpinski conjecture project, which is attempting to prove that 78557 is the smallest odd value of k for which k + 2^n is always composite. There are currently 8 k values less than 78557 for which the status is unknown, see http://sierpinski.insider.com/dual . The weaker "mixed Sierpinski" conjecture says that 78557 is the smallest value of k for which there is no prime of either the form k*2^n + 1 or k + 2^n. This mixed conjecture will be proven once the above probable prime is proven to be prime. (For more details, see the 10th Prime!! thread.) I started running Primo on this number on May 9th, around 5pm. By May 16th, it had run down from 16390 bits to 15000 bits, progress of about 200 bits a day, but it has since then increased progress to the point that it is currently at 12980 bits, progress in the past five days of about 400 bits a day. It is currently working on test 131, trying to prove that a number of 12980 bits is prime. Once that is done, it will be able to establish the primality of the original number. I expect that the program will finish quickly once we get below 10000 bits.

[philmoore]

A quick update, Friday afternoon 4:30 local time: 4 more days has Primo running on test 207 with 11116 digits left, a rate of about 450 digits per day. I am guessing that the run will finish in the middle of next week, maybe 4 or 5 more days.

[philmoore]

Tuesday evening, 8:30 pm local time: Primo just finished phase 1 and has started phase 2. Phase 1 still had 8700 bits left when I got to work this morning and finished this much in 12 hours. Considering that it took 19.5 days to go from 16390 bits to 8700 bits, the progress today has seemed very fast! It now says, "EC test, factoring polynomial, degree 8". I have no idea how long phase 2 will take, as I haven't used this program for years, and have never done a number this large. I'll give you another update tomorrow.

[philmoore]

It looks like my optimism was unjustified! Phase 2 has been running for 13.5 hours and has only progressed to test 12, from the original 16390 bits down to 16119 bits. My impression is that phase 2 runs faster than phase 1, but not radically faster. Perhaps it may finish in a week to a week-and-a-half. Then we need to verify the certificate, which I think should go fairly quickly.

[olaright]

Thanks for keeping us informed! I am keeping my fingers crossed.

Ola

[philmoore]

Well, it just keeps chugging along, now on test 106 and down from 16390 bits to 13601 bits, after not quite 3 days of work. Phase 2 is definitely going faster than phase 1, and I'm guessing that it will probably finish early next week. It seems to spend most of its time factoring large polynomials of a wide range of degrees, from degree 2 up to at least degree 464 once.

[philmoore]

I am guessing that it will finish tonight - it is now on test 302 at 8559 bits. If it accelerates toward the end like it did in phase 1, it should only take a few hours.

[philmoore]

From the Primo certificate file:

[PRIMO - Primality Certificate]
Version=2.3.2
WebSite=http://www.ellipsa.net/
Format=3
ID=B2E8503A0D5CB
Created=05/09/2007 04:55:31 pm
TestCount=666
Status=Candidate certified prime

[Running Times]
Initialization=58.57s
1stPhase=483h 10mn 25s
2ndPhase=147h 3mn 36s
Total=630h 14mn 59s

[Candidate]
File=C:\Program Files\primo[1]\work\Sierp.in
Expression=2^16389+67607
HexadecimalSize=4098
DecimalSize=4934
BinarySize=16390

It must have finished just after 11, as the running time was 26 days, 6 hours, and 15 minutes. Jim Fougeron has sent me a copy of his Cert_Val program to validate the certificate, and I haven't run it yet, but I have never heard of any problem with Primo certificates, so it looks like we have a prime and a new theorem:

Theorem: 78557 is the smallest odd positive integer k such that k*2^n+1 and k+2^n are always composite for all positive integers n.

[philmoore]

For good measure, I validated the certificate twice, so we should be pretty certain that this sucker is prime! The first time was with Jim Fougeron's CertVal program, it took 27 hours, 39 minutes, and 24 seconds. Second time was with Primo, the program which generated the certificate in the first place. This took 10 hours, 51 minutes, and 43 seconds. Certainly faster, but to my mind, there is merit in having an independent validation as well. They seem like long runs, but don't forget that it took over 26 days just to generate the certificate in the first place. Now SoB has a genuine theorem to its credit!