Re: [math-fun] The largest twin-primes known today...
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 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
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 Bill Gosper writes:
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
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
math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
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
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).
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
2996863034895 factors to 3^2*5*18583*3583757 seemingly instantly in maple. On Wed, Sep 21, 2016 at 6:29 AM, Adam P. Goucher <apgoucher@gmx.com> 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).
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (4)
-
Adam P. Goucher -
Bill Gosper -
James Buddenhagen -
Tom Karzes