Register FAQ Search Today's Posts Mark Forums Read

2021-06-01, 13:40   #958
ryanp

Jun 2012
Boulder, CO

1010110002 Posts

Quote:
 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

 2021-07-09, 10:49 #959 Pascal Ochem     Apr 2006 103 Posts no OPN is smaller than 10^2200 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}$$.
 2021-07-09, 11:46 #960 henryzz Just call me Henry     "David" Sep 2007 Liverpool (GMT/BST) 26·3·31 Posts 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.
2021-07-11, 05:27   #961
wblipp

"William"
May 2003
New Haven

1001010000012 Posts

Quote:
 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.

 2021-07-11, 13:17 #962 Pascal Ochem     Apr 2006 103 Posts 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.
2021-07-11, 23:26   #963
lavalamp

Oct 2007
Manchester, UK

3·5·7·13 Posts

Quote:
 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.

Last fiddled with by lavalamp on 2021-07-11 at 23:29

2021-07-11, 23:55   #964
RichD

Sep 2008
Kansas

22·11·79 Posts

Quote:
 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.

2021-07-12, 03:34   #965
ryanp

Jun 2012
Boulder, CO

34410 Posts

Quote:
 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.

2021-09-09, 14:06   #966
henryzz
Just call me Henry

"David"
Sep 2007
Liverpool (GMT/BST)

26×3×31 Posts

Quote:
 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.

 2021-11-04, 15:12 #967 ThomRuley     May 2003 3·97 Posts Is anybody doing the numbers in the t500 file or is there a better place to work on composites?
2021-11-04, 19:17   #968
RichD

Sep 2008
Kansas

D9416 Posts

Quote:
 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post Xyzzy GPU Computing 1 2017-05-17 20:22 Mark Rose GPU Computing 52 2016-07-02 12:11 firejuggler GPU Computing 12 2016-02-23 06:55 Elhueno Homework Help 5 2008-06-12 16:37 jchein1 Factoring 30 2005-05-30 14:43

All times are UTC. The time now is 07:41.

Wed Jan 19 07:41:11 UTC 2022 up 180 days, 2:10, 0 users, load averages: 1.48, 1.91, 1.90