# As N gets large, what is the likelihood some K is a Fermat Liar for N?

I've been running a simulation for a while starting at 2^(2^8) checking for Fermat possible primes base 2. So far it's listed about 1 in 180 numbers as possible primes. By the prime number theorem, I believe you would expect about 1 in 177 numbers as actual primes at this range, so odds are it is reporting few if any actual Pseudo-primes.

I could start to run a full prime certification on these but a) That's going to take quite a while, currently odds are nearly all of these numbers are prime so there will be next to no fast rejections and b) that isn't going to help estimate at other ranges - such as 2^2^16, which I am currently more interested in, but is prohibitively expensive for me to search at to any degree of statistical usefulness.

Note, I am not looking for, "for a particular N what is provable maximum probability of K being a Fermat liar (if N is not Carmichael)" which is what searching really wants to show me, but rather more: "for a particular K, roughly how many integers in the range N to M should we expect K to be a Fermat liar for, for large N,M".

Edit1: I left the simulation running overnight, and after 50M tests it has converged to roughly 177.34 as the gap between found primes as opposed to a gap of 177.44 indicated by the prime number theorem, so virtually all of the possible primes are actually prime and 2 is going to be a Fermat Liar for this range with very very low probability (as it is not a liar for most of the potential primes, and obviously a liar for none of the rejected numbers). I guess the next step for me is actually running some primality proofs to get some exact numbers.

Edit2: Testing against 11 bases in the strong pseudoprime test (should be enough to expect not much more than 1 false positive in ~4M primes in the worst case) run against the first 200K possible primes found, and only the second number in the range (2^2^8+1) was both flagged as a probable prime but did not pass all 11 rounds. This suggest (but does not prove) Fermat Liars are vanishingly rare as N gets large, save for numbers of some special form.

• oeis.org/A001567 gives the Fermat pseudoprimes. There are a number of references, but I didn't see an estimate of density. I believe the recommendation for prime checking is to check Fermat for a number of small bases before you go to a full prime test. Most of these will fail $3$. – Ross Millikan Feb 12 at 5:06
• Please describe more precise which kind of numbers you want to check. In particular, do you want to check huge "random" numbers or huge "special" numbers ? – Peter Feb 12 at 9:38
• I'm not sure to get more precise than "for a particular K, roughly how many integers in the range N to M should we expect K to be a Fermat liar for, for large N,M". I believe that fully describes what I am looking for. – Steven Armstrong Feb 12 at 16:01
• @StevenArmstrong It will be extremely difficult to estimate the number of liars. Therefore, I ask which kind of numbers you want to check because the answer can heavily depend on this. – Peter Feb 13 at 13:49