Other

drummers-lowrise

Message boards : Fermat Divisor Search : How many?

 Subscribe SortOldest firstNewest firstHighest rated posts first
Author Message
Yves Gallot
Volunteer developer
Project scientist

Joined: 19 Aug 12
Posts: 671
ID: 164101
Credit: 305,042,960
RAC: 0

Message 133065 - Posted: 21 Sep 2019 | 10:25:45 UTC

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 · 23329782 + 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

JeppeSN

Joined: 5 Apr 14
Posts: 1511
ID: 306875
Credit: 34,984,759
RAC: 23,002

Message 133072 - Posted: 21 Sep 2019 | 14:01:43 UTC

Thanks, Yves. Quite exciting. /JeppeSN

Ravi Fernando
Volunteer tester
Project scientist

Joined: 21 Mar 19
Posts: 165
ID: 1108183
Credit: 9,883,087
RAC: 8,152

Message 133094 - Posted: 21 Sep 2019 | 20:39:19 UTC - in response to Message 133065.

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 double-checked.
- 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 10-15% 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 Gallot
Volunteer developer
Project scientist

Joined: 19 Aug 12
Posts: 671
ID: 164101
Credit: 305,042,960
RAC: 0

Message 133106 - Posted: 22 Sep 2019 | 9:31:44 UTC

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 Gallot
Volunteer developer
Project scientist

Joined: 19 Aug 12
Posts: 671
ID: 164101
Credit: 305,042,960
RAC: 0

Message 133108 - Posted: 22 Sep 2019 | 10:59:29 UTC

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?