mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > FermatSearch

Reply
 
Thread Tools
Old 2018-07-19, 01:37   #12
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

7×419 Posts
Default

Quote:
Originally Posted by a1call View Post
https://en.m.wikipedia.org/wiki/Fermat_number

How is that not meaningless, given that there are infinite number of Fermat numbers?
Thank you in advance.
https://en.wikipedia.org/wiki/Prime_number_theorem

Quote:
This means that for large enough N, the probability that a random integer not greater than N is prime is very close to 1 / log(N)

Fermat numbers grows very very fast (double exponential function) so 1/log(2^(2^N)) = 1/(2^N*log (2)) grows very very slowly so even if there are infinite number of terms it will still be a small finite value.

If you sum 1/(2^N*log(2)) from N=33 to 1000 or higher in PARI/GP you get ~ 3.359*10^(-10) which is about 1 in 2.98 billion. If we only count those above n=33 with no known factor the chance is about 1 in 3.4 billion.

Last fiddled with by ATH on 2018-07-19 at 01:44
ATH is offline   Reply With Quote
Old 2018-07-19, 02:34   #13
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

23·3·79 Posts
Default

Barring my usual miscalculation, I found a factor for F12 which is not listed here:

https://oeis.org/A023394/list

Is there somewhere I can have it submitted or otherwise included?

Thank you in advance.

Last fiddled with by a1call on 2018-07-19 at 02:37
a1call is offline   Reply With Quote
Old 2018-07-19, 02:51   #14
GP2
 
GP2's Avatar
 
Sep 2003

22·3·5·43 Posts
Default

Quote:
Originally Posted by a1call View Post
Barring my usual miscalculation, I found a factor for F12 which is not listed here:
That seems to be a list of all factors of any Fermat number, in increasing order, except it shows only the smallest ones.

The known factors of F12 are:

7 × 214 + 1 = 114689
397 × 216 + 1 = 26017793
973 × 216 + 1 = 63766529
11613415 × 214 + 1 = 190274191361
76668221077 × 214 + 1 = 1256132134125569
17353230210429594579133099699123162989482444520899 × 215 + 1 = 568630647535356955169033410940867804839360742060818433

The largest was discovered in 2010. People have been looking for a larger one since then, without success.


If you find one that's not in the above list, chances are it's a composite factor consisting of two or more of the above multiplied together.

If you've really found a new one, just post it here and become famous. But almost certainly you haven't.

Last fiddled with by GP2 on 2018-07-19 at 02:56
GP2 is offline   Reply With Quote
Old 2018-07-19, 03:06   #15
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

23·3·79 Posts
Default

Didn't think of having it factored.

2983954661377 | F12

2983954661377 = 114689 x 26017793
a1call is offline   Reply With Quote
Old 2018-07-19, 03:09   #16
GP2
 
GP2's Avatar
 
Sep 2003

22·3·5·43 Posts
Default

Quote:
Originally Posted by ATH View Post
For F33: k*235 searched to k=4.8*1017 and k*236 searched to k=7*1017 and lower for k*237, k*238 etc.
I wonder, for F32 did they stop searching when they found a factor at k=1479? Is there any record of a systematic search for a larger second factor?

I wonder if there could possibly be easy additional factors to be found for F29 and higher, where little or no ECM can be done.

I already mentioned the only known factors for F31 and F32, for the others they are:

F29 has one known factor: 1120049 × 231 + 1
F30 has two known factors: 149041 × 232 + 1 and 127589 × 233 + 1
GP2 is offline   Reply With Quote
Old 2018-07-19, 03:53   #17
GP2
 
GP2's Avatar
 
Sep 2003

22·3·5·43 Posts
Default

As already mentioned, the paper by Boklan and Conway cited in the Wikipedia article on Fermat numbers estimates the odds of a new Fermat prime at less than one in a billion.

Interestingly, it also conjectures that there is only a finite number of Mersenne primes whose exponent p is a Sophie Germain prime (i.e., 2p + 1 is also prime).

The known Sophie-Germain-prime exponents of Mersenne primes are: 2, 3, 5, 89, 9689, 21701, 859433, 43112609.

Edit: this is actually OEIS sequence A065406, except the last term needs to be added.

The paper actually makes a more general conjecture: "There are only finitely many Mersenne primes 2p − 1 where p is a prime and ap + b is also
prime (for some fixed integers a and b where (b, p) = 1)." For the special case of Sophie Germain primes, a = 2 and b = 1.

Last fiddled with by GP2 on 2018-07-19 at 04:08
GP2 is offline   Reply With Quote
Old 2018-07-19, 07:19   #18
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

2·2,383 Posts
Default

Quote:
Originally Posted by GP2 View Post
I wonder, for F32 did they stop searching when they found a factor at k=1479? Is there any record of a systematic search for a larger second factor?
Nope 😊 the whole set of N in [31 \ 39] has been completely searched up to k = 10^17...
ET_ is offline   Reply With Quote
Old 2018-07-19, 12:26   #19
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

293310 Posts
Default

Quote:
Originally Posted by GP2 View Post
I wonder, for F32 did they stop searching when they found a factor at k=1479? Is there any record of a systematic search for a larger second factor?
When the programs test for example k*2^36 up to k=7*10^17, they only test odd k values but then they trial divide them in every Fermat number up to F34.

So the tested limits for F32 is the limits for k*2^34, k*2^35, etc.
ATH is offline   Reply With Quote
Old 2018-07-19, 12:57   #20
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

11·127 Posts
Default

Quote:
Originally Posted by GP2 View Post
As already mentioned, the paper by Boklan and Conway cited in the Wikipedia article on Fermat numbers estimates the odds of a new Fermat prime at less than one in a billion.
Quote:
Originally Posted by ET_ View Post
Nope 😊 the whole set of N in [31 \ 39] has been completely searched up to k = 10^17...
Good article, but working with real data the expected probability is higher, roughly log(10^17)/(2^33*log(2))=6e-9 for F33, [there could be here a small additional factor also].
R. Gerbicz is offline   Reply With Quote
Old 2018-07-19, 13:25   #21
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

22×5×173 Posts
Default

Quote:
Originally Posted by GP2 View Post
Interestingly, it also conjectures that there is only a finite number of Mersenne primes whose exponent p is a Sophie Germain prime (i.e., 2p + 1 is also prime).
This is certainly true for p == 3 (mod 4). The work is half done!
;-)

Quote:
The paper actually makes a more general conjecture: "There are only finitely many Mersenne primes 2p − 1 where p is a prime and ap + b is also
prime (for some fixed integers a and b where (b, p) = 1)." For the special case of Sophie Germain primes, a = 2 and b = 1.
Are there any cases besides 4n + 3, 8n + 7 both prime that automatically produce a factor?
Dr Sardonicus is offline   Reply With Quote
Old 2018-07-19, 20:49   #22
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

293310 Posts
Default

Quote:
Originally Posted by GP2 View Post
The paper actually makes a more general conjecture: "There are only finitely many Mersenne primes 2p − 1 where p is a prime and ap + b is also
prime (for some fixed integers a and b where (b, p) = 1)." For the special case of Sophie Germain primes, a = 2 and b = 1.
For a,b<=10 the combination with the highest mersenne prime exponent that also have ap+b prime is 3p+10 with 21 exponents. The highest for a,b<=100 is 25, a,b<=1000: 27, a,b<=10000: 31.

Code:
21:
3p+10:  3 7 17 19 31 61 89 107 607 1279 2203 3217 9689 9941 110503 132049 216091 3021377 24036583 25964951 42643801

25:
3p+50:  3 7 13 17 19 61 89 127 521 607 2203 4253 9941 23209 44497 86243 132049 859433 1257787 1398269 6972593 20996011 24036583 25964951 30402457
12p+25:  3 7 13 17 31 61 89 127 521 607 1279 2281 3217 4253 4423 9689 11213 44497 86243 132049 216091 756839 1257787 1398269 43112609
42p+55:  2 3 7 13 17 19 61 89 107 521 1279 2203 2281 4253 4423 9689 9941 19937 86243 859433 1398269 6972593 32582657 37156667 43112609

27:
15p+532:  3 5 13 17 31 61 89 107 127 1279 2203 2281 3217 4253 4423 44497 86243 132049 859433 1398269 3021377 13466917 25964951 32582657 37156667 42643801 77232917
21p+880:  13 17 19 31 61 89 127 521 607 1279 2203 2281 3217 4423 19937 86243 110503 216091 756839 859433 1257787 1398269 2976221 6972593 20996011 37156667 74207281
52p+525:  13 17 31 61 89 107 127 521 607 1279 3217 9689 9941 19937 21701 44497 132049 216091 756839 859433 1257787 6972593 13466917 30402457 37156667 74207281 77232917
504p+55:  2 3 7 13 17 19 31 127 1279 2203 2281 3217 4253 4423 9689 11213 19937 21701 44497 110503 756839 859433 1257787 24036583 30402457 43112609 74207281

31:
33p+2590:  3 13 19 31 61 89 107 127 607 1279 2203 2281 3217 4253 4423 9689 9941 21701 44497 86243 132049 216091 756839 859433 1257787 6972593 13466917 24036583 37156667 42643801 57885161
ATH is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Prime95 potential race on WORKER_THREADS_ACTIVE and WORKER_THREADS_STOPPING Explorer09 Software 2 2017-03-09 08:17
Would you give up your cat ownership if it increased your potential virility? jasong jasong 21 2016-05-28 09:59
A potential cause of Windows low-memory messages cheesehead Software 14 2013-05-16 00:45
Low-Stress Job with High Potential? Mathematician cheesehead Lounge 20 2009-06-05 20:24
Formula to calculate number of potential factors? Fusion_power Miscellaneous Math 13 2005-10-24 17:58

All times are UTC. The time now is 02:05.

Tue Sep 22 02:05:46 UTC 2020 up 11 days, 23:16, 0 users, load averages: 1.25, 1.42, 1.46

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.