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

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

by Zhenxiang Zhang

Let bi be the ith prime and let

(1)         L = 1 ≤ i s bi ei

with s 2, ei 1 for  i {1, s} and ei 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) };


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  pa | na 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 < 108, 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(1) = 2  2 ≤ j s, j even bj ej


L(2) =  1 ≤ j s, j odd  bj ej


Q (L) ={prime q : q 1 D (L(1)),  q + 1 D (L(2));  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(1) | n 1},


W (L) ={n C (L) : L(2)| n + 1} = {n N (L) : L(1) | n 1, L(2)| 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  log2 log2|C (L)| = s(1+o(1)).

Conjecture 2. For an EDON L with  ω(L) = s, we have   log2 log2|W (L)| =s 1/2o(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  (bs+1)2s   and   |D (L)| = 2s(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 = 26 · 33 · 52 · 7 · 11 · 13 · 17

is  the largest  EDON  less  than  109 .    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 224 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)