On 2016-09-21 04:29, Adam P. Goucher wrote:
I personally like Pollard's rho factorisation. Easy to implement (no fancy sieves) and offers a quadratic speedup over trial division (so a worst-case time complexity of sqrt(sqrt(N)) for factorising N).
It's easy to like: fast, terse, and clever. But it just finds a factor rather than the full factorization, and doesn't prove primality. How tersely can we do *all* this if we settle for √n time complexity? --rwg
You can check primality first using Miller-Rabin for various initial values. I think there's a bound (or rather two, the tighter one being dependent on GRH) of how many values you need to check.
Sent: Wednesday, September 21, 2016 at 1:20 PM From: "Bill Gosper" <billgosper@gmail.com> To: math-fun@mailman.xmission.com Subject: Re: [math-fun] The largest twin-primes known today...
On Wed, Sep 21, 2016 at 2:14 AM, Bill Gosper <billgosper@gmail.com> wrote:
I think Allan means 3^2, not 3^12. This would have been an extremely easy factorization even for Lehmer's optical contraption <https://en.wikipedia.org/wiki/Lehmer_sieve>. Or Macsyma back when it trial-divided by consecutive odd numbers. Which is pretty much like GCDing with their product, now that we can store big numbers. I just wrote a tiny (and very untested) recursive program in a similar vein:
In[832]:= Clear[dumfac]; dumfac@1 = {}; dumfac[n_Integer] := (dumfac@n = {n}; dumfac@n = Join[dumfac[#], dumfac[n/#]] &@ GCD[n, Binomial[#, Floor[#/2]] &@Floor[Sqrt[n]]])
In[833]:= dumfac[2996863034895] // tim
During evaluation of In[833]:= 0.188517 sec, 5
Out[833]= {5, 3, 3, 18583, 3583757}
In[834]:= PrimeQ /@ %
Out[834]= {True, True, True, True, True} --rwg
Phew, that doesn't even slightly work!
In[342]:= dumfac@11111111111111111 // tim
During evaluation of In[342]:= 12.903538,1
Out[342]= {11111111111111111}
Mindlessly changing a 2 to a 3, In[338]:= Clear[dumfac]; dumfac@1 = {}; dumfac[n_Integer] := (dumfac@n = {n}; dumfac@n = Join[dumfac[#], dumfac[n/#]] &@ GCD[n, Binomial[#, Floor[#/3]] &@Floor[Power[n, (2)^-1]]])
In[339]:= dumfac@11111111111111111 // tim
During evaluation of In[339]:= 11.772568,2
Out[339]= {2071723, 5363222357}
But 12 seconds! On 2016-09-21 03:04, Tom Karzes wrote:
Or you could just invoke the factor program that's part of GNU coreutils and is part of a standard Ubuntu Linux install:
% factor 2996863034895 2996863034895: 3 3 5 18583 3583757 %
See the info file for details.
Tom
But the elephant in the room is Mathematica: In[320]:= FactorInteger[(10^59 - 1)/9] // tim
During evaluation of In[320]:= 0.035899 sec, 2
Out[320]= {{2559647034361, 1}, {4340876285657460212144534289928559826755746751, 1}} --rwg
On 2016-09-20 16:05, Allan Wechsler wrote:
Factoris says the coefficient factors to 3^12.5.18583.3583757.
On Tue, Sep 20, 2016 at 6:55 PM, Dan Asimov <asimov@msri.org> wrote:
P.S. I'm puzzled by this statement about these twin primes at that
link:
----- They will enter Chris Caldwell's “The Largest Known Primes Database” (http://primes.utm.edu/primes) ranked 1st for twins, and each
entered
individually ranked 4180th overall. -----
Why do they have the same ranking overall? Does it not matter that one is bigger than the other?
—Dan
> On Sep 20, 2016, at 3:35 PM, Dan Asimov <asimov@msri.org> wrote: > > Is anything known about the factorization of that coefficient > > (other than its divisibility by 5 and 9)? > > Was it chosen as part of some algorithm that singled out relatively > likely candidates? Or was it just stumbled on at random from a > massive search? > > > Or maybe one of our factoring experts can factor it? (You know who you are.) > > —Dan > > >> On Sep 20, 2016, at 3:18 PM, Eric Angelini <Eric.Angelini@kntv.be
wrote: >> >> >> ... are: >> 2996863034895*2^1290000-1 >> and >> 2996863034895*2^1290000+1 >> >> http://www.primegrid.com/download/twin-1290000.pdf
math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun