### Pseudoprimes: construction methods

In this post we're going to look at several methods for generating various kinds of pseudoprimes and we're also listing some open-problems that motivate the generation of such numbers.

## # Introduction

A composite number that passes a certain compositeness tests, is called a pseudoprime to that test.

## # Fermat pseudoprimes

Definition: a Fermat pseudoprime to base b is a composite number n such that b^(n-1) ≡ 1 mod n with gcd(b,n) = 1.

Let f_b(n) be the multiplicative order of b modulo n, defined as the smallest positive integer k such that b^k ≡ 1 mod n.

If n is composite and f_b(n) | n-1, then n is a Fermat pseudoprime to base b.

For a prime number p with gcd(b,p) = 1, the multiplicative order f_b(p) is the smallest divisor d of p-1 that satisfy b^d ≡ 1 mod p.

If n is squarefree with prime factorization n = p_1*p_2*...*p_k and gcd(n,b) = 1, then

f_b(n) = lcm(f_b(p_1), f_b(p_2), ..., f_b(p_k))

#### ## Fermat pseudoprimes with k prime factors

A recursive method for generating all the squarefree Fermat pseudoprimes to base b, that are coprime to b, in a given range [A,B] with exactly k prime factors:

Define the function F(m, \lambda, s, k) as:
1. If k = 1, then iterate over the primes p in the range [\max(s, ceil(A/m)), floor(B/m)].
•   If \lcm(\lambda, f_b(p)) divides m p - 1, then m p is a Fermat pseudoprime to base b.
2. If k >= 2, then iterate over the primes p in the range [s, (B/m)^(1/k)].
• For values of p coprime to b with \gcd(m, f_b(p)) = 1, recursively call the F function as F(m p, \lcm(\lambda, f_b(p)), p+1, k-1).

Now we can call the function as F(1, 1, 2, k), for some integer value of k >= 2.

Optimization: for the case when k=1, rather than iterating over all the primes in the range [\max(s, ceil(A/m)), floor(B/m)], we can iterate only over the primes x, in the same range, that satisfy the following congruence:

m x ≡ 1 mod \lambda

The solutions to x have the form: r + j \lambda, for integers j >= 0, where r = m^(-1) mod \lambda.

#### ## Construction of superpseudoprimes to base b

If n = p_1*p_2*...*p_k and f_b(n) | gcd(p_1-1, p_2-1, ..., p_k-1), then n is a superpseudoprime to base b, satisfying b^d ≡ b mod n for all divisors d|n.

The following method can be used for constructing superpseudoprimes to base b, by grouping primes together, indexed by the divisors d|p-1 such that b^d ≡ 1 mod p, which is equivalent with f_b(p) | d:
1. Let p be a prime with gcd(b,p) = 1.
2. Let k = f_b(p) be the multiplicative order of b modulo p.
3. Iterate over the positive divisors d | p-1.
4. If k|d, store p in a dictionary array indexed by key d.
Apply the above steps for many distinct primes p.
• From each array in the dictionary with at least 2 elements, create combinations of primes.
• The product of each combination is a superpseudoprime to base b.

Example:

Let b = 2 and p = 31, for which k = f_2(31) = 5 and the divisors d|p-1 such that k|d <=> b^d ≡ 1 mod p, are given by the set S = {5, 10, 15, 30}.

For each d \in S, we create an array inside a dictionary, indexed by key d, appending p into that array:

G(5) = {31}
G(10) = {31}
G(15) = {31}
G(30) = {31}

Next, if we take p = 11, the set of divisors d|p-1 such that b^d ≡ 1 mod p, is {10}.

Following the fourth step, we append p = 11 into the array indexed by key d = 10:

G(10) = {31, 11}

in which we now have two elements.

By definition, the product of this array should be a superpseudoprime to base 2, which indeed it is: 11 * 31 = 341 (cf. A050217).

Continuing this process with more primes, allows us to construct more superpseudoprimes.

#### ## Construction of overpseudoprimes to base b

An overpseudoprime n to base b satisfies the following property: f_b(n) = f_b(p) for all prime p|n. For b = 2, the sequence of overpseudoprimes to base 2 includes the composite Mersenne numbers and the composite Fermat numbers.

The method for generating superpseudoprimes can be easily modified to generate overpseudoprimes (cf. A141232) to base b, grouping primes together by f_b(p). Then for each group of primes that have the same multiplicative order, the product of each combination of primes is an overpseudoprime to base b.

Example:

Let b = 2 and p = 23, for which k = f_2(23) = 11. Storing the prime inside the dictionary of arrays indexed by the key k = 11, we have:

G(11) = {23}

If we now take p = 89, we have k = f_2(89) = 11, giving us:

G(11) = {23, 89}

where their product is an overpseudoprime to base 2.

For increasing the chances of collision, one trick would be to use the prime factors p of b^k-1 for many small integers k.

## # Carmichael numbers

Definition: a Carmichael number is a Fermat pseudoprime to all bases b>=2 with gcd(b,n) = 1.

If the prime factorization of n is known, then it can be proven if n is indeed a Carmichael number by checking Korselt's criterion, which states that n is a Carmichael number iff n is square-free and for each prime factor p|n => p-1 | n-1.

For example, let's assume n is a square-free composite integer: n = p_1 * p_2 * ... * p_k.
We want to show that b^(n-1) ≡ 1 mod n for any b coprime to n.

It suffices to show that for any prime p dividing n:

b^(n-1) ≡ 1 mod p

By Fermat's little theorem, b^(p - 1) ≡ 1 mod p for any prime number p with gcd(b,p) = 1. Therefore, if n-1 is a multiple of p-1, for every prime p|n, then the above statement is true, since, if n - 1 = (p-1) * m, we have:

b^((p-1) * m) ≡ (b^(p-1))^m ≡ 1^m ≡ 1 mod p

Additionally, all the divisors of a Carmichael numbers, are cyclic numbers, such as d|n => gcd(\phi(d), d) = 1.

#### ## Carmichael numbers with k prime factors

A recursive method for generating all the Carmichael numbers in a given range [A,B] with exactly k prime factors:

Define the function F(m, \lambda, s, k) as:
1. If k = 1, then iterate over the primes p in the range [\max(s, ceil(A/m)), floor(B/m)].
•   If \lcm(\lambda, p-1) divides m p - 1, then m p is a Carmichael number.
2. If k >= 2, then iterate over the primes p in the range [s, (B/m)^(1/k)].
• For values of p with \gcd(m, p-1) = 1, recursively call the F function as F(m p, \lcm(\lambda, p-1), p+1, k-1).

Now we can call the function as F(1, 1, 3, k), for some integer value of k >= 3.

Optimization: for the case when k=1, rather than iterating over all the primes in the range [\max(s, ceil(A/m)), floor(B/m)], we can iterate only over the primes x, in the same range, that satisfy the following congruence:

m x ≡ 1 mod \lambda

The solutions to x have the form: r + j \lambda, for integers j >= 0, where r = m^(-1) mod \lambda.

Additionally, the largest prime factor of Carmichael numbers less than n, is at most (1+\sqrt(8n+1))/4.

#### ## Erdős construction method

In 1992, Paul Erdős sketched an interesting method for generating Carmichael numbers, based on the following observation: if n is composite and \lambda(n) | n-1, then n is a Carmichael number, where \lambda(n) is the Carmichael lambda function.

If n is a square-free integer n = p_1*p_2*...*p_k, then \lambda(n) = lcm(p_1-1, p_2-1, ..., p_k-1).

#### ### Algorithm

• Choose an even lambda value L with many divisors.
• Let P be the set of odd primes p, such that p-1|L and p∤L.
• Find a subset S of P such that \prod_{p \in S} p ≡ 1 mod L
Then n = \prod_{p \in S} p is a Carmichael number, since L | n-1 and p-1|L for every p|n.

• Alternatively, find a subset T of P such that \prod_{p \in T} p ≡ \prod_{p \in P} p mod L.

Then n = \frac{\prod_{p \in P} p}{\prod_{p \in T} p} is a Carmichael number.

When generating Carmichael numbers with many prime factors, the second approach should be preferred.

Several interesting papers on the generation of Carmichael numbers, include:

### ## Multiples of multiplicative order

Let n be a Fermat pseudoprime to base b.
1. Let k = f_b(n) be the multiplicative order of b modulo n.
2. Iterate over the divisors d of (n-1)/k.
3. If p = k d + 1 is prime and gcd(n,p) = 1, then n p is a new Fermat pseudoprime to base b.
This method can be used for constructing larger Fermat pseudoprimes from a list of already known Fermat pseudoprimes.

For generating Carmichael numbers from a given Carmichael number n:
1. Let k = \lambda(n).
2. Iterate over the divisors d of (n-1)/k.
3. If p = k d + 1 is prime and gcd(n,p) = 1, then n p is a new Carmichael number.
The method can also be applied recursively on the newly generated pseudoprimes, rapidly creating larger and larger numbers.

### ## Chernick-Carmichael numbers

In 1939, Jack Chernick proved that, for n >= 3 and m >= 1:

U_n(m) = (6m + 1) (12m + 1) \prod_{k=1}^(n-2) (2^k * 9m + 1)

is a Carmichael number if all the factors in parentheses are prime numbers and m is a multiple of 2^(n-4) when n >= 5. Furthermore, m is also a multiple of 5 when n >= 6 (otherwise one of the factors is a multiple of 5).

For n=3, this means that if we can find a value of m such that a, b and c are all prime numbers:

a = 6m + 1
b = 12m + 1
c = 18m + 1

then the product a b c is a Carmichael number.

The OEIS sequence A318646 by Amiram Eldar gives the smallest Chernick-Carmichael number with n prime factors.

At the moment of writing, no Chernick-Carmichael number with 12 (or more) prime factors is known. If such a number exist, then for all n >= 12, we have m > 8 * 10^15.

Under the assumption of Schinzel's hypothesis H, there should exist infinitely many Chernick-Carmichael numbers with n prime factors, for any n >= 3.

## # Lucas-Carmichael numbers

A Lucas-Carmichael number is defined as an odd square-free integer satisfying p+1|n+1 for every p|n.

For a Lucas-Carmichael number n = p_1*p_2*...p_k, its corresponding lambda value is defined as:

L = lcm(p_1+1, p_2+1, ..., p_k+1)

If n is an odd square-free integer and L|n+1, then n is a Lucas-Carmichael number.

#### ## Lucas-Carmichael numbers with k prime factors

A recursive method for generating all the Lucas-Carmichael numbers in a given range [A,B] with exactly k prime factors:

Define the function F(m, \lambda, s, k) as:
1. If k = 1, then iterate over the primes p in the range [\max(s, ceil(A/m)), floor(B/m)].
•   If \lcm(\lambda, p+1) divides m p + 1, then m p is a Lucas-Carmichael number.
2. If k >= 2, then iterate over the primes p in the range [s, (B/m)^(1/k)].
• For values of p with \gcd(m, p+1) = 1, recursively call the F function as F(m p, \lcm(\lambda, p+1), p+1, k-1).

Now we can call the function as F(1, 1, 3, k), for some integer value of k >= 3.

Optimization: for the case when k=1, rather than iterating over all the primes in the range [\max(s, ceil(A/m)), floor(B/m)], we can iterate only over the primes x, in the same range, that satisfy the following congruence:

m x ≡ -1 mod \lambda

The solutions to x have the form: r + j \lambda, for integers j >= 0, where r = -1 * m^(-1) mod \lambda.

Additionally, the largest prime factor of Lucas-Carmichael numbers less than n, is at most \sqrt(n+1)-1.

#### ## Erdős construction method modified for Lucas-Carmichael numbers

Lucas-Carmichael numbers can be constructed using a modified version of Erdős's method:
• Pick an even lambda value L with many divisors.
• Let P be the set of odd primes p, such that p+1|L and p∤L.
• Find a subset S of P such that \prod_{p \in S} p ≡ -1 mod L
Then n = \prod_{p \in S} p is a Lucas-Carmichael number, since L|n+1 and p+1|L for every p|n.
• Alternatively, find a subset T of P such that \prod_{p \in T} p ≡ -\prod_{p \in P} p mod L.
Then n = \frac{\prod_{p \in P} p}{\prod_{p \in T} p} is a Lucas-Carmichael number.

Open problem: find a Carmichael number that is also a Lucas-Carmichael number.

The OEIS sequence A329948 lists Carmichael numbers n that contain at least 3 prime factors p|n satisfying p+1|n+1. Larger terms can be found here.

Similarly, A335336 lists Carmichael numbers n with the greatest prime factor p|n satisyfing p+1|n+1. Larger terms can be found here.

## # Lucas pseudoprimes

A Lucas \Delta-pseudoprime to the Lucas sequence U_n(P,Q), for \Delta = P^2-4Q, is a composite number n such that:

\U_(n-\epsilon(n))(P,Q) ≡ 0 mod n

where \epsilon(n) = (\Delta/n) is the Kronecker symbol.

Similarly, a \Delta-pseudoprime to the Lucas sequence V_n(P,Q), satisfies:

V_n(P,Q) ≡ P mod n

In both cases, \Delta must not be a perfect square.

Let n = p_1 * p_2 * ... * p_k and \Delta be a non-square integer. We then define the Lucas-lambda value of n as:

U_L = lcm(U_\Delta(p_1), U_\Delta(p_2), ..., U_\Delta(p_k))

where U_\Delta(p) is the smallest divisor d of p-\epsilon(p) satisfying U_d(P,Q) ≡ 0 mod p.

For a square-free composite integer n, if U_L divides n - \epsilon(n), then n is a Lucas \Delta-pseudoprime to the U sequence. The converse is also true.

L = lcm(p_1 - \epsilon(p_1), p_2 - \epsilon(p_2), ..., p_k - \epsilon(p_k))

This value is useful in creating new Lucas pseudoprimes from a list of Lucas pseudoprimes, using Erdős's method described below.

### ## Erdős method

For generating \Delta-pseudoprimes to the Lucas U sequence, we present a modified version of Erdős's method:
• Pick an even lambda value L with many divisors.
• Let P be the set of odd primes p, such that p-\epsilon(p)|L and p∤L.
• Find a subset S of P such that n = \prod_{p \in S} p satisfies U_n(P,Q) ≡ 0 mod n.
Then n is a Lucas \Delta-pseudoprime. Optionally, we can restrict \epsilon(n) = -1.

### ## Prime-grouping method

An alternative method would be to group primes based on their d | p-\epsilon(p) with U_d(P,Q) ≡ 0 mod p.
1. Let p be a prime number with gcd(\Delta, p) = 1.
2. Iterate over the divisors d of p-\epsilon(p).
3. If \U_d(P,Q) ≡ 0 mod p, store the prime p in group d.
Repeat the above steps for many different primes p, then find groups that contain at least 2 primes. The product of any combination of primes in such groups, is a Lucas \Delta-pseudoprime to the U sequence.

## # Open problems

This section includes several pseudoprime-related open-problems and challenges.

### ## Abundant Fermat pseudoprimes

On 17 December 2017, Shyam Sunder Gupta published the following problem on their website: "Can you find the smallest abundant number which is also pseudoprime (base-2)?".

I first heard about the problem on 25th October 2019 from Amiram Eldar's interesting sequence A328691.

After trying different techniques, on 09th November 2019, I finally "cracked" the problem, generating 42 abundant Fermat pseudoprimes to base 2, the smallest one in my list being the following 40-digit number:

3470207934739664512679701940114447720865

Meanwhile, I generated a few more abundant pseudoprimes to base 2, which can be found here.

Update (28 August 2022): using a new idea, I generated two smaller abundant Fermat pseudoprimes to base 2:

2596282479202818734176082185090403265
12796625128232187655293894634808130945

Update (10 March 2023): using the same idea as above, I've found two smaller abundant Fermat pseudoprimes to base 2:

898943937249247967890084629421065
222042825169546323981793629414604065

Challenge: find a smaller abundant Fermat pseudoprime to base 2, or prove that there is no smaller one.

### ## Abundant Carmichael numbers

Inspired by Shyam Sunder Gupta's problem, in A329460, Amiram Eldar asked the question: "Do abundant Carmichael numbers exist?".

On 15th August 2020, I answered the question in positive (source code) by generating the following 97-digit abundant Carmichael number, showing that abundant Carmichael numbers do exist:

2050222770372550554323267720953963601363820698627252818938445687085323309254089582862054255135745

In constructing abundant Carmichael numbers, one important idea (source code) is the following: if a Carmichael number is a multiple of an odd abundant cyclic number, such as:

8177568910636879136524885826320973235
or
17277031840122951876810012573270045985

then it will be abundant.

Since the above multipliers are both odd abundant cyclic numbers and all odd cyclic numbers seem to have Carmichael multiples, suggests that infinitely many abundant Carmichael numbers do exist.

A day later, I constructed a slightly smaller (88-digit) abundant Carmichael number (but, most likely, it's still not the smallest one):

2059832906607460252767290568443059994787898033540634712711845135488141590979778401392385

Challenge: find an abundant Carmichael number divisible by 3.
Open problem: find the smallest abundant Carmichael number.

A list of Carmichael numbers with abundancy index > 1.9 can be found here.

### ## Abundant Lucas-Carmichael numbers

A related question would be: "do abundant Lucas-Carmichael numbers exist?". The answer is "yes"!

For generating abundant Lucas-Carmichael numbers, we used a similar method as in the generation of abundant Carmichael numbers.

First, we generated odd squarefree (almost) abundant numbers k, satisfying gcd(k, \psi(k)) = 1 (source code), where \psi(n) is the Dedekind psi function. Such a number k must be a term of A255602.

Then we used a modified version of Erdős's construction method for Carmichael numbers, adapted to the construction of Lucas-Carmichael numbers (source code) and also with support for using our multiplier k with its corresponding lambda value L.

The smallest abundant Lucas-Carmichael number that I was able to find so far, is the following 70-digit number:

1012591408428327888883952080728349448745451794025524955777432246705535

It is conjectured that every term of A255602 is a divisor of a Lucas-Carmichael number. The smallest such multiples are given in A253598. If the conjecture is true, then there exists infinitely many abundant Lucas-Carmichael numbers, as the A255602 sequence includes infinitely many abundant terms.

Challenge: find an abundant Lucas-Carmichael number divisible by 3.
Open problem: find the smallest abundant Lucas-Carmichael number.

Several upper-bounds to A253598 are listed here.

In collaboration with Amiram Eldar, we submitted the OEIS sequence A356821, which lists the Lucas-Carmichael numbers  k that have an abundancy index \frac{sigma(k)}{k} that is larger than the abundancy indices of all smaller Lucas-Carmichael numbers.

A list of Lucas-Carmichael numbers with abundancy index > 1.9 is available here.

### ## Lucas-Carmichael-Fermat pseudoprimes

Challenge: find a Lucas-Carmichael number with (5/n) = -1 that is also a Fermat pseudoprime to some base b >= 2.

### ## Lehmer's totient problem

Lehmer's totient problem asks whether there exists any composite integer n such that Euler's totient function \phi(n) divides n-1.

In other words, we are looking for a composite integer n for which the following equation holds for some integer k:

k * \phi(n) = n-1

Furthermore, we call k the Lehmer index of n. Lehmer showed that if such a number exists, then it must be a Carmichael number divisible by at least 7 distinct primes.

In 1980, Cohen and Hagis built upon the result of Lehmer, showing that any such n must have at least 14 distinct primes and must be greater than 10^20.

Up to 10^20, the Carmichael number 171800042106877185 has the largest Lehmer index of 2.2349... (see also A329460).

A list of Carmichael numbers greater than 2^64 having a Lehmer index greater than 2, can be found here.

### ## Pseudoprimes to the Baillie-PSW primality test

The Baillie-PSW primality test is a combination of two tests: a Miller-Rabin test to base 2 and a strong (or extra-strong) Lucas test with a carefully chosen discriminant \Delta such that (\Delta/n) = -1.

Since its publication in 1980, no composite number passing the test has been found, not even if the test is weakened to use a regular Fermat test to base 2.

However, an heuristic argument of Carl Pomerance (paper), suggests that there should exist infinitely many counter-examples to the Baillie-PSW test.

Open problem: find a Fermat pseudoprime n to base 2 such that U_(n+1)(P,-1) ≡ 0 mod n, where P is the smallest positive integer P >= 1 satisfying ((P^2 + 4)/n) = -1.

The special case, with P = 1 and (5/n) = -1, is called the PSW conjecture and has a prize tag of \$620 for the first counter-example, or for a proof that no such number exists.

Carl Pomerance showed that if an odd square-free composite number n = p_1 * p_2 * ... * p_k satisfies the following conditions, then it would be a counter-example to the Baillie-PSW primality test:
• Let T and k >= 5 be fixed integers.
Then, for each prime p|n:
• T < p < T^k
• p ≡ 3 mod 8 and (5/p)=-1.
• (p-1)/2 and (p+1)/4 are both square-free and T-smooth.
• each prime factor q of (p-1)/2 satisfy q ≡ 1 mod 4 and q < T.
• each prime factor q of (p+1)/4 satisfy q ≡ 3 mod 4  and q < T.
Such a number would simultaneously be a Carmichael number, a Lucas-Carmichael number, a strong Fermat pseudoprime to base 2 and a Lucas pseudoprime for any Lucas test with discriminant \Delta = 5.

Jon Grantham compiled a list of 2030 primes (A018188) in which the author strongly believes that some sub-product of those primes is a counter-example to the PSW conjecture.

The above conjecture implies that there exists a counter-example to the BPSW test smaller than 10^25286 (Charles R Greathouse IV, 2019). However, finding such a subset is computationally infeasible, assuming that such a subset exists.

### ## Agrawal's conjecture

In the article Remarks on Agrawal's conjecture, Hendrick Lenstra showed that if a Carmichael number, with an odd number of prime factors p|n => p ≡ 3 mod 80, is also a Lucas-Carmichael number, then it would be a counter-example to Agrawal's conjecture (cf. A329223).

Currently, only the following such Carmichael numbers are known, but none of them is also a Lucas-Carmichael number:

330468624532072027 = 2003 * 574003 * 287432003
1358406397003392026912594827 = 47051443 * 3811166803 * 7575282163
194462892367341977828363075381947 = 1571719603 * 22527980963 * 5492112195923

More Fermat pseudoprimes to base 2 with these properties, can be found here.

## # Upper-bounds to some interesting sequences in the OEIS

In this section we list some upper-bounds to some pseudoprime-related sequences in the OEIS.

### ## Smallest anti-Carmichael Fermat psp-2 with n prime factors

Thomas Ordowski defined the following interesting sequence: a(n) = A316908(n) is the smallest k with n prime factors such that 2^(k-1) ≡ 1 mod k and p-1 does not divide k-1 for every prime p dividing k.

a(9) <= 797365221484475174021
a(10) <= 1315856103949347820015303981
a(11) <= 6357507186189933506573017225316941
a(12) <= 77822245466150976053960303855104674781
a(13) <= 42864570625001423761497389323695509974049581
a(14) <= 34015651529746754841597629769101132590516759547941
a(15) <= 53986954871543199290951271756765558658193549930487667861

More upper-bounds can be found here.

### ## Smallest imprimitive Carmichael number with n prime factors

Amiram Eldar defined the following interesting sequence: a(n) = A328938(n) is the smallest imprimitive Carmichael number with n prime factors.

An imprimitive Carmichael number is defined to be a Carmichael number, n = p_1 * p_2 * ... * p_k, such that:

gcd(p_1 - 1, p_2 - 1, ..., p_k - 1)^2 > lcm(p_1 - 1, p_2 - 1, ..., p_k - 1)

The list of imprimitive Carmichael numbers is given by A328935.

a(8) <= 1717329690048308373193368241
a(9) <= 3267914929260691848833226795711841
a(10) <= 9826697385996014043286435094944561164001
a(11) <= 325533792014488126487416882038879701391121
a(12) <= 1605045791181700950034233564955898780122791301414374937801
a(13) <= 1802188215375086135161896807172372148518756613537876342449815601
a(14) <= 37301957856686414877340399600312307212530668530569712518803959550606029812859921
a(15) <= 111752741147928878460543122185614013584493764844954493341714777557828905006762368931787841

More upper-bounds can be found here.

### ## Smallest strong pseudoprime to base 2  with n prime factors

The sequence A180065 lists the smallest strong pseudoprime to base 2 with n prime factors.

Some terms and upper-bounds (> 2^64) for this sequence include:

a(11) = 24325630440506854886701
a(12) = 27146803388402594456683201
a(13) = 4365221464536367089854499301
a(14) = 2162223198751674481689868383601
a(15) = 548097717006566233800428685318301
a(16) <= 431963846549014459308449974667236801
a(17) <= 1554352698725568399952746943189797571201
a(18) <= 2095080420396817592160909089382002325129301
a(19) <= 1085479319509324324097609405158976672897141701

More upper-bounds can be found here.

### ## Smallest superpseudoprime to base 2 with n prime factors

Submitted by Amiram Eldar, the sequence a(n) = A328665(n) lists the smallest superpseudoprime to base 2 with n prime factors.

Some upper-bounds for this sequence, include:

a(7) <= 1842158622953082708177091
a(8) <= 192463418472849397730107809253922101
a(9) <= 1347320741392600160214289343906212762456021
a(10) <= 70865138168006643427403953978871929070133095474701
a(11) <= 3363391752747838578311772729701478698952546288306688208857
a(12) <= 132153369641266990823936945628293401491197666138621036175881960329
a(13) <= 9105096650335639994239038954861714246150666715328403635257215036295306537
a(14) <= 7605797846771738682631804190686245080923244102451432651379391224410677241944951032625821

More upper-bounds can be found here.

### ## Smallest overpseudoprime to base 2  with n prime factors

The sequence a(n) =  A353409(n) lists the smallest overpseudoprime to base 2 with n prime factors.

Only 3 terms exist <= 2^64:

a(2) = 2047
a(3) = 13421773
a(4) = 14073748835533

Some upper-bounds for this sequence, include:

a(5) <= 1376414970248942474729
a(6) <= 48663264978548104646392577273
a(7) <= 294413417279041274238472403168164964689
a(8) <= 98117433931341406381352476618801951316878459720486433149
a(9) <= 1252977736815195675988249271013258909221812482895905512953752551821

More upper-bounds can be found here.

### ## Smallest Carmichael strong pseudoprime to base 2 with n prime factors

The sequence a(n) =  A356866(n) lists the smallest strong pseudoprime to base 2 with n prime factors that is also a Carmichael number.

The first 13 terms are:

a(3) = 15841
a(4) = 5310721
a(5) = 440707345
a(6) = 10761055201
a(7) = 5478598723585
a(8) = 713808066913201
a(9) = 1022751992545146865
a(10) = 5993318051893040401
a(11) = 120459489697022624089201
a(12) = 27146803388402594456683201
a(13) = 14889929431153115006659489681

Several upper-bounds include:

a(14) <= 12119528395859597855693434006201
a(15) <= 45989156618415671982294689977060801
a(16) <= 431963846549014459308449974667236801
a(17) <= 1554352698725568399952746943189797571201
a(18) <= 8836650128005495946439182680127795429976001
a(19) <= 4590172857833958394304163760489663619756066401

More upper-bounds can be found here.

### ## Smallest Carmichael superpseudoprime to base 2 with n prime factors

In 2017, Max Alekseyev and Thomas Ordowski submitted the A291637 sequence, which lists the Carmichael numbers that are also superpseudoprimes to base 2.

A list of terms with 5 or more prime factors, can be found here.

Letting a(n) to be the smallest such number with n prime factors, we have:

a(3) = 294409
a(4) = 3018694485093841

By using the tables of pseudoprimes up to 2^64, we find that a(5) > 2^64.

a(5) <= 521635331852681575100906881
a(6) <= 2835402730651853232634509813787097410561
a(7) <= 165784025660216242122027716057592895796242004385542265601

More upper-bounds can be found here.

### ## Smallest Carmichael overpseudoprime to base 2  with n prime factors

The sequence A352987 lists the Carmichael numbers that are also overpseudoprimes to base 2.

A list of terms with 4 or more prime factors, can be found here

Letting a(n) to be the smallest such number with n prime factors, we have:

a(3) = 65700513721
a(4) <= 84286331493236478328609
a(5) <= 3157343757823970959759947380425728583752001

More upper-bounds can be found here.

## # Source-code implementations

This section includes source-code implementation of the presented methods for generating various pseudoprimes.

Several more experimental programs for generating pseudoprimes, can be found here.