Message boards :
Fermat Divisor Search :
How many?
Author 
Message 
Yves GallotVolunteer developer Project scientist Send message
Joined: 19 Aug 12 Posts: 672 ID: 164101 Credit: 305,042,960 RAC: 0

How many primes and how many Fermat divisors will be found during the Fermat Divisor Search? We don't know but it can be estimated. The expected values are 78 primes and 3 Fermat divisors!
Because n > 3640000 for k <= 49, that's more than 50 megaprimes and 3 mega Fermat divisors.
And since the largest known Fermat factor is 193 · 2^{3329782} + 1, the Fermat Divisor Search will certainly find a largest divisor.
k weight n_min n_max #primes #FermatDiv
5 1.01 6000000 9000000 0.59 0.2133
7 2.48 6000000 9000000 1.45 0.2072
9 2.69 4000000 9000000 3.15 0.3495
11 1.55 3640000 9000000 2.03 0.1846
13 1.10 3640000 9000000 1.44 0.1105
15 3.36 3640000 9000000 4.39 0.2925
17 0.75 3640000 9000000 0.98 0.0576
19 0.96 3640000 9000000 1.25 0.0658
21 2.65 3640000 9000000 3.47 0.1650
23 0.93 3640000 9000000 1.21 0.0527
25 2.42 3640000 9000000 3.17 0.1266
27 2.78 3640000 9000000 3.64 0.4040
29 2.44 3640000 9000000 3.18 0.1098
31 0.89 3640000 9000000 1.16 0.0373
33 2.27 3640000 9000000 2.97 0.0899
35 2.33 3640000 9000000 3.04 0.0869
37 2.91 3640000 9000000 3.80 0.1028
39 3.76 3640000 9000000 4.92 0.1261
41 0.99 3640000 9000000 1.30 0.0316
43 1.88 3640000 9000000 2.46 0.0572
45 2.89 3640000 9000000 3.78 0.0840
47 0.22 3640000 9000000 0.28 0.0060
49 1.39 3640000 9000000 1.81 0.0369
1323 3.73 1550000 3322000 4.10 0.0093
2187 2.50 1550000 3322000 2.75 0.0038
3125 1.31 1550000 3322000 1.45 0.0023
3267 2.35 1550000 3322000 2.59 0.0024
3375 2.95 1550000 3322000 3.24 0.0029
19683 2.38 300000 4000000 8.89 0.0045
TOTAL 78.5 3.02  


Thanks, Yves. Quite exciting. /JeppeSN  

Ravi FernandoProject administrator Volunteer tester Project scientist Send message
Joined: 21 Mar 19 Posts: 176 ID: 1108183 Credit: 10,198,834 RAC: 4,842

Thanks for the analysis, Yves. In a different thread, I predicted that we'd find about two Fermat divisors in the search. My calculations differ from yours in a few ways:
 I'm not sure whether you're including even n's for k=9 and 27. I excluded them, as they can't produce Fermat divisors (and we are not searching them).
 In the absence of a theoretical explanation of what's going on with k=5, I'm less optimistic about finding Fermat divisors there than you are. I assumed that k=5 primes have a 1/5 chance of being Fermat divisors, rather than the empirical proportion of 9/25.
 For k=27, I assumed that PRPNet hasn't missed any primes up to its current search limit near n=7.5M. This admittedly probably puts too much trust in a search that hasn't been doublechecked.
 I excluded the six large k's in my calculation. Your numbers look reasonable.
 I used a very crude estimate of the weight of each k, based on the number of primes they have produced so far. Strangely (unless I miscalculated somehow), my weights turned out to be systematically 1015% lower than yours, besides the expected statistical noise. I'm assuming your values are more accurate.
The first three bullet points each seem to affect the expected number of Fermat divisors by about 0.1 or slightly more, the fourth by about 0.025, and the last by about 0.4. This led me to a prediction of 2.2 Fermat divisors. That would drop by another ~0.27 if you trust that there are no missed primes in the ranges searched outside PrimeGrid for k = 9, 11, 13, 15, and 47.
Of course, the biggest potential source of error in this whole calculation is just plain luck. If we expect 3 Fermat divisors, then finding e.g. 1 or 5 really wouldn't be surprising.  

Yves GallotVolunteer developer Project scientist Send message
Joined: 19 Aug 12 Posts: 672 ID: 164101 Credit: 305,042,960 RAC: 0

Thanks Ravi, I agree with you, k = 9 and 27 must be corrected, but I remain optimistic for k = 5.
For k = 9 and 27, the weight is now the "odd weight".
The new estimate is lambda = 2.5 Fermat divisors (k = 27 collapsed!).
The distribution is
0 prime, 8%
1 prime, 21%
2 primes, 26%
3 primes, 21%
4 primes, 13%
5 primes or more, 11%
Considering the pessimistic estimate lambda = 2, we have
0 prime, 14%
1 prime, 27%
2 primes, 27%
3 primes, 18%
4 primes, 9%
5 primes or more, 5%
In both cases, the chance of winning is high for a PrimeGrid project!
I will compute the table for n < n_min and compare the estimate with the number of Fermat divisors found in this range.  

Yves GallotVolunteer developer Project scientist Send message
Joined: 19 Aug 12 Posts: 672 ID: 164101 Credit: 305,042,960 RAC: 0

In the tested ranges, the expected number of primes is 808 and 772 were found (relative error = 4.46%) and the expected number of Fermat divisors is 47.2 and 44 were found (6.86%).
Since n is exponential and the number of ranges (23) is relatively small, this is a reasonable degree of error.
k weight n_min n_max ~prm < n_min prm < n_min ~Fdiv < n_min Fdiv < n_min ~prm > n_min ~Fdiv > n_min
5 1.01 6000000 9000000 21.0 25 7.58 9 0.59 0.2133
7 2.48 6000000 9000000 51.0 41 7.29 6 1.45 0.2072
9* 1.69 4000000 9000000 33.6 33 3.73 4 1.98 0.2198
11 1.55 3640000 9000000 30.5 31 2.78 2 2.03 0.1846
13 1.10 3640000 9000000 21.5 22 1.65 2 1.44 0.1105
15 3.36 3640000 9000000 65.5 59 4.37 1 4.39 0.2925
17 0.75 3640000 9000000 14.6 19 0.86 3 0.98 0.0576
19 0.96 3640000 9000000 18.6 20 0.98 3 1.25 0.0658
21 2.65 3640000 9000000 51.4 47 2.45 3 3.47 0.1650
23 0.93 3640000 9000000 17.9 18 0.78 0 1.21 0.0527
25 2.42 3640000 9000000 46.8 41 1.87 1 3.17 0.1266
27* 0.72 7500000 9000000 14.7 16 1.63 2 0.19 0.0211
29 2.44 3640000 9000000 46.9 41 1.62 4 3.18 0.1098
31 0.89 3640000 9000000 17.0 11 0.55 0 1.16 0.0373
33 2.27 3640000 9000000 43.6 40 1.32 1 2.97 0.0899
35 2.33 3640000 9000000 44.6 43 1.28 0 3.04 0.0869
37 2.91 3640000 9000000 55.8 52 1.51 1 3.80 0.1028
39 3.76 3640000 9000000 72.1 80 1.85 2 4.92 0.1261
41 0.99 3640000 9000000 19.0 16 0.46 0 1.30 0.0316
43 1.88 3640000 9000000 36.0 37 0.84 0 2.46 0.0572
45 2.89 3640000 9000000 55.2 53 1.23 0 3.78 0.0840
47 0.22 3640000 9000000 4.1 3 0.09 0 0.28 0.0060
49 1.39 3640000 9000000 26.4 24 0.54 0 1.81 0.0369
TOTAL 808.1 772 47.2 44 50.83 2.49
Rel error 4.46% 6.86%
 

Message boards :
Fermat Divisor Search :
How many? 