OP Home Composites Cleared Against Pomerance ElevenSmooth |
In addition to direct road blocks, the nine special cases from the BCR paper had to be resolved.
Bound | Chain | Comments |
10^{329} |
σ(5)=2*3 σ(3^{2})=13 σ(13^{4})=30941 σ(30941^{36})=C162 |
On March 2, 2005 Alex Kruppa factored the C162 into P50 * P113 using SNFS. |
10^{412} |
σ(5)=2*3 σ(3^{4})=11^{2} σ(11^{4})=5*3221 σ(3221^{4})=5*11*195760063931 σ(195760063931^{16})=C197 |
On February 18, 2005 OddPerfect.org factored the C197 into P29 * P169 using GMP ECM. |
10^{454} | σ(127^{108})=C228 |
On February 11, 2005 OddPerfect.org factored the C228 into P48 * C180 using GMP ECM. It was the sixth largest GMP ECM factor so far in 2005. |
10^{478} | σ(3^{2})=13 σ(13^{4})=30941 σ(30941)=2*3^{4}*191 σ(191^{102})=C233 |
On March 12, 2010 Tom Womack factored the C233 into P115*P118 using SNFS This was the last known case where the Excess Exponent Extension (see below) would have been needed. |
10^{482} |
σ(5)=2*3 σ(3^{2})=13 σ(13^{4})=30941 σ(30941^{30})=81760848073*C124 σ(81760848073^{10})=C110 |
0n February 19, 2005 Alex Kruppa factored the C110 into P44 * P66 using SNFS. Later the C124 was factored into P45 * P80 |
10^{486} | σ(5^{348})=C244 |
On April 9, 2006 Alex Kruppa factored the C244 into P108 * P136 using SNFS. |
10^{487} | σ(3^{2})=13 σ(13^{4})=30941 σ(30941)=2*3^{4}*191 σ(191^{16})=3153651086937051299292748168322873857 σ(3153651086937051299292748168322873857^{6})=C219 |
On February 27, 2005 OddPerfect.org factored the C219 into P34 * C186 using P-1 via the ECM Server. |
10^{491} | σ(19^{192})=C246 |
On September 29, 2005 Ryan Propper factored the C246 into P56 * P191 using the OddPerfect ECM Server. |
10^{511} | σ(5)=2*3 σ(3^{4})=11^{2} σ(11^{4})=5*3221 σ(3221^{73})=C253 |
On December 29, 2008 Tom Womack et al. factored the C253 into P70 * P88 * P96 in an SNFS factorization coordinated through the Mersenne Forum. |
10^{541} | σ(3^{2}) = 13 σ(13) = 2 * 7 σ(7^{4}) = 2801 σ(2801^{78}) = C269 |
On October 27, 2010 Tom Womack et al factored the C269 into P85 * P184 in an SNFS factorization coordinated through the MersenneForum |
10^{568} | σ(3^{2}) = 13 σ(13) = 2 * 7 σ(7^{4}) = 2801 σ(2801^{83}) = C283 |
On March 15, 2013 Ryan Propper factored the C283 into P93 * P193 in an SNFS factorization |
10^{578} | σ(5) = 2 * 3 σ(3^{606}) = C290 |
On November 1, 2010 NFS@Home factored the C290 into P85 * P96 * P110 in an SNFS factorization. |
10^{586} | σ(3^{6}) = 1093 σ(1093) = 2 * 547 σ(547^{106}) = C291 |
On July 22, 2013 Ryan Propper factored C291 into P60 * P232 in an SNFS factorization |
10^{593} | σ(19^{232})=C297 |
On January 8, 2008 OddPerfect.org factored the C297 into P46 * P252 using the OddPerfect ECM Server. |
Special methods were used to push these nine cases above the limit of 10^{300}, but more general solutions are needed to push the limit much higher. Complete factorizations are now known for these nine cases and for all other composites in the BCR proof.
BCR used a "back track" algorithm that creates short "pretty" proofs with little repetition. OddPerfect.org will use a "pile on" algorithm that creates longer uglier proofs that sometimes go further with the same known factors. We believe that "ugly" proofs, which may have some factor subchains repeated many times, are acceptable now because these proofs are likely to be checked by computer programs rather than by people. This "pile on" approach would have cleared some of the the BCR roadblocks.
Case 1 line 7343 |
σ(11^{4})=5*3221 σ(3221^{42})=C148 |
On February 23, 2005 Alex Kruppa factored the C148 into P72 x P77 using SNFS. |
Case 2 line 7163 |
σ(7^{172})=C146 |
The C146 was factored into P49 x P97 before the founding of OddPerfect.org. |
Case 3 line 7985 |
σ(31^{2})=3*331 σ(331^{4})=5*37861*63601 σ(63601^{2})=3*2203*612067 σ(612067^{22})=C128 |
On April 3, 2005 the C128 was factored as P47 x P82. Also, OddPerfect.org could pile on with 37861 or 2203. |
Case 4 line 8866 |
σ(13^{2})=3*61 σ(61^{2})=3*13*97 σ(97^{2})=3*3169 σ(3169^{36})=C127 |
In January, 2005 OddPerfect.org factored the C127 into P32 x C95 using Alpertron. On March 1, 2005 the C95 was factored into P45 x P50 from Oddperfect.org's Composites Page |
Case 5 line 4479 |
σ(7^{4})=2801 σ(2801)=2*3*467 σ(467^{46})=C123 |
The C123 was factored into P24 x P43 x P52 before the founding of OddPerfect.org. |
Case 6 line 9527 |
σ(13^{4})=30941 σ(30941)=2*3^{4}*191 σ(191^{46})=C105 |
The C105 was factored into P34 x P72 before the founding of OddPerfect.org. |
Case 7 line 11343 |
σ(3^{18})=1597*36389 σ(36389^{22})=C101 |
The C101 factors as P37 x P65. Also, OddPerfect.org could "pile on" with 1597. |
Case 8 line 9526 |
σ(13^{4})=30941 σ(30941)=2*3^{4}*191 σ(191^{42})=C96 |
The C96 was factored into P46 x P51 before the founding of OddPerfect.org. |
Case 9 line 12201 |
σ(3^{240})=C115 |
The C115 was factored into P36 x P79 before the founding of OddPerfect.org. |
Consider the factor "3" in the chain for the cleared road block at 10^{478} prior to factoring the now-factored C233:
To see why we can't just declare this to be a contradiction, think about why the OPN chains only consider exponents one less than a prime. Why don't we explicitly consider 3^{8} or 3^{14}? We don't consider these because σ(3^{8}) and σ(3^{14}) are divisible by σ(3^{2}). At the point in a proof where we might consider these, we will have previously proved there is no OPN in the present search space divisible by σ(3^{2}).
This means the assumption being made on the line σ(3^{2}) is that 3 occurs as a divisor of N as 3^{3k-1}, and 3^{2} is just the smallest member of this set. The factor of 3^{4} on the right side shows that k must be greater than 1. These observations lead to a new sequence of assumptions that can be made at this point to extend the chain: k is divisible by 3, or by 5, or by 7, or by increasing p values.
The first of these, k is divisible by 3, leads to the assumption that 3^{8} is a factor, and gives us the additional prime 757 from σ(3^{8}) to extend the factor chain. The later cases of k=3p for p=5 and higher each bring in the factors from σ(3^{p-1}), which must be considered anyway. This almost leads to the conclusion that we don't have to consider these cases here because they can be subsumed under the cases of 3^{p-1} which occur later in the proof.
Almost, but not quite. The subsumption only works if we clear all the following 3^{p-1} cases without again resorting to the Excess Exponent Extension method. For example, we might later end up eliminating 3^{4} by reaching a point where the right side has at least 5 factors of 3, and invoking Excess Exponent Elimination for 3^{5j-1}, with j greater than 1. Rather than try to keep track of these restrictions, we will explicitly consider each case of p in 3^{3p-1}. This is another example of ugly proofs, but it makes both the creation and the checking of the proof simpler.