Pascal's OPN roadblock files

[ryanp]

Originally Posted by Pascal Ochem

The run with bound \(10^{2100}\) just finished and we see the impact of the C301.
The old file has 1589 composites.
http://www.lirmm.fr/~ochem/opn/old_mwrb2100.txt
The new file has 1192 composites.
http://www.lirmm.fr/~ochem/opn/mwrb2100.txt

Don't worry if you are working on a composite that has disappeared.
It will re-appear in mwrb2200 once the run with bound \(10^{2200}\) is over, because of the composite \(\sigma(11^{330})\).

I'm down to 1124 composites remaining in my mwrb2100.

Remaining: https://cs.stanford.edu/~rpropper/mwrb2100.txt
Factors found: https://cs.stanford.edu/~rpropper/opn.txt

[Pascal Ochem]

The run for \(10^{2200}\) is now over. The program gave up on the following branches:

\(127^{192}\) / \(19^2\) \(3^6\) \(1093^2\) \(398581^{102}\) / \(7^2\) / \(13^1\)
\(127^{192}\) / \(19^2\) \(3^6\) \(1093^2\) \(398581^{108}\) / \(7^2\) / \(13^1 \)
\(61^{232}\) / \(13^2\) \(3^2\) / \(5^{520}\) / \(179^{138}\) / \(1789^1\)

The first two situations are due to a standard branching on \(3^6\), so that the considered upper bound on the abundancy is \(\frac32\) instead of \(\frac{1093}{3^6}\).
I fixed it by making an exact branching, after \(127^{192}\) / \(19^2\), on every component \(3^{2i}\), that is, even when \(2i+1\) is composite.

There is no such fix for the third situation: we already have exact branchings on \(13^2\), \(3^2\), \(1789^1\), and the abundancy \(\sigma_{-1}(p^e)\) is really close to \(\sigma_{-1}(p^\infty)=\frac{p}{p-1}\) for \(61^{232}\), \(5^{520}\), \(179^{138}\).

The abundancy in this branch is \(\frac{61}{60}\frac{183}{13^2}\frac{13}{3^2}\frac54\frac{179}{178}\frac{1790}{1789}=1.99999792324886\), which is very close to 2.
If we don't get a miraculous ECM factor and if we want to avoid a huge roadblock circumventing, we can use an old school argument:
One copy of 5 comes from \(\sigma(1789^1)\).
The other 519 copies of 5 must come from things of the form \(\sigma(p^4)\) with \(p\equiv1\pmod{5}\). Moreover, \(p\ge963121\) so that the abundancy is at most 2.
The case of \(\sigma(p^{5^k-1})\) giving \(5^k\) with \(k\ge2\) is ruled out because it is suboptimal for our argument.
Now \((963121^4)^{519}\) is greater than our bound \(10^{2200}\).

[henryzz]

It might be a good learning exercise to push each of the forbidden factors as far as possible(assuming that previous primes have been forbidden). Working out the logic to circumvent these roadblocks could be an important learning exercise. I know runtime will limit some of the primes but AFAIK some are still quite quick runs.
The logic gained from these circumventions could potentially be used to shorten the current proof.

Unless I have made a mistake 179^139-1 looks factorable with 179*(179^23)^6-1 at 314 digits which looks within reach of nfs@home(or maybe ryanp) which is currently sieving a couple of SNFS candidates with 326 digits.

[wblipp]

Originally Posted by Pascal Ochem

The first two situations are due to a standard branching on \(3^6\), ...

I fixed it by making an exact branching, after \(127^{192}\) / \(19^2\), on every component \(3^{2i}\), that is, even when \(2i+1\) is composite.

Could I persuade you to explain the rationale for choosing this fix?

In the paper for \(10^{1500}\) you used exact branches on \(3^2\) and \(3^4\), which required additional standard branches at \(3^8\), \(3^{14}\), and \(3^{24}\). You could have added an exact branch at \(3^6\) by adding standard branches as \(3^{20}\), \(3^{34}\), and \(3^{48}\). I have thought of two possible reasons that you didn't do this. First, perhaps this wouldn't have been sufficient and more complex exact branches would have been required - \(3^8\) would be particularly complicated. Second, perhaps you judged this growing list of extra standard branches to be aesthetically ugly, and chose the "every component" as more elegant and simpler to explain.

[Pascal Ochem]

Henry:
Luckily, the ad-hoc argument is simple (and computer-free) thanks to a Fermat prime raised to large power (5^520) and a special prime that is already specified.
It is good enough for now, we don't need to rush the factorization of 179^139-1 that would cost dozens of dollars and grams of CO2.
Maybe more important feasible composites will show up after a closer look at the log files of this run.

William:
Assuming subtle mathematical or aesthetical motives is not a good bet this time.
The exact branch at 3^6 that you describe certainly works, but there is no suitable command option to do it, whereas I only had to replace "-X4 3" by "-Y 3".
The expected computational gain is not worth the effort of adding the "-X6" option and the risk to mess with Michael's code.

[lavalamp]

Originally Posted by Pascal Ochem

we don't need to rush the factorization of 179^139-1 that would cost dozens of dollars and grams of CO2.

Has it been attacked much with ECM?

Alas it is just above the size that can be run with GPU-ECM.

[RichD]

Originally Posted by lavalamp

Has it been attacked much with ECM?

Alas it is just above the size that can be run with GPU-ECM.

I don't know of much ECM work except the above post by ryanp which did a blanket ECM run of the entire file. Based upon the factors found I am guessing about a t60 or t61.

[ryanp]

Originally Posted by lavalamp

Has it been attacked much with ECM?

Alas it is just above the size that can be run with GPU-ECM.

For that one in particular, I've hit it with 110K curves at B1=85e7. May try B1=29e8 next.

[henryzz]

Originally Posted by Pascal Ochem

Henry:
Luckily, the ad-hoc argument is simple (and computer-free) thanks to a Fermat prime raised to large power (5^520) and a special prime that is already specified.
It is good enough for now, we don't need to rush the factorization of 179^139-1 that would cost dozens of dollars and grams of CO2.
Maybe more important feasible composites will show up after a closer look at the log files of this run.

William:
Assuming subtle mathematical or aesthetical motives is not a good bet this time.
The exact branch at 3^6 that you describe certainly works, but there is no suitable command option to do it, whereas I only had to replace "-X4 3" by "-Y 3".
The expected computational gain is not worth the effort of adding the "-X6" option and the risk to mess with Michael's code.

I have finally had time to think further on this and have a few more questions:

Am I correct in thinking that 5 being a Fermat prime made it easier to determine the optimal way of finding all the needed 5s and similar logic could be applied to other primes although less effectively(maybe \(963121^{519}\) rather than \((963121^4)^{519}\)?) Does the special prime need to always be specified as long as it is accounted for(there may be examples of it providing more than one of the prime).
If we can generalize this technique without it becoming ineffective it could reduce the tree significantly. Surely there must be a useful argument for finding the needed 232 61s. Applying this sort of argument to more than one prime at once could get complicated as a term could provide both needed primes. I will think on this further. It shouldn't be too difficult for a program to find a list of the 232 smallest \(p^x\) such that \(61 | \sigma(p^x)\), however, it would be necessary to also check for \(61^2 | \sigma(p^x)\) for \(\sigma(p^x)\) up to twice the size(and 61^3 etc.) which could be harder. Maybe a suboptimal(we underestimate the size) case could be proven.

You mentioned a -Y option above. The version posted at https://www.arthy.org/opn/ doesn't contain this. Are you working with a later version(if so would you be willing to share?)? Am I correct in thinking that the -X2, -X4 and -Y options are only needed for some of the primes to avoid issues but could be removed for other forbidden factors? Theoretically, the -Y could only be used for 127^192 reducing computation in the other trees where 3 appears especially 3^x.

Are we still only forbidding the factors 127,19,7,11,331,31,97,61,13,398581,1093,3,5,307,17? http://www.lirmm.fr/~ochem/opn/efficiency.txt suggests this was only sufficient up to 1735

The link to the BCR paper http://wwwmaths.anu.edu.au/~brent/pub/pub116.html is now broken. https://maths-people.anu.edu.au/~brent/pub/pub116.html seems to work.

[ThomRuley]

Is anybody doing the numbers in the t500 file or is there a better place to work on composites?

[RichD]

Originally Posted by ThomRuley

Is anybody doing the numbers in the t500 file or is there a better place to work on composites?

There is no t500 file. Did you mean t550 or t600?
I have a lot of ECM work completed on these latter files.