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:

• Constructing Carmichael numbers through improved subset-product algorithms
• Building pseudoprimes with a large number of prime factors
• A new algorithm for constructing large Carmichael numbers
• Constructing Carmichael numbers which are strong pseudoprimes to several bases

## 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.

Additionally, we define:

`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.

Sidef:

• Carmichael numbers in range
• Carmichael strong Fermat pseudoprimes in range
• Carmichael generation Erdos method
• Smallest Carmichael divisible by n
  
• Fermat pseudoprimes in range
  
• Fermat pseudoprimes generation
• Fermat pseudoprimes generation 2
• Fermat pseudoprimes generation 3
• Fermat overpseudoprimes in range
• Strong Fermat pseudoprimes in range
• Squarefree Fermat pseudoprimes in range
• Squarefree strong Fermat pseudoprimes in range
  
• Squarefree Fermat overpseudoprimes in range
• Squarefree Lucas U pseudoprimes in range
  
• Fermat overpseudoprimes generation
• Fermat superpseudoprimes generation
  
• Frobenius pseudoprimes generation
• Lucas pseudoprimes generation
• Lucas pseudoprimes generation Erdos method
• Lucas-Carmichael numbers in range
  
• Lucas-Carmichael generation Erdos method
• Smallest Lucas-Carmichael divisible by n
  
• Pomerance condition for B-PSW counter-example

Perl:

• Carmichael numbers in range
• Carmichael numbers in range mpz
  
• Carmichael numbers in range from prime factors 
• Carmichael numbers generation Erdos method
• Carmichael strong Fermat pseudoprimes in range
  
• Smallest Carmichael divisible by n
• Fermat pseudoprimes in range
• Fermat pseudoprimes in range mpz 
• Fermat pseudoprimes generation 
• Fermat pseudoprimes generation 2 
• Fermat pseudoprimes generation 3
• Fermat overpseudoprimes in range
• Strong Fermat pseudoprimes in range
• Strong Fermat pseudoprimes in range mpz 
• Squarefree Fermat pseudoprimes in range
• Squarefree Fermat pseudoprimes in range mpz
  
• Squarefree strong Fermat pseudoprimes in range 
• Squarefree strong Fermat pseudoprimes in range mpz
  
• Squarefree Fermat overpseudoprimes in range
• Squarefree Lucas U pseudoprimes in range 
• Fermat overpseudoprimes generation
• Fermat superpseudoprimes generation
• Fibonacci pseudoprimes generation
• Frobenius pseudoprimes generation
• Lucas-Carmichael numbers in range
• Lucas-Carmichael numbers in range mpz
• Lucas pseudoprimes generation
• Lucas pseudoprimes generation Erdos method
• Lucas-Carmichael numbers in range from prime factors
  
• Smallest Lucas-Carmichael divisible by n 
• Random Carmichael Fibonacci pseudoprimes
• Random Miller-Rabin pseudoprimes

 Julia:

• Carmichael numbers in range
• Chernick-Carmichael numbers
  
• Fermat pseudoprimes generation
  
• Lucas-Carmichael numbers in range
• Squarefree Fermat pseudoprimes in range

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