The Baillie-PSW primality test consists of a strong Fermat base $2$ test and a standard or strong Lucas sequences test. For an odd number $n$, the Fermat base $2$ test consists in checking whether the congruence $2^{n-1} \equiv 1 \pmod n$. A composite $n$ that passes the Fermat base $2$ test is known as a base $2$ pseudoprime, or psp-2 for short. These are listed at OEIS under sequence A001567: https://oeis.org/A001567 . The standard and strong Lucas sequences test are explained in the paper Lucas pseudoprimes by Baillie and Wagstaff at the link: https://www.ams.org/journals/mcom/1980-35-152/S0025-5718-1980-0583518-6/ . The Lucas pseudoprimes following Selfridge’s Method A are listed at OEIS under sequence A217120: https://oeis.org/A217120. Let $F$ be the set of Fermat base $2$ pseudoprimes and $L$ be the set of Lucas pseudoprimes following Selfridge’s Method A. It’s not known whether the intersection of $F$ and $L$ is non-empty, although it is conjectured by Pomerance that the Baillie-PSW test has infinitely many pseudoprimes, which would imply that the intersection of $F$ and $L$ is an infinite set. We will explain a heuristic involving random sets that gives a simple answer to when one might expect to see the smallest Fermat-Lucas pseudoprime, which we define as a Fermat base 2 pseudoprime which is also a Lucas pseudoprime following Selfridge’s Method A.
Given a large integer $N$, we define $F_{N}=\{n| n \in F, n<N\}$ and $L_{N}=\{n|n \in L, n<N\}$. For some $\alpha$ between $0$ and $1$, $|F_{N}| = N^{\alpha}$ and similarly there is a $\beta$ between $0$ and $1$ for which $|L_{N}|= N^{\beta}$. To model $F_{N}$ and $L_{N}$ probabilistically, we can use Bernoulli random subsets of $\{1…N\}$, with probability parameter $N^{\alpha-1}$ for $F_{N}$ and$N^{\beta-1}$ for $L_{N}$. A Bernoulli random subset of a finite set $S$ with parameter $p$ is intuitively a set constructed by conducting $|S|$ random Bernoulli trials with parameter $p$ and including element number $j$ exactly when Bernoulli trial number $j$ yields $1$, for $j=1 \cdots |S|$. Let $A$ denote a Bernoulli random subset of $\{1…N\}$ with probability parameter $N^{\alpha-1}$ and $B$ denote a Bernoulli random subset of $\{1… N\}$ with probability parameter $N^{\beta-1}$. Then the expected value of $|A|$ is $N^{\alpha}$ and the expected value of $|B|$ is $N^{\beta}$. We assume the elements of $A$ and $B$ are selected independently. Given an element $x$ of $\{1… N\}$, $x$ has probability $N^{\alpha-1}$ of belonging to $A$ and probability $N^{\beta-1}$ of belonging to $B$. Therefore, $x$ has probability $N^{\alpha+\beta-2}$ of belonging to $A \cap B$. We can treat the $N$ elements of $\{1,… N\}$ independently, therefore the expected size of $A \cap B$ is $N^{\alpha+\beta-1}$. In case $\alpha + \beta-1 > 0$ the expected size of $A \cap B$ is greater than $1$ while if $\alpha + \beta – 1 < 0$ the expected size of $A \cap B$ is less than $1$.
From Dana Jacobsen’s web-page on pseudoprimes: http://ntheory.org/pseudoprimes.html we find that for $N=10^{15}$, $|F_N|=1801533$ and that $|L_N|=2402549$. So $\alpha = 0.4170$ and $\beta = 0.4254$, giving $\alpha+\beta-1 = -0.1576$. The Bernoulli random subset heuristic then suggests that $F_N$ and $L_N$ are unlikely to have non-empty intersection. On the other hand, if an $N$ exists for which $\alpha+\beta-1>0$, then the Bernoulli random subset heuristic suggests that $F_N$ and $L_N$ are likely to have non-empty intersection.
