mersenneforum.org New Fermat factors
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2018-12-21, 07:30   #276
Gary

"Gary"
Aug 2015
Texas

72 Posts

Quote:
 Originally Posted by ET_ December 19th, 2018 New Fermat factor from FermatSearch! 1075441212722595 . 2135+1 is a Factor of F132!!! Peter Strasser discovered the seventh Fermat factor of this year! He used George Woltman's mmff program running on his home computer. Congratulations to Peter from FermatSearch, for his second factor! -
Congratulations Peter!!!

Last fiddled with by ET_ on 2018-12-21 at 08:42

 2019-01-29, 10:31 #277 ET_ Banned     "Luigi" Aug 2002 Team Italia 2×2,383 Posts January 28th, 2019 New Fermat factor from FermatSearch! 1527888802614951 . 2120+1 is a Factor of F118!!! Peter Strasser discovered the first Fermat factor of this year! He used George Woltman's mmff program running on his home computer Congratulations to Peter from FermatSearch, for his third factor!
2019-01-29, 11:32   #278
feromant

"Roman"
Dec 2016
Everywhere

2×13 Posts

Quote:
 Originally Posted by ET_ January 28th, 2019 New Fermat factor from FermatSearch! 1527888802614951 . 2120+1 is a Factor of F118!!! Peter Strasser discovered the first Fermat factor of this year! He used George Woltman's mmff program running on his home computer Congratulations to Peter from FermatSearch, for his third factor!
Congratulations Peter!!!

 2019-03-26, 04:15 #279 Gary     "Gary" Aug 2015 Texas 72 Posts A new factor from FermatSearch I would like to report the following new Fermat factor: 332,436,749 * 2^9865 + 1 divides F9863 This was discovered March 23 using pmfs on a HPE Superdome X system. In each year from 2013 to 2018 no more than 7 new factors were found. So far in 2019 we are on the same pace: 2 factors in ~3 months. But who knows, maybe we will all get lucky and find many new factors. Might we match the 16 new factors discovered in 2012?
2019-03-29, 12:53   #280
mathwiz

Mar 2019

2×32×5 Posts

Quote:
 Originally Posted by Gary I would like to report the following new Fermat factor: 332,436,749 * 2^9865 + 1 divides F9863 This was discovered March 23 using pmfs on a HPE Superdome X system. In each year from 2013 to 2018 no more than 7 new factors were found. So far in 2019 we are on the same pace: 2 factors in ~3 months. But who knows, maybe we will all get lucky and find many new factors. Might we match the 16 new factors discovered in 2012?
Nice find!

Curious which range(s) you have fully searched?

2019-03-31, 15:59   #281
Gary

"Gary"
Aug 2015
Texas

72 Posts

Quote:
 Originally Posted by mathwiz Nice find! Curious which range(s) you have fully searched?
Thanks mathwiz!

That depends on what you mean by "fully". For every range assigned to me in the fermatsearch.org Merge Tables, I have tested each Proth number (k * 2^n + 1) that survives the sieve to see if it divides any classic Fermat number. I have NOT tested to see if it divides any GFN or xGFN, since (as I understand it) that usually involves first testing to see if the Proth number is prime or PRP, which my program does not do.

2019-03-31, 17:23   #282
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

11·127 Posts

Quote:
 Originally Posted by Gary I have NOT tested to see if it divides any GFN or xGFN, since (as I understand it) that usually involves first testing to see if the Proth number is prime or PRP, which my program does not do.
You could test basically in no time the generalized Fermat numbers (GFN), [and don't know what is xGFN, perhaps that is a^(2^n)+b^(2^n)], because you can make a cheap prp test if n is not that small:

what you are doing is:
let d=k*2^n+1 what survived the sieving process:
you calculate a(i)=2^(2^i) mod d, for say up to i<=n+30. (nobody saves the whole "a" array, only the last term).

for a cheap prp test you need only: res=2^(d-1)=a(n)^k mod d, ofcourse for a prp number you need res=1. For n~10000, k~1e30 the slowdown of the extra prp test is less than 0.5%, in general it is ~T*log(k)/n if the total running time was T.

2019-04-02, 03:11   #283
Gary

"Gary"
Aug 2015
Texas

618 Posts

Quote:
 Originally Posted by R. Gerbicz You could test basically in no time the generalized Fermat numbers (GFN), [and don't know what is xGFN, perhaps that is a^(2^n)+b^(2^n)], because you can make a cheap prp test if n is not that small: what you are doing is: let d=k*2^n+1 what survived the sieving process: you calculate a(i)=2^(2^i) mod d, for say up to i<=n+30. (nobody saves the whole "a" array, only the last term). for a cheap prp test you need only: res=2^(d-1)=a(n)^k mod d, ofcourse for a prp number you need res=1. For n~10000, k~1e30 the slowdown of the extra prp test is less than 0.5%, in general it is ~T*log(k)/n if the total running time was T.
Thanks for the suggestion Robert, and for walking me through the math. I am not a mathematician, so the explanation was very helpful. I will add this to the program the next time I am making changes.

Itâ€™s difficult to find a complete definition of all the GFN terminology on the web, but several researchers seem to be using the following:

Generalized Fermat Numbers (GFN or GF): GF(n,a) = a^(2^n) + 1
Extended Generalized Fermat Numbers (xGFN or xGF): xGF(n,a,b) = a^(2^n) + b^(2^n)

Someone please correct me if this is inaccurate.

2019-04-02, 09:48   #284
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

25658 Posts

Quote:
 Originally Posted by R. Gerbicz you calculate a(i)=2^(2^i) mod d, for say up to i<=n+30. (nobody saves the whole "a" array, only the last term).
That is excessive, for Fermat numbers you have to check up to i=n-2, because F_m has got divisors k*2^n+1 for n>=m+2.

Quote:
 Originally Posted by Gary I will add this to the program the next time I am making changes.
Discovered later, but the real slowdown would be higher in your range, because you need also a^(2^i) mod a for a<=12 and i<n, if you want the vintage range for GFN,xGFN. If you are not obsessed with only Fermat factors, then the slowdown would be roughly 4 % with n~10000, sieving depth~50.

Don't see here a shortcut, only the "known" gain, let r(a)=a^(2^(n-30)) mod d, for prp we already know r(2), then
compute r(3),r(5),r(7),r(11) (so where the base is prime) and then with only one mulmod you can get the rest:
r(1)=1 (ofcourse)
r(4)=r(2)*r(2) mod d
r(6)=r(2)*r(3) mod d
r(8)=r(2)*r(4) mod d
r(9)=r(3)*r(3) mod d
r(10)=r(2)*r(5) mod d
r(12)=r(2)*r(6) mod d
[you need to do this in order, because you also reuse composite index, say r(4) for r(8)]
after that you know r(a) mod d for all a<=12.
Then for up to m=n-1 with only extra 12 (actually 11) mulmods per exponent, and in total 29*11 mulmods you
can get a^(2^i) mod d for a=1..12,i=n-30..n-1.

And at each i=(n-30)..(n-1) check to see if a^(2^i)+b(2^i) mod d = 0 for xGFN (basically checking only GFN gives no speedup).

ps. so you have to stop at i=n-1, and not at i=n-2 (like for Fermat number divisors).

 2019-12-11, 17:47 #285 ET_ Banned     "Luigi" Aug 2002 Team Italia 10010100111102 Posts New Fermat factor from Gary Gostin! News from Gary Gostin! I would like to report a new Fermat factor: ***** 15,249,465,809 * 2^2591 + 1 divides F2587 This was discovered running pmfs on an HPE Superdome X system. Mankind has now discovered 350 factors of Fermat numbers! We should have a party!
 2019-12-12, 09:34 #286 LaurV Romulan Interpreter     Jun 2011 Thailand 2×3×31×47 Posts Yeeee! Congrats!

 Similar Threads Thread Thread Starter Forum Replies Last Post Batalov Factoring 149 2017-02-20 12:06 yourskadhir Miscellaneous Math 5 2012-12-12 04:18 siegert81 Factoring 1 2011-09-05 23:00 Merfighters Factoring 0 2010-04-13 14:16 UberNumberGeek Factoring 6 2009-06-17 17:22

All times are UTC. The time now is 01:46.

Sat Sep 26 01:46:50 UTC 2020 up 15 days, 22:57, 0 users, load averages: 1.55, 1.85, 1.82