0
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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$. $\endgroup$ – Ross Millikan Feb 12 at 5:06
  • $\begingroup$ 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 ? $\endgroup$ – Peter Feb 12 at 9:38
  • $\begingroup$ 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. $\endgroup$ – Steven Armstrong Feb 12 at 16:01
  • $\begingroup$ @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. $\endgroup$ – Peter Feb 13 at 13:49
0
$\begingroup$

Fermat Liars become extremely rare as numbers grow large.

At the scale of 2^2^256, at most 1 in 2 trillion numbers will be a Fermat Liar for base 2 in particular. The relationship is not exactly a power of the number, but it is close. If you double the bit size of the number in question, you increase the bit size of the average gap between numbers for which 2 is a Fermat Liar by approximately 85% for numbers in these ranges.

Around 2^2^16, the average gap is on the order of 1e(2e3) [yes, nested scientific notation], and so barring some other contributing factor, selecting a range of numbers that size that you can complete any operation on will not in general result in finding any Fermat Liars for any number at any base.

However...

Numbers of certain forms are far more likely to produce Fermat Liars to certain bases than their general infrequency indicates. Numbers of the form 2^2^n+1 pass the Fermat Primality test to base 2 for all values of n from at least 0 to 20, and are Fermat liars whenever this number isn't also prime. These are specifically the Fermat Primes, and there are no known Fermat Primes for n > 4, 2 is a liar for most of these numbers.

As such both scales quoted in the question contain an initial Fermat Liar base 2, and while other Fermat Liars for the smaller scale (2^2^8) would eventually be found with a protracted naive search, at the larger scale (2^2^16) this is unlikely. Base k at k^k^n+b for small b (single digit) is an unusually likely place to run into a Fermat Liar without particularly searching for them and other numbers with short and simple (aka low Shannon entropy) descriptions should also be considered suspect, but in general they simply won't be encountered when examining small ranges (even ranges a few trillion count as small here) of bases and candidate numbers at that magnitude.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.