New Fermat factors

[Gary]

Originally Posted by ET_

December 19th, 2018
New Fermat factor from FermatSearch!
1075441212722595 . 2¹³⁵+1 is a Factor of F₁₃₂!!!
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!!!

[ET_]

January 28th, 2019
New Fermat factor from FermatSearch!
1527888802614951 . 2¹²⁰+1 is a Factor of F₁₁₈!!!
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!

[feromant]

Originally Posted by ET_

January 28th, 2019
New Fermat factor from FermatSearch!
1527888802614951 . 2¹²⁰+1 is a Factor of F₁₁₈!!!
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!!!

[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?

[mathwiz]

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?

[Gary]

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.

[R. Gerbicz]

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.

[Gary]

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.

[R. Gerbicz]

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.

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).

[ET_]

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!

[LaurV]

Yeeee! Congrats!