% This is the revised version submitted to Mathematics of Computation
% with corrections and alterations as suggested by the referee and by
% results that came in over the summer.
%
% Last updated 30 September 1992	Richard Pinch 
\magnification\magstep1
\input amstex

\documentstyle{amsppt}

%\input amshead

% Definitions for this paper only
\def\C(#1){{C\left(#1\right)}}
\def\congruent{\equiv}
\def\divides{\mid}\def\notdivides{\nmid}\def\exdivides{\parallel}
\define\lcm{{\operatornamewithlimits{lcm}}}
\def\sL{{\Cal L}}
\def\sC{{\Cal C}}
\def\O(#1){{\text{O}\left(#1\right)}}
%
\hyphenation{Car-michael}

% We use A4 paper!
\pagewidth{16truecm}\pageheight{23truecm}

\topmatter
\title The Carmichael numbers up to $10^{15}$ \endtitle
\author R.G.E. Pinch \endauthor
\affil Department of Pure Mathematics and Mathematical Statistics, \\
       University of Cambridge \endaffil
\address University of Cambridge,
Department of Pure Mathematics and Mathematical Statistics,
16 Mill Lane, Cambridge  CB2 1SB, U.K. \endaddress
\email {\tt RGEP \@ PHX.CAM.AC.UK} \endemail
\date 30 September 1992 \enddate
\subjclass Primary 11Y99; Secondary 11A51,11Y11\endsubjclass
\abstract
There are 105212 Carmichael numbers up to $10^{15}$: we describe
the calculations.  The numbers were generated by a back-tracking search for
possible prime factorisations, and the computations checked by
searching selected ranges of integers directly using a sieving technique,
together with a ``large prime variation''.

\endabstract
\endtopmatter
\document


\subhead 0.  Introduction \endsubhead

A {\it Carmichael number} $N$ is a composite number $N$ with the property
that for every $x$ prime to $N$ we have $x^{N-1} \congruent 1 \mod N$.
It follows that a Carmichael number $N$
must be square-free, with at least three prime factors, and
that $p-1 \divides N-1$ for every prime $p$ dividing $N$:
conversely, any such $N$ must be a Carmichael number.

For background on Carmichael numbers we refer to Ribenboim \cite{24}
and \cite{25}.  Previous tables of Carmichael numbers
were computed by Pomerance, Selfridge and
Wagstaff \cite{23}, Jaeschke \cite{13}, Guillaume \cite{11}, Keller \cite{14}
and Guthmann \cite{12}.
Yorinaga \cite{28} also obtained many Carmichael numbers.

We have shown that there are 105212 Carmichael numbers up to $10^{15}$,
all with at most 9 prime factors.  Let $\C(X)$ denote
the number of Carmichael numbers less than $X$; let $\C(d,X)$ denote the
number with exactly $d$ prime factors.  Table 1 gives the values
of $\C(X)$ and $\C(d,X)$ for $d \le 9$ and $X$ in powers of 10 up to $10^{15}$.

We have used the same methods to calculate the smallest Carmichael numbers
with $d$ prime factors for $d$ up to 20.  The results are given in Table 2.

It has recently been shown by Alford, Granville and Pomerance \cite{1}
that there are infinitely many Carmichael numbers:
indeed $\C(X) > X^{2/7}$ for sufficiently large $X$.
Their proof is described by Granville \cite{10}.

\subhead 1.  Some properties of Carmichael numbers \endsubhead

In this section we gather together various elementary properties of
Carmichael numbers.  We assume throughout that $N$ is a Carmichael number
with exactly $d$ prime factors, say, $p_1 , \dots , p_d$
in increasing order.

\proclaim{Proposition 1}
Let $N$ be a Carmichael number less than $X$.
\roster
\item
Let $r < d$ and put $P = \prod_{i=1}^r p_i$.  Then $p_{r+1} < (X/P)^{1/(d-r)}$
and $p_{r+1}$ is prime to $p_i - 1$ for all $i \le r$.
\item
Put $P = \prod_{i=1}^{d-1} p_i$
and $L = \lcm\left\lbrace p_1 - 1,\dots,p_{d-1} - 1\right\rbrace$.
Then $Pp_d \congruent 1 \mod L$ and $p_d-1$ divides $P-1$.
\item
Each $p_i$ satisfies $p_i < \sqrt{N} < \sqrt{X}$.
\endroster
\endproclaim
\demo{Proof}
Parts \therosteritem1 and \therosteritem2 follow at once from the fact that
$p_i - 1$ divides $N - 1$ for each $i$.  For part \therosteritem3, consider
the largest prime factor $p_d$.  From \therosteritem2,
$N = Pp_d$ and $p_d-1 \divides P-1$, so that $p_d < P$.  But now
$p_d^2 < Pp_d = N$.
\qed
\enddemo

\proclaim{Proposition 2}
Let $P = \prod_{i=1}^{d-2} p_i$.
There are integers $2 \le D < P < C$ such that, putting $\Delta = C D - P^2$,
we have
\roster
\item
$$
p_{d-1} = { (P-1)(P+D) \over \Delta } + 1 ;
$$
\item
$$
p_d = { (P-1)(P+C) \over \Delta } + 1 ;
$$
\item
$$
P^2 < C D < P^2 \left({p_{d-2}+3 \over p_{d-2}+1} \right) .
$$
\endroster
\endproclaim
\demo{Proof}
For convenience we put $q = p_{d-1}$ and $r = p_d$.
We have $r - 1 \divides P q - 1$ and $q  - 1 \divides P r - 1$; say
$$
D = { P q - 1 \over r - 1 }
$$
and
$$
C = { P r - 1 \over q - 1 } .
$$
Since $q < r$ we have $D < P < C$ and since $Pq \ne r$ we have $D \ne 1$,
that is, $D \ge 2$.
Substituting for $r$ we have
$$
P \left( {{P q - 1} \over D} + 1 \right) - 1 = C \left( q - 1 \right)
$$
and so
%$$
%(C D - P^2) q = PD + CD - P - D = P(D-1) + D(C-1) > 0
%$$
%so that
%$\Delta = C D - P^2 \ge 1$.
%Now
%$$
%\Delta(q-1) = P(D-1) + D(C-1) + CD - P^2 = (P-1)(P+D)
%$$
$$
C D (q-1) = P^2 q - P + P D - D .
$$
Putting $\Delta = C D - P^2$, we have
$$
\Delta(q-1) = (CD-P^2)(q-1) = P^2 - P + PD - D = (P-1)(P+D).
$$
So $\Delta > 0$ and
$$
q = \left( { (P-1)(P+D) \over \Delta } \right) + 1 ;
$$
similarly
$$
r = \left( { (P-1)(P+C) \over \Delta } \right) + 1 .
$$
Now $q \ge p_{d-2} + 2$ and $D < P$, so
$$
p_{d-2} + 1 \le {(P-1)(P+D) \over \Delta} < {2P^2 \over \Delta},
$$
giving
$$
C D - P^2 < P^2 \left( { 2 \over p_{d-2} + 1 } \right)
$$
whence
$$
C D < P^2 \left( { p_{d-2} + 3 \over p_{d-2} + 1 } \right) ,
$$
as required.
\qed
\enddemo

\proclaim{Corollary}
There are only finitely many Carmichael numbers $N = \prod_{i=1}^d p_i$
with a given set of $d-2$ prime factors $p_1,\dots,p_{d-2}$.
\qed
\endproclaim

Parts \therosteritem1 and \therosteritem2 of Proposition 2 are contained in
Satz B(e) of Kn\"odel \cite{15}.  The Corollary was obtained by Beeger \cite{2}
for the case $d = 3$ and by Duparc \cite{9} in general.


\proclaim{Proposition 3}
Let $P = \prod_{i=1}^{d-2} p_i$.  Then
\roster
\item
$$
p_{d-1} < 2P^2 ;
$$
\item
$$
p_d < P^3 .
$$
\endroster
\endproclaim
\demo{Proof}
We use Proposition 2.
Putting $\Delta \ge 1$ and $D < P$ in \therosteritem1 we
have $p_{d-1} < (P-1)(2P) + 1 < 2P^2$.
Putting  $D \ge 2$ and $p_{d-2} \ge 3$ in \therosteritem3 we
have $C \le 3P^2/4$: substituting this in \therosteritem2 we
have $p_d < P^3$, as required.
\qed
\enddemo

A slightly stronger form of this result was obtained by Duparc \cite{9}.

\subhead 2.  Organisation of the search \endsubhead

Assume throughout that $N$ is a Carmichael number less than some
pre-assigned bound $X$ and with exactly $d$ prime factors.  We obtain
all such $N$ as lists of prime factors by a back-tracking search.

We produce successive lists of $p_1,\dots,p_{d-2}$ by looping at
each stage over all the primes permitted by Proposition 1\therosteritem1.

At search level $d-2$ we put $P = \prod_{i=1}^{d-2} p_i$.
If $P$ is small enough then we proceed by using
Proposition 2, looping first over all $D$ in the range $2$ to $P-1$
and then over all $C$ with $C D$ satisfying the inequalities of
Proposition 2\therosteritem3.
For each such pair $(C,D)$, we test whether the values of
$p_{d-1}$ and $p_d$ obtained from 2\therosteritem1 and 2\therosteritem2
are integral and, if so, prime.  Finally we
test whether $N-1$ is divisible by $p_{d-1}-1$ and $p_d-1$.

If the value of $P$ at level $d-2$ is large then we loop over all
values of $p_{d-1}$ permitted by Proposition 1\therosteritem1 and
Proposition 3\therosteritem1.  Now put
$L = \lcm\left\lbrace p_1-1,\dots,p_{d-1}-1 \right\rbrace$.
The innermost loop runs over all primes
$p$ with $Pp \congruent 1 \mod L$ for which $p-1$
divides $P-1$ and which satisfy the bounds of Propositions
1\therosteritem3 and 3\therosteritem2.
Such $p$ are possible $p_d$.

This innermost
loop is speeded up considerably by splitting the range of such $p$ into
two parts.  For small values of $p$ we compute $P'$
with $PP' \congruent 1 \mod L$ and let $p$ run over the arithmetic
progression of numbers congruent to
$P' \mod L$, starting at the first term which exceeds $p_{d-1}$.
For each such $p$ we test whether $p$ is prime and $p-1$ divides $P-1$.
For large values of $p$ we run over small factors $f$ of $P-1$.
Putting $p =(P-1)/f + 1$ we then test whether $Pp \congruent 1 \mod L$ and
$p$ is prime.

We note that testing candidates for $p_i$ for primality is required at every
stage of the calculation.  We found that precomputing a list of prime numbers
up to a suitable limit produced a considerable saving in time.

Finally we note that using Proposition 1\therosteritem3 ensures that,
in the range up to $10^{15}$, the candidate $p_i$ are all less than $2^{25}$,
so that 32-bit integer arithmetic is always sufficient.

\subhead 3.  Checking ranges by sieving  \endsubhead

We used a sieving technique to verify that the list of Carmichael
numbers produced by the method of Section 2 was complete in certain
ranges.

Suppose that we wish to list those Carmichael numbers in a range up to
$X$ which are divisible only by primes less than $Y$.  We precompute
the list $\sL$ of primes up to $Y$.  We form a table of entries for the
integers up to $X$; for each $p$ in $\sL$ we add $\log p$ into the table
entries corresponding to numbers $t$ with $t > p$, $t \congruent 0 \mod p$ and
$t \congruent 1 \mod (p-1)$:
that is, $t \ge p^2$ and $t \congruent p \mod p(p-1)$.
At the end of this process we output any $N$ for which the table entry
is equal to $\log N$.  Such an $N$ has the property that $N$ is
square-free, all the prime
factors $p$ of $N$ are in $\sL$ and that $N \congruent 1 \mod (p-1)$
for every $p$ dividing $N$: that is, $N$ is a Carmichael number whose
prime factors are all in $\sL$.

From Proposition 1\therosteritem3, it is sufficient to take $Y = \sqrt X$
to obtain all the Carmichael numbers up to $X$.

The time taken to sieve over all the numbers up to $X$ will be bounded by
$$
X + \sum_{p \le Y} \left\lfloor \frac{X}{p(p-1)} \right\rfloor
\le
X + X \sum_p \frac1{p(p-1)}
= \O(X),
$$
which is an improvement over a direct search for Carmichael
numbers\footnote{Testing the condition $2^{N-1} \congruent 1 \mod N$
for all $N$ up to $X$ would take time $\O(X\log X)$.}
but still considerably slower in practice than the search technique.

We therefore consider a ``large prime variation''.  After sieving
with $Y = X^{\frac13}$, we use a further technique to deal
with those Carmichael numbers which have a prime factor $q$ greater 
than $X^{\frac13}$.
For each prime $q$ in the range $X^{\frac13}$ to $X^{\frac12}$, 
we consider all numbers $P$
up to $X/q$ which are $\congruent 1 \mod (q-1)$.  For each such $P$ we
first test whether $\left(2^P\right)^q \congruent 2 \mod P$.
If so, $N = Pq$ is a Fermat pseudo-prime to base 2 and hence a candidate
to be a Carmichael number.
The number of $P$ tested at this stage is
$$
\sum_{q=X^{\frac13}}^{X^{\frac12}} {X \over q} = \O(X^{\frac12} \log X) .
$$
Let $C_X$ denote the number of $P$ which pass on to the second stage.
We next factorise such $P$, checking that
the primes $p$ dividing $P$ are distinct,
less than $q$ and have the property that $N \congruent 1 \mod (p-1)$.
If so, then $N$ is a Carmichael number with $q$
as largest prime factor.  The time taken
to perform the second stage, using trial division,
is $\sqrt P = \O(X^{\frac13})$ for each value of $P$, so
$\O(C_X X^{\frac13}) = \O(X^{\frac56 + \epsilon})$ in total.
Hence the total time taken for the large prime variation is
$\O(X^{\frac56 + \epsilon})$.



\subhead 4.  Comparison with existing tables  \endsubhead

Carmichael in his original paper \cite{3}
gave four examples with three prime factors
and later \cite{4} a further ten examples with three prime factors and
one example with four prime factors.
Swift \cite{26} described a computation of the Carmichael numbers to $10^9$,
searching over possible lists of prime factors, and discusses earlier tables.
Yorinaga \cite{28} gave examples of
Carmichael numbers with up to 15 prime factors.  Pomerance, Selfridge and
Wagstaff \cite{23} listed the Fermat pseudoprimes base 2 up to $25.10^9$,
and selected the Carmichael numbers from this list by testing the prime
factors.  Jaeschke \cite{13} computed the Carmichael numbers up
to $10^{12}$ by a search strategy.
These results are summarised by Ribenboim \cite{24,25}.
Guillaume \cite{11} computed the Carmichael numbers up to $10^{12}$
using a method similar to the ``large prime variation''.
Keller \cite{14} obtained the
Carmichael numbers up to $10^{13}$ by a search
strategy and Guthmann \cite{12} used a sieving method very similar to that 
of Section 3 on a vector computer to obtain the
Carmichael numbers up to $10^{14}$.

Our results are consistent with the statistics of
the computations described above with two exceptions.
Jaeschke \cite{13} reports three fewer Carmichael
numbers up to $10^{12}$.  He has stated\footnote{Letter dated 21
January 1992} that this discrepancy is due to
his computer program having terminated prematurely when testing numbers
very close to the upper bound of the range.
Keller \cite{14} reports one less Carmichael number up to $10^{13}$.
He has stated\footnote{Electronic mail dated 5 May 1992}
that this was missed by a book-keeping error.

We have further
checked our tables by extracting the Carmichael numbers from the
tables of Fermat pseudoprimes base 2
of Pomerance, Selfridge and Wagstaff \cite{23}, and Pinch \cite{20}.
Morain has checked our tables up to $10^{12}$ against those of Guillaume.
In each case there is no discrepancy.

Keller has recently verified the computation up to $10^{15}$ by a different
method: see \cite{14}.


\subhead 5.  Description of the calculations  \endsubhead

We ran the search procedure of Section 2 with upper limits of $X = 10^n$
for each value of $n$ up to 15 independently.  As a consequence
the list of Carmichael numbers up to $10^{14}$ was in effect
computed twice, that up to $10^{13}$ three times and so on.
The computer programs were written in C, using 32-bit integer arithmetic,
and run on a Sun 3/60 or a Sparc workstation.  
As a check, both on the programs and the results,
some of the runs, including all those up to
$10^{12}$, were duplicated using the
rather strict Norcroft C compiler on an IBM 3084Q mainframe.  A total
of about 200 hours of CPU time was required.  All the results were consistent.

The sieving process of Section 3 turned out to be too expensive
to run over the whole range up to $10^{15}$.  We therefore applied the sieving
technique to various sub-ranges.

As a preliminary check,
we ran the ``large prime variation'' for Carmichael numbers up to $10^{12}$
with a prime factor between $10^4$ and $10^6$, and for
Carmichael numbers up to $10^{15}$ with
a prime factor between $10^5$ and $10^{7.5}$.
The lists matched those found by the search process: there were
2347 such numbers in the list up to $10^{12}$ and 4245 in the list up to
$10^{15}$.  These checks took about 100 hours of CPU time on a Sun 3/60
workstation.

In order to check our results against those of \cite{13}, we
carried out the sieve for the range $10^{12} - 10^{10}$ to
$10^{12}$ using primes up to $10^5$.  The search method had previously
found 24 Carmichael numbers
in this range, 20 having all prime factors less than $10^5$.  The
sieve found these 20 as expected, and the run of the
large prime variation for this range had already
found the other four.  This check
took about 20 hours of CPU time on a Sparc workstation.

The sieving method was run up to $10^{12}$ with a set of primes including
those up to $10^6$ as part of the calculations in Pinch \cite{20}.

We also used the sieve on a number of randomly chosen intervals of length
$10^6$ up to $10^{15}$.  In each case the results were again consistent
with the results of the search.


\subhead 6.  Statistics  \endsubhead

Let $\C(X)$ denote the number of Carmichael
numbers less than $X$, and $\C(d,X)$ denote the number which
have exactly $d$ prime factors.  In Table 1 we give $\C(d,X)$ and $\C(X)$ for
values of $X$ up to $10^{15}$.  No Carmichael number in this range
has more than 9 prime factors.  We have $\C(10^{15}) = 105212$.

In Table 2 we give the smallest Carmichael number with $d$ prime factors
for $d$ up to $20$.

In Table 3 we tabulate the function $k(X)$, defined by Pomerance, Selfridge and
Wagstaff \cite{23} by
$$
\C(X) = X \exp\left(-k(X) {\log X \log\log\log X \over \log\log X}\right),
$$
and the ratios $\C(10^n) / \C(10^{n-1})$ investigated by Swift \cite{26}.
Pomerance, Selfridge and Wagstaff \cite{23} proved that $\liminf k \ge 1$
and suggested that $\limsup k$ might be $2$, although they also observed
that within the range
of their tables $k(X)$ is decreasing.  This decrease is reversed between
$10^{13}$ and $10^{14}$; Swift's ratio, again initially decreasing,
also increases again before $10^{15}$.  Pomerance \cite{21,22} gave
a heuristic argument suggesting that $\lim k = 1$.

In Table 4 we give the number of Carmichael numbers in each class modulo $m$
for $m = 5$, 7, 11 and 12.

In Tables 5 and 6 we give the number of Carmichael numbers divisible by
primes $p$ up to 97.  In Table 5 we count all Carmichael numbers divisible
by $p$: in Table 6 we count only those which $p$ is the smallest prime factor.
The largest prime factor of a Carmichael number up
to $10^{15}$ is 21792241, dividing
$$
949803513811921 = 17 \cdot 31 \cdot 191 \cdot 433 \cdot 21792241,
$$
and the largest prime to occur as the smallest prime factor of a Carmichael
number in this range is 72931, dividing
$$
651693055693681 = 72931 \cdot 87517 \cdot 102103.
$$

It is well-known that the probability, $P_R(N)$, say, of an odd composite $N$
passing the Rabin test for a random base modulo $N$ is at most $\frac 14$:
it is easy to show that this bound is achieved if and only if $N$ is
a Carmichael number with exactly three prime factors, all $\congruent 3 \mod 4$:
call this class $\sC_3$.
McDonnell \cite{18} showed that if $P_R(N) \ge \frac{11}{64}$ for $N \ge 11$
then $N \in \sC_3$, or else one of $3N+1$, $8N+1$ is a square;
Damg\aa rd, Landrock and Pomerance \cite{5,6} improved
this to $P_R(N) \ge \frac18$ for $N$ prime to $6$.
Numbers in $\sC_3$ are also those
for which Davenport's ``maximal 2-part'' refinement \cite{7} gives
no strengthening of the Rabin test.
There are $487$ $\sC_3$-numbers up to $10^{15}$ and $868$ up to $10^{16}$,
the first being $8911 = 7 \cdot 19 \cdot 67$.

Lidl, M\"uller and Oswald \cite{16,17,19} characterize
a {\it strong Fibonacci pseudoprime}
as a Carmichael number $N = \prod p_i$ with one of the following properties:
either {(\it Type I)}\ an even number of the $p_i$
are $\congruent 3 \mod 4$ with
$2(p_i+1) \divides N-1$ for the $p_i \congruent 3 \mod 4$
and $p_i+1 \divides N \pm 1$ for the $p_i \congruent 1 \mod 4$;
or {\it (Type II)}\ there is an odd number
of $p_i$, all $\congruent 3 \mod 4$,
and $2(p_i+1) \divides N - p_i$ for all $p_i$.
(A strong Fibonacci pseudoprime is termed a {\it strong $(-1)$-Dickson
pseudoprime} in \cite{19}.)  They were not able to exhibit
any such numbers.  We found just one Type I strong Fibonacci pseudoprime
up to $10^{15}$, namely
$$
443372888629441 =
      17 \cdot 31 \cdot 41 \cdot 43 \cdot 89 \cdot 97 \cdot 167 \cdot 331,
$$
and none of Type II.  This also answers the question of Di Porto and
Filipponi \cite{8}.

Williams \cite{27} asked whether there are any Carmichael numbers $N$ with
an odd number of prime divisors and the additional
property that for $p \divides N$, $p +1 \divides N + 1$.  There are no such
Carmichael numbers up to $10^{15}$.

Finally we note that $\C(274859381237761) = 65019$ gives the
smallest value of $X$ for which $\C(X) > X^{\frac13}$.


\subhead 7.  Acknowledgements \endsubhead

The author is grateful to D. Guillaume, W. Keller, F. Morain and W. M\"uller
for helpful discussions
and for providing preprints and details of unpublished work.  Thanks
are also due to Prof. S.S. Wagstaff jr for providing a file containing
the tables described in \cite{23} and to the referee of the first version
of this paper for valuable comments.


\Refs

\ref \no 1 \by W.R. Alford, A. Granville and C. Pomerance
\paper There are infinitely many Carmichael numbers
\paperinfo Preprint 3 April 1992
\endref

\ref \no 2 \by N.G.W.H. Beeger
\paper On composite numbers $n$ for which $a^{n-1}\congruent1\bmod n$
for every $a$ prime to $n$
\jour Scripta math. \vol 16 \yr 1950 \pages 133--135
\endref

\ref \no 3 \by R.D. Carmichael
\paper Note on a new number theory function
\jour Bull. Amer. Math. Soc. \vol 16 \yr 1909--10 \pages 232--238
\endref

\ref \no 4 \bysame % R.D. Carmichael
\paper On composite numbers $P$ which satisfy the
congruence $a^{P-1} \congruent 1 \mod P$
\jour Amer. Math. Monthly \vol 19 \yr 1912 \pages 22--27
\endref

\ref \no 5 \by I. Damg\aa rd and P. Landrock
\paper Improved bounds for the Rabin primality test
\paperinfo Preprint 12 March 1992
\inbook Coding and cryptography III@.
Proceedings of the 3rd IMA conference
on coding and cryptography, Cirencester, December 1991@.
M. Ganley (ed.)
\finalinfo (to appear)
\endref

\ref \no 6 \by I. Damg\aa rd, P. Landrock and C. Pomerance
\paper Average error estimates for the strong probable prime test
\paperinfo Submitted
\endref

\ref \no 7 \by J.H. Davenport
\paper Primality testing revisited
\paperinfo Preprint 20 April 1992
\finalinfo Proceedings ISSAC 1992 (to appear)
\endref

\ref \no 8 \by A. Di Porto and P. Filipponi
\paper A probabilistic primality test based on the properties of
certain generalized Lucas numbers
\inbook Advances in Cryptology --- {\smc Eurocrypt'88}@.
Lecture notes in Computer Science {\bf 330}@.
C.G. G\"unther (ed.)
\publ Springer \publaddr Berlin \yr 1988
\endref

\ref \no 9 \by H. Duparc
\paper On Carmichael numbers
\jour Simon Stevin \vol 29 \yr 1951--2 \pages 21--24
\endref

\ref \no 10 \by A. Granville
\paper Primality testing and Carmichael numbers
\jour Notices Amer. Math. Soc. \vol 39 \yr 1992 \pages 696--700
\endref

\ref \no 11 \by D. Guillaume
\paper Table des nombres de Carmichael inferieurs \`a $10^{12}$
\paperinfo Preprint May 1991
\endref

\ref \no 12 \by A. Guthmann
\paper On the computation of Carmichael numbers
\paperinfo Universit\"at Kaiserslauten preprint 218, April 1992
\endref

\ref \no 13 \by G. Jaeschke
\paper The Carmichael numbers to $10^{12}$
\jour Math. Comp. \vol 55 \yr 1990 \pages 383--389
\endref

\ref \no 14 \by W. Keller
\paper The Carmichael numbers to $10^{13}$
\jour Abstracts Amer. Math. Soc.
\vol 9 \yr 1988 \pages 328--329
\endref

\ref \no 15 \by W. Kn\"odel
\paper Carmichaelsche Zahlen
\jour Math. Nachr. \vol 9 \yr 1953 \pages 343--350
\endref

\ref \no 16 \by R. Lidl and W.B. M\"uller
\paper A note on strong Fibonacci pseudoprimes
\inbook Advances in cryptology --- {\smc Auscrypt '90}@.
Lecture notes in Computer Science 453@.
J. Seberry and J. Pieprzyk (edd)
\publ Springer \publaddr Berlin \yr 1990
\endref

\ref \no 17 \by R. Lidl, W.B. M\"uller and A. Oswald
\paper Some remarks on strong Fibonacci pseudoprimes
\jour Applicable Algebra in Engineering, Communication and Computing
\vol 1 \yr 1990 \pages 59--65
\endref

\ref \no 18 \by F.J. McDonnell
\paper Rabin's algorithm and the proportion of `liars'
for various families of numbers
\paperinfo University of Warwick preprint March 1989
\endref

\ref \no 19 \by W.B. M\"uller and A. Oswald
\paper Dickson pseudoprimes and primality testing
\inbook Advances in cryptology --- {\smc Eurocrypt'91}@.
Lecture notes in Computer Science 547@.
D.W. Davies (ed.)
\publ Springer \publaddr Berlin \yr 1991
\endref

\ref \no 20 \by R.G.E. Pinch
\paper The pseudoprimes up to $10^{12}$
\paperinfo Preprint June 1992
\endref

\ref \no 21 \by C. Pomerance
\paper On the distribution of pseudoprimes
\jour Math. Comp. \vol 37 \yr 1981 \pages 587--593
\endref

\ref \no 22 \bysame % C. Pomerance
\paper Two methods in elementary number theory
\inbook Number theory and applications@.
R.A. Mollin (ed.)
\publ Kluwer \publaddr Dordrecht \yr 1989
\endref

\ref \no 23 \by C. Pomerance, J.L. Selfridge and S.S. Wagstaff jr
\paper The pseudoprimes to $25.10^9$
\jour Math. Comp. \vol 35 \yr 1980 \pages 1003--1026
\endref

\ref \no 24 \by P. Ribenboim
\book The book of prime number records
\publ Springer \publaddr New York \yr 1988
\endref

\ref \no 25 \bysame % P. Ribenboim
\book The little book of big primes
\publ Springer \publaddr New York \yr 1991
\endref

\ref \no 26 \by J.D. Swift
\paper Review 13[9] --- Table of Carmichael numbers to $10^9$
\jour Math. Comp. \vol 29 \yr 1975 \pages 338--339
\endref

\ref \no 27 \by H.C. Williams
\paper On numbers analogous to the {Carmichael} numbers
\jour Canad. Math. Bull. \vol 20 \yr 1977 \pages 133--143
\endref

\ref \no 28 \by M. Yorinaga
\paper Numerical computation of Carmichael numbers
\jour Math. J. Okayama Univ. \vol 20 \yr 1978 \pages 151--163
\moreref
\paper II
%\jour Math. J. Okayama Univ.
\vol 21 \yr 1979 \pages 183--205
\endref

\endRefs

\newpage
%\vfill\bigpagebreak

%\input tab1
% tab1.tex
% Last updated 3 February 1992
\vbox{\offinterlineskip
\hrule
\halign{
\strut#%
&\vrule#&\strut\quad\hfil$#$\quad
&\vrule#&\strut\quad\hfil$#$\quad
&\vrule#&\strut\quad\hfil$#$\quad
&\vrule#&\strut\quad\hfil$#$\quad
&\vrule#&\strut\quad\hfil$#$\quad
&\vrule#&\strut\quad\hfil$#$\quad
&\vrule#&\strut\quad\hfil$#$\quad
&\vrule#&\strut\quad\hfil$#$\quad
&\vrule#&\strut\quad\hfil$#$\quad
&\vrule#\cr
\noalign{\hrule}
&&  &&\multispan{13}\hfil$d$\hfil&&\omit&\cr
\noalign{\hrule}
&& X && 3 && 4 && 5 && 6 && 7 && 8 && 9 && \hbox{total} &\cr
\noalign{\hrule}
\omit&height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr
&&  3 &&    1 &&    0 &&    0 &&    0 &&    0 &&    0 &&    0 &&    1 &\cr
&&  4 &&    7 &&    0 &&    0 &&    0 &&    0 &&    0 &&    0 &&    7 &\cr
&&  5 &&   12 &&    4 &&    0 &&    0 &&    0 &&    0 &&    0 &&   16 &\cr
&&  6 &&   23 &&   19 &&    1 &&    0 &&    0 &&    0 &&    0 &&   43 &\cr
&&  7 &&   47 &&   55 &&    3 &&    0 &&    0 &&    0 &&    0 &&  105 &\cr
&&  8 &&   84 &&  144 &&   27 &&    0 &&    0 &&    0 &&    0 &&  255 &\cr
&&  9 &&  172 &&  314 &&  146 &&   14 &&    0 &&    0 &&    0 &&  646 &\cr
&& 10 &&  335 &&  619 &&  492 &&   99 &&    2 &&    0 &&    0 && 1547 &\cr
&& 11 &&  590 && 1179 && 1336 &&  459 &&   41 &&    0 &&    0 && 3605 &\cr
&& 12 && 1000 && 2102 && 3156 && 1714 &&  262 &&    7 &&    0 && 8241 &\cr
&& 13 && 1858 && 3639 && 7082 && 5270 && 1340 &&   89 &&    1 &&19279 &\cr
&& 14 && 3284 && 6042 &&14938 &&14401 && 5359 &&  655 &&   27 &&44706 &\cr
&& 15 && 6083 && 9938 &&29282 &&36907 &&19210 && 3622 &&  170 &&105212&\cr
\omit&height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr}
\hrule}
\par

\midspace{1pt}\caption{Table 1.  The number of Carmichael numbers with $d$
prime factors up to $10^{15}$}

\newpage
%\input tab2
% tab2.tex
% Last updated 19 February 1992
\vbox{\offinterlineskip
\hrule
\halign{
\strut#%
&\vrule#&\strut\quad\hfil#\quad
&\vrule#&\strut\quad#\quad\hfil
&\vrule#\cr
\noalign{\hrule}
&& $d$ && \hfill $N$ &\cr
&& \omit && factors &\cr
\noalign{\hrule}
\omit&height2pt&\omit&&\omit&\cr
&&  3 && \hfill                561 &\cr
&& \omit &&  3.11.17 &\cr
\noalign{\hrule}
&&  4 && \hfill               41041 &\cr
&& \omit &&  7.11.13.41 &\cr
\noalign{\hrule}
&&  5 && \hfill              825265 &\cr
&& \omit &&  5. 7.17.19.73 &\cr
\noalign{\hrule}
&&  6 && \hfill           321197185 &\cr
&& \omit &&  5.19.23.29.37.137 &\cr
\noalign{\hrule}
&&  7 && \hfill          5394826801 &\cr
&& \omit &&  7.13.17.23.31.67.73 &\cr
\noalign{\hrule}
&&  8 && \hfill        232250619601 &\cr
&& \omit &&  7.11.13.17.31.37.73.163 &\cr
\noalign{\hrule}
&&  9 && \hfill       9746347772161 &\cr
&& \omit &&  7.11.13.17.19.31.37.41.641 &\cr
\noalign{\hrule}
&& 10 && \hfill    1436697831295441 &\cr
&& \omit && 11.13.19.29.31.37.41.43.71.127 &\cr
\noalign{\hrule}
&& 11 && \hfill   60977817398996785 &\cr
&& \omit &&  5. 7.17.19.23.37.53.73.79.89.233 &\cr
\noalign{\hrule}
&& 12 && \hfill 7156857700403137441 &\cr
&& \omit && 11.13.17.19.29.37.41.43.61.97.109.127 &\cr
\noalign{\hrule}
&& 13 && \hfill   1791562810662585767521 &\cr
&& \omit && 11.13.17.19.31.37.43.71.73.97.109.113.127 &\cr
\noalign{\hrule}
&& 14 && \hfill  87674969936234821377601 &\cr
&& \omit &&  7.13.17.19.23.31.37.41.61.67.89.163.193.241 &\cr
\noalign{\hrule}
&& 15 && \hfill 6553130926752006031481761 &\cr
&& \omit && 11.13.17.19.29.31.41.43.61.71.73.109.113.127.181 &\cr
\noalign{\hrule}
&& 16 && \hfill 1590231231043178376951698401 &\cr
&& \omit && 17.19.23.29.31.37.41.43.61.67.71.73.79. 97.113.199 &\cr
\noalign{\hrule}
&& 17 && \hfill 35237869211718889547310642241 &\cr
&& \omit && 13.17.19.23.29.31.37.41.43.61.67.71.73. 97.113.127.211 &\cr
\noalign{\hrule}
&& 18 && \hfill 32809426840359564991177172754241 &\cr
&& \omit && 13.17.19.23.29.31.37.41.43.61.67.71.73. 97.127.199.281.397 &\cr
\noalign{\hrule}
&& 19 && \hfill 2810864562635368426005268142616001 &\cr
&& \omit &&13.17.19.23.29.31.37.41.43.61.67.71.73.109.113.127.151.281.353 &\cr
\noalign{\hrule}
&& 20 && \hfill 349407515342287435050603204719587201 &\cr
&& \omit && 11.13.17.19.29.31.37.41.43.61.71.73.97.101.109.113.151.181.193.641 &\cr
\omit&height2pt&\omit&&\omit&\cr}
\hrule}
\par

\midspace{1pt}\caption{Table 2.  The smallest Carmichael numbers with $d$
prime factors, $3 \le d \le 20$}

%\input tab3
% tab3.tex
% Last updated 14 February 1992
\vbox{\offinterlineskip
\hrule
\halign{
\strut#%
&\vrule#&\strut\hfil\quad$#$\quad
&\vrule#&\strut\hfil\quad$#$\quad
&\vrule#&\strut\hfil\quad$#$\quad\hfil
&\vrule#\cr
\noalign{\hrule}
&& n && k\left(10^n\right) && \C(10^n)/\C(10^{n-1}) &\cr
\noalign{\hrule}
\omit&height2pt&\omit&&\omit&&\omit&\cr
&&  3 && 2.93319 &&       &\cr
&&  4 && 2.19547 && 7.000 &\cr
&&  5 && 2.07632 && 2.286 &\cr
&&  6 && 1.97946 && 2.688 &\cr
&&  7 && 1.93388 && 2.441 &\cr
&&  8 && 1.90495 && 2.429 &\cr
&&  9 && 1.87989 && 2.533 &\cr
&& 10 && 1.86870 && 2.396 &\cr
&& 11 && 1.86421 && 2.330 &\cr
&& 12 && 1.86377 && 2.286 &\cr
&& 13 && 1.86240 && 2.339 &\cr
&& 14 && 1.86293 && 2.319 &\cr
&& 15 && 1.86301 && 2.353 &\cr
\omit&height2pt&\omit&&\omit&&\omit&\cr}
\hrule}
\par

\midspace{1pt}\caption{Table 3.  The functions $k\left(10^n\right)$
and $\C(10^n)/\C(10^{n-1})$}

%\input tab4
% tab4.tex
% Last updated 3 February 1992
\vbox{\offinterlineskip
\hrule
\halign{
\strut#%
&\vrule#&\strut\quad\hfil$#$\quad
&\vrule#&\strut\quad\hfil$#$\quad
&\vrule#&\strut\quad\hfil$#$\quad
&\vrule#&\strut\quad\hfil$#$\quad
&\vrule#&\strut\quad\hfil$#$\quad
&\vrule#&\strut\quad\hfil$#$\quad
&\vrule#&\strut\quad\hfil$#$\quad
&\vrule#&\strut\quad\hfil$#$\quad
&\vrule#\cr
\noalign{\hrule}
&& m  && c && 25.10^9 && 10^{11} && 10^{12} && 10^{13} && 10^{14} && 10^{15} &\cr
\noalign{\hrule}
\omit&height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr
&& 5  && 0 &&   203 && 312 && 627 && 1330 &&  2773 &&  5814 &\cr
&&    && 1 &&  1652 &&2785 &&6575 &&15755 && 37467 && 90167 &\cr
&&    && 2 &&    82 && 154 && 327 &&  702 &&  1484 &&  3048 &\cr
&&    && 3 &&   102 && 172 && 344 &&  725 &&  1463 &&  3059 &\cr
&&    && 4 &&   124 && 182 && 368 &&  767 &&  1519 &&  3124 &\cr
\omit&height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr
\noalign{\hrule}
\omit&height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr
&& 7  && 0 &&   401 && 634 &&1334 &&  2774 &&  5891 && 12691  &\cr
&&    && 1 &&  1096 &&1885 &&4613 && 11447 && 28001 && 69131 &\cr
&&    && 2 &&   105 && 186 && 432 &&   967 &&  2109 &&  4599 &\cr
&&    && 3 &&   152 && 232 && 496 &&  1055 &&  2178 &&  4707 &\cr
&&    && 4 &&   129 && 211 && 450 &&   985 &&  2122 &&  4592 &\cr
&&    && 5 &&   138 && 222 && 454 &&  1033 &&  2224 &&  4777 &\cr
&&    && 6 &&   142 && 235 && 462 &&  1018 &&  2181 &&  4715 &\cr
\omit&height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr
\noalign{\hrule}
\omit&height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr
&&11  && 0 &&   335 && 547 && 1324 && 3006 &&  7032 && 16563 &\cr
&&    && 1 &&   640 &&1131 && 2770 && 6786 && 16548 && 40891 &\cr
&&    && 2 &&   139 && 217 && 473 &&  1068 &&  2361 &&  5338 &\cr
&&    && 3 &&   142 && 220 && 457 &&  1045 &&  2348 &&  5319 &\cr
&&    && 4 &&   104 && 187 && 442 &&  1026 &&  2317 &&  5261 &\cr
&&    && 5 &&   152 && 243 && 466 &&  1066 &&  2370 &&  5316 &\cr
&&    && 6 &&   116 && 198 && 440 &&  1061 &&  2400 &&  5384 &\cr
&&    && 7 &&   122 && 195 && 458 &&  1023 &&  2223 &&  5165 &\cr
&&    && 8 &&   129 && 222 && 475 &&  1107 &&  2450 &&  5449 &\cr
&&    && 9 &&   131 && 218 && 465 &&  1042 &&  2285 &&  5179 &\cr
&&   && 10 &&   153 && 227 && 471 &&  1049 &&  2372 &&  5347 &\cr
\omit&height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr
\noalign{\hrule}
\omit&height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr
&&12  && 1 &&  2071 &&3462 &&7969 &&18761 &&43760 && 103428  &\cr
&&    && 3 &&     0 &&   0 &&   1 &&    2 &&    2 &&      5 &\cr
&&    && 5 &&    20 &&  32 &&  64 &&  124 &&  228 &&    448 &\cr
&&    && 7 &&    47 &&  75 && 147 &&  289 &&  547 &&   1027 &\cr
&&    && 9 &&    25 &&  36 &&  60 &&  103 &&  165 &&    294 &\cr
&&   && 11 &&     0 &&   0 &&   0 &&    0 &&    4 &&     10 &\cr
\omit&height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr}
\hrule}
\par

\midspace{1pt}\caption{Table 4.  The number of Carmichael numbers congruent
to $c$ modulo $m$ for $m = 5,7,11,12$}

%\input tab5
% tab5.tex
% Last updated 18 February 1992
\vbox{\offinterlineskip
\hrule
\halign{
\strut#%
&\vrule#&\strut\quad\hfil$#$\quad
&\vrule#&\strut\quad\hfil$#$\quad
&\vrule#&\strut\quad\hfil$#$\quad
&\vrule#&\strut\quad\hfil$#$\quad
&\vrule#&\strut\quad\hfil$#$\quad
&\vrule#&\strut\quad\hfil$#$\quad
&\vrule#&\strut\quad\hfil$#$\quad
&\vrule#\cr
\noalign{\hrule}
&& p && 25.10^9 && 10^{11} && 10^{12} &&10^{13} && 10^{14} && 10^{15} &\cr
\noalign{\hrule}
\omit&height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr
&&  3 &&  25 &&   36 &&   61 &&  105 &&  167 &&  299 &\cr
&&  5 && 203 &&  312 &&  627 && 1330 && 2773 && 5814 &\cr
&&  7 && 401 &&  634 && 1334 && 2774 && 5891 &&12691 &\cr
&& 11 && 335 &&  547 && 1324 && 3006 && 7032 &&16563 &\cr
&& 13 && 483 &&  807 && 1784 && 3998 && 9045 &&20758 &\cr
&& 17 && 293 &&  489 && 1182 && 2817 && 6640 &&16019 &\cr
&& 19 && 372 &&  608 && 1355 && 3345 && 7797 &&18638 &\cr
&& 23 && 113 &&  207 &&  507 && 1282 && 3135 && 7716 &\cr
&& 29 && 194 &&  336 &&  832 && 2094 && 5158 &&12721 &\cr
&& 31 && 335 &&  571 && 1320 && 3086 && 7270 &&17382 &\cr
&& 37 && 320 &&  535 && 1270 && 2926 && 6826 &&16220 &\cr
&& 41 && 227 &&  390 && 1001 && 2418 && 5896 &&14344 &\cr
&& 43 && 184 &&  296 &&  772 && 1920 && 4663 &&11594 &\cr
&& 47 &&  53 &&   80 &&  199 &&  492 && 1223 && 2873 &\cr
&& 53 &&  92 &&  160 &&  351 &&  813 && 2041 && 5143 &\cr
&& 59 &&  26 &&   41 &&   92 &&  262 &&  644 && 1611 &\cr
&& 61 && 269 &&  453 && 1075 && 2542 && 6047 &&14429 &\cr
&& 67 && 110 &&  178 &&  407 && 1063 && 2540 && 6306 &\cr
&& 71 && 104 &&  194 &&  521 && 1320 && 3351 && 8546 &\cr
&& 73 && 198 &&  348 &&  849 && 2145 && 4925 &&11929 &\cr
&& 79 &&  64 &&  107 &&  247 &&  686 && 1728 && 4318 &\cr
&& 83 &&  14 &&   24 &&   56 &&  137 &&  340 &&  838 &\cr
&& 89 &&  68 &&  131 &&  320 &&  788 && 1951 && 4981 &\cr
&& 97 && 123 &&  193 &&  495 && 1277 && 3123 && 7594 &\cr
\omit&height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr}
\hrule}
\par

\midspace{1pt}\caption{Table 5.  The number of times a prime $p \le 97$
occurs in a Carmichael number}

\newpage

%\input tab6
% tab6.tex
% Last updated 18 February 1992
\vbox{\offinterlineskip
\hrule
\halign{
\strut#%
&\vrule#&\strut\quad\hfil$#$\quad
&\vrule#&\strut\quad\hfil$#$\quad
&\vrule#&\strut\quad\hfil$#$\quad
&\vrule#&\strut\quad\hfil$#$\quad
&\vrule#&\strut\quad\hfil$#$\quad
&\vrule#&\strut\quad\hfil$#$\quad
&\vrule#&\strut\quad\hfil$#$\quad
&\vrule#\cr
\noalign{\hrule}
&& p && 25.10^9 && 10^{11} && 10^{12} &&10^{13} && 10^{14} && 10^{15} &\cr
\noalign{\hrule}
\omit&height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr
&&  3 &&  25 &&   36 &&   61 &&  105 &&  167 &&  299 &\cr
&&  5 && 202 &&  309 &&  624 && 1325 && 2765 && 5797 &\cr
&&  7 && 364 &&  579 && 1218 && 2557 && 5461 &&11874 &\cr
&& 11 && 263 &&  428 && 1071 && 2509 && 5979 &&14397 &\cr
&& 13 && 237 &&  431 && 1058 && 2462 && 5699 &&13514 &\cr
&& 17 && 117 &&  206 &&  496 && 1318 && 3244 && 8114 &\cr
&& 19 && 152 &&  244 &&  532 && 1401 && 3358 && 8141 &\cr
&& 23 &&  37 &&   78 &&  207 &&  535 && 1360 && 3317 &\cr
&& 29 &&  55 &&  103 &&  284 &&  729 && 1822 && 4659 &\cr
&& 31 && 101 &&  168 &&  390 &&  876 && 2116 && 5153 &\cr
&& 37 &&  60 &&   95 &&  219 &&  551 && 1401 && 3418 &\cr
&& 41 &&  35 &&   68 &&  171 &&  414 && 1092 && 2736 &\cr
&& 43 &&  35 &&   65 &&  168 &&  403 &&  943 && 2308 &\cr
&& 47 &&  14 &&   16 &&   36 &&   81 &&  195 &&  459 &\cr
&& 53 &&  19 &&   30 &&   55 &&  147 &&  363 &&  973 &\cr
&& 59 &&   2 &&    4 &&   11 &&   43 &&  100 &&  272 &\cr
&& 61 &&  34 &&   58 &&  148 &&  364 &&  851 && 1978 &\cr
&& 67 &&   8 &&   18 &&   50 &&  123 &&  317 &&  815 &\cr
&& 71 &&  15 &&   25 &&   66 &&  161 &&  389 &&  979 &\cr
&& 73 &&  14 &&   28 &&   68 &&  175 &&  406 && 1015 &\cr
&& 79 &&   4 &&   10 &&   17 &&   66 &&  175 &&  467 &\cr
&& 83 &&   1 &&    1 &&    4 &&    8 &&   39 &&   79 &\cr
&& 89 &&  10 &&   16 &&   23 &&   55 &&  148 &&  409 &\cr
&& 97 &&  10 &&   20 &&   50 &&  106 &&  261 &&  606 &\cr
\omit&height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr}
\hrule}
\par

\midspace{1pt}\caption{Table 6.  The number of times a prime $p \le 97$
occurs as the least prime factor of a Carmichael number}

\enddocument

\end
