EXPANDED ABSTRACT of the paper

“Estimating the counts of Carmichael and Williams numbers with small multiple seeds”,

Math. Comp., 84:291 (2015), 309-337.

by Zhenxiang Zhang

Let b_i be the ith prime and let

(1) L = ∏_{1 ≤ i ≤ s} b_i ^ei

with s ≥ 2, e_i ≥ 1 for i ∈ {1, s} and e_i ≥ 0 for 1 < i < s.

Define the set D (L) = {d ∈ Z⁺ : 2 | d; d | L}, which is the set of even divisors of L.

Define sets P (L) = {prime p : p − 1 ∈ D (L); p ∤ L};

N (L) ={n > 1 : n is square-free and composed entirely of the primes in P (L) };

and

C (L) = {n ∈ N (L) : L | n − 1; n −1 ≠ L if L + 1 is prime}.

Then every number n ∈ C (L) is Carmichael.

In 1977 Williams asked that whether there are any Carmichael numbers n with an odd number of prime divisors and the additional property that for each prime p | n,

(2) p + 1 | n + 1.

In 2007 Echi omitted the phrase “with an odd number of prime divisors” to relax the Williams question. Echi then said: “This is a long standing open question; and it is possible that there is no such number.” So, he extended the problem of Williams: he called a square-free composite n an a-Williams number if p−a | n−a and p+a | n+a for all primes p dividing n, where a is a given nonzero integer. In 2010 Bouall`egue, et al. found some a-Williams numbers n < 10⁸, with a ≈ n/3. In contrast to Echi, we believe that there should be infinitely many Carmichael numbers satisfying (2). We call such Carmichael numbers Williams numbers (which are 1-Williams numbers by Echi), though so far not a single Williams number has been found.

Let L be as defined in (1). Let

L⁽¹⁾ = 2 ∏_{2 ≤ j ≤ s, j even} b_j ^ej

and

L⁽²⁾ = ∏_{1 ≤ j ≤ s, j odd} b_j ^ej

Let

Q (L) ={prime q : q − 1 ∈ D (L⁽¹⁾), q + 1 ∈ D (L⁽²⁾); q ∤ L},

N’(L) ={n > 1 : n is square-free and composed entirely of the primes in Q (L) },

C’(L) ={n ∈ N’(L) : L⁽¹⁾ | n − 1},

and

W (L) ={n ∈ C’ (L) : L⁽²⁾| n + 1} = {n ∈ N’ (L) : L⁽¹⁾ | n – 1, L⁽²⁾| n + 1}.

Then every number n ∈ W (L) is Williams. In this paper, we evaluate both |C (L)| and |W (L)| for general (non-square-free) L. We call L an even-divisors-optimal number (EDON) if it has more even divisors than any number less than L. We give some reasons and certain numerical evidence to support the following conjectures, where ω(L) is the number of different prime divisors of L.

Conjecture 1. For an EDON L with ω(L) = s, we have log₂ log₂|C (L)| = s(1+o(1)).

Conjecture 2. For an EDON L with ω(L) = s, we have log₂ log₂|W (L)| =s ^1/2−o(1).

Our reasons for making Conjectures 1 and 2 are mainly based on the heuristics of ErdÖs, Alford, Granville, and Pomerance concerning ErdÖs’s construction of Carmichael numbers and based on Theorem 1.

Theorem 1. If L is an EDON withω(L) = s, then we have

L < 2 (b_s+1)^2s and |D (L)| = 2^s(1+o(1)).

In §3 we prove Theorem 1. In §4 we describe an algorithm, based on Theorem 1, to generate EDONs and tabulate some of them with relative values which are necessary for next sections. In §5, we give numerical evidence to support Conjecture 1. By an adaptation of the procedure described in §2 of our 2011 paper for computing |C (L)| for a square-free L to compute |C (L)| for a general non-square-free L, we find that

|C (L)| = 243222 … 969349 (112 digits)

which seems currently to be the largest known cardinality of a set of Carmichael numbers, where

L = 735134400 = 2⁶ · 3³ · 5² · 7 · 11 · 13 · 17

is the largest EDON less than 10⁹ . In §6, we describe procedures for obtaining numerical evidence of |Q (L)| to support Conjecture 2. We exhibit such EDONs L that W (L) might be non-empty. In §7,we tabulate a table of 1029 primes, and establish that there are at least 2²⁴ Williams numbers made up from them, thought we have not yet actually found any Williams number. We state the difficulties for explicitly finding Williams numbers, and predict what a Williams number looks like. (download the txt file of the 1029 primes)

2022-1-18