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 bn-1 1modn with gcd(b,n)=1.

Let fb(n) be the multiplicative order of b modulo n, defined as the smallest positive integer k such that bk1modn.

If n is composite and fb(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 fb(p) is the smallest divisor d of p-1 that satisfy bd1modp.

If n is squarefree with prime factorization n=p1p2...pk and gcd(n,b)=1, then

fb(n)=lcm(fb(p1),fb(p2),...,fb(pk))

## 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,λ,s,k) as:
  1. If k=1, then iterate over the primes p in the range [max(s,Am),Bm].
    •   If lcm(λ,fb(p)) divides mp-1, then mp is a Fermat pseudoprime to base b.
  2. If k2, then iterate over the primes p in the range [s,(Bm)1k]
    • For values of p coprime to b with gcd(m,fb(p))=1, recursively call the F function as F(mp,lcm(λ,fb(p)),p+1,k-1).

Now we can call the function as F(1,1,2,k), for some integer value of k2.
 
Optimization: for the case when k=1, rather than iterating over all the primes in the range [max(s,Am),Bm], we can iterate only over the primes x, in the same range, that satisfy the following congruence:

mx1modλ

The solutions to x have the form: r+jλ, for integers j0, where r=m-1modλ.

## Construction of superpseudoprimes to base b

If n=p1p2...pk and fb(n)gcd(p1-1,p2-1,...,pk-1), then n is a superpseudoprime to base b, satisfying bdbmodn for all divisors dn.

The following method can be used for constructing superpseudoprimes to base b, by grouping primes together, indexed by the divisors dp-1 such that bd1modp, which is equivalent with fb(p)d:
  1. Let p be a prime with gcd(b,p)=1.
  2. Let k=fb(p) be the multiplicative order of b modulo p.
  3. Iterate over the positive divisors dp-1.
  4. If kd, 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=f2(31)=5 and the divisors dp-1 such that kdbd1modp, are given by the set S={5,10,15,30}.

For each dS, 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 dp-1 such that bd1modp, 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: 1131=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: fb(n)=fb(p) for all prime pn. 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 fb(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=f2(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=f2(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 bk-1 for many small integers k.

# Carmichael numbers

Definition: a Carmichael number is a Fermat pseudoprime to all bases b2 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|np-1|n-1.

For example, let's assume n is a square-free composite integer: n=p1p2...pk.
We want to show that bn-11modn for any b coprime to n.

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

bn-11modp

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

b(p-1)m(bp-1)m1m1modp

Additionally, all the divisors of a Carmichael numbers, are cyclic numbers, such as dngcd(ϕ(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,λ,s,k) as:
  1. If k=1, then iterate over the primes p in the range [max(s,Am),Bm].
    •   If lcm(λ,p-1) divides mp-1, then mp is a Carmichael number.
  2. If k2, then iterate over the primes p in the range [s,(Bm)1k]
    • For values of p with gcd(m,p-1)=1, recursively call the F function as F(mp,lcm(λ,p-1),p+1,k-1).

Now we can call the function as F(1,1,3,k), for some integer value of k3.
 
Optimization: for the case when k=1, rather than iterating over all the primes in the range [max(s,Am),Bm], we can iterate only over the primes x, in the same range, that satisfy the following congruence:

mx1modλ

The solutions to x have the form: r+jλ, for integers j0, where r=m-1modλ.
 
Additionally, the largest prime factor of Carmichael numbers less than n, is at most 1+8n+14.
 

## Erdős construction method

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

If n is a square-free integer n=p1p2...pk, then λ(n)=lcm(p1-1,p2-1,...,pk-1).

### Algorithm

  • Choose an even lambda value L with many divisors.
  • Let P be the set of odd primes p, such that p-1L and p.
  • 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.

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 2017Max 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.

Comments

  1. Hey there Daniel. On a post on YouTube from a few days back under your channel, you asked about whether any progress had been made on the integer factorisation suite of methods I described in a comment on a video about Lenstra's Factorisation Method. I believe, rightly or wrongly, but with good reason, and backed up by irrefutable mathematical logic, that I have indeed developed better methods than those which are in the public domain. I have worked hard over the past year especially to write up my researches. I'm in the final stages of writing up the last sections of what I am able and willing to share publicly. I'm also in the process of beginning to learn C programming properly (I've dabbled before, but never undertaken a serious enough study to make useful programs - hopefully that will change this year - wish me luck! ; - ) ). I just wanted to provide you a link to my work. I'm taking no chances, because a lot of comments I attempt to make on You Tube are either blocked or censored, usually with no good reason. I really hope you will be able to create something useful with the contents of my research work; I am merely the uncoverer of truth, and to me mathematics is the ultimate truth that can never be disputed, refuted or denied in any way. Therefore it's the only truth worth pursuing. I hope you feel at least a little bit the same way about it. Anyway, because I was denied from leaving you a simple comment on You Tube, I had to go into full sleuth mode to work out another channel on which to contact you on. Luckily enough I found this blog of yours, if you wish to communicate further over the next year or so, then it might be useful for me to have your email address. I would post mine here, but I would prefer to remain somewhat anonymous to other prying eyes. Anyway, that's all just possibility for the moment, here is the link to (a small part) of my work:

    https://bit.ly/39VrUax

    If you are interested, then please either leave a comment on YouTube under the Lenstra video, or email me at the following address which is my Googol account email: jmf(One-Zero-Three)@gmail.com Simply remove the brackets and hyphens and insert numbers in place of the number spelt in words, so One would become 1 and Zero 0 for example. Thanks for your time, I look forward to hearing from you.

    PS: You're obviously an accomplished perl programmer; there is a big overlap I feel between mathematics and all programming languages. I have resisted learning to program properly until now because I felt it might have sullied the purity of mathematical thought. Now I am at the final part of research though, I feel it's the right time to learn to program, even just to a basic enough level to computerise the work I've done.

    ReplyDelete

Post a Comment