mersenneforum.org Potential primality of F33, F34, and F35
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2018-07-19, 01:37   #12
ATH
Einyen

Dec 2003
Denmark

7×419 Posts

Quote:
 Originally Posted by a1call 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

 2018-07-19, 02:34 #13 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 23·3·79 Posts 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
2018-07-19, 02:51   #14
GP2

Sep 2003

22·3·5·43 Posts

Quote:
 Originally Posted by a1call 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

 2018-07-19, 03:06 #15 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 23·3·79 Posts Didn't think of having it factored. 2983954661377 | F12 2983954661377 = 114689 x 26017793
2018-07-19, 03:09   #16
GP2

Sep 2003

22·3·5·43 Posts

Quote:
 Originally Posted by ATH 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

 2018-07-19, 03:53 #17 GP2     Sep 2003 22·3·5·43 Posts 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
2018-07-19, 07:19   #18
ET_
Banned

"Luigi"
Aug 2002
Team Italia

2·2,383 Posts

Quote:
 Originally Posted by GP2 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...

2018-07-19, 12:26   #19
ATH
Einyen

Dec 2003
Denmark

293310 Posts

Quote:
 Originally Posted by GP2 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.

2018-07-19, 12:57   #20
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

11·127 Posts

Quote:
 Originally Posted by GP2 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_ 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].

2018-07-19, 13:25   #21
Dr Sardonicus

Feb 2017
Nowhere

22×5×173 Posts

Quote:
 Originally Posted by GP2 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?

2018-07-19, 20:49   #22
ATH
Einyen

Dec 2003
Denmark

293310 Posts

Quote:
 Originally Posted by GP2 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

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post Explorer09 Software 2 2017-03-09 08:17 jasong jasong 21 2016-05-28 09:59 cheesehead Software 14 2013-05-16 00:45 cheesehead Lounge 20 2009-06-05 20:24 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.