\documentclass[12pt,reqno]{article}
\usepackage{amssymb}
\usepackage
[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\usepackage{amsthm,amssymb,color,epsf}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}
\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}
\newtheorem{Definition}{Definition}[section]
\newtheorem{Lemma}[Definition]{Lemma}
\newtheorem{Theorem}[Definition]{Theorem}
\newtheorem{Notation}[Definition]{Notation}
\newtheorem{Prop}[Definition]{Proposition}
\newtheorem{Cor}[Definition]{Corollary}
\renewcommand{\baselinestretch}{1.2}
\renewcommand{\arraystretch}{.7}
\makeatletter
\def\section{\@startsection {section}{1}{\z@}{-3.5ex plus -1ex minus
-.2ex}{2.3ex plus .2ex}{\normalsize\bf}}
\makeatother
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\begin{center}
%\epsfxsize=4in
%\leavevmode\epsffile{logo0019.eps}
\vskip 1cm
{\LARGE\bf Carmichael Numbers of the form $\bf{(6m+1)(12m+1)(18m+1)}$}
\vskip 1cm
\large Harvey Dubner\\
\vskip 0.5cm
449 Beverly Road \\
Ridgewood, New Jersey 07450 \\
USA\\
\vskip 0.5cm
{ \href{mailto:hdubner1@compuserve.com}{\tt hdubner1@compuserve.com} }
\vskip 1cm
\bf {Abstract}
\end{center}
{\em
Numbers of the form $(6m+1)(12m+1)(18m+1)$ where all three factors are
simultaneously prime are the best known examples of Carmichael numbers.
In this paper we tabulate the counts of such numbers up to $10^n$ for each
$n\le 42$. We also derive a function for estimating these counts that is
remarkably accurate.
}
%\vspace*{+.1in}
% Absolute value notation
\newcommand{\abs}[1]{\lvert#1\rvert}
% Blank box placeholder for figures (to avoid requiring any
% particular graphics capabilities for printing this document).
\newcommand{\blankbox}[2]{%
\parbox{\columnwidth}{\centering
% Set fboxsep to 0 so that the actual size of the box will match the
% given measurements more closely.
\setlength{\fboxsep}{0pt}%
\fbox{\raisebox{0pt}[#2]{\hspace{#1}}}%
}%
}
\section{Introduction}
Fermat's ``Little Theorem" says that if $a$ is any integer prime to $N$,
and if $N$ is prime, then
\begin{displaymath}
a^{N-1}\equiv 1 \pmod N .
\end {displaymath}
However, this is not a sufficient condition for a number to be prime since
there are composite numbers known as Carmichael numbers which satisfy this
congruence. Carmichael numbers meet the following criterion,\\
\textbf{Korselt's criterion (1899).} \emph{A composite odd number N is a
Carmichael number if and only if N is squarefree and $p-1$ divides $N-1$ for
every prime p dividing N.}\\
Considerable progress has been made investigating Carmichael numbers in the
past several years. Alford, Granville and Pomerance showed that there are
infinitely many Carmichael numbers \cite{AGP94}. L\"ow and Niebuhr
constructed Carmichael numbers with millions of components \cite{LN96}.
Balasubramanian and Nagaraj established an upper bound for the number of
3-component Carmichael numbers up to $x$ that is a little more than $x^{1/3}$
\cite{BN97}. Granville and Pomerance have developed several conjectures
which seem to resolve some serious inconsistencies concerning the total number
of Carmichael numbers \cite{GP02}.
These various conjectures are supported by counts of Carmichael numbers
mostly done by Richard Pinch \cite{Pinch1,Pinch2}.
However, in many cases the data is too limited to fully support some
of the conjectures.
The main purpose of this paper is to supply accurate extended counts of an
important family of 3-component Carmichael numbers.
Chernick in 1939 \cite{CH35} derived one-parameter expressions for
Carmichael numbers which he called ``Universal Forms,'' the most prominent
of these being
\begin{equation}
\label{eq:U3}
U_3(m)=(6m+1)(12m+1)(18m+1) .
\end{equation}
$U_3(m)$ is a Carmichael number when the quantities in parentheses are
simultaneously prime. There are indications that this family represents
about 2.2\% of the 3-component Carmichael numbers, more than any
such family.
\section{Search Method}
The method used to search for and count numbers of the form
(\ref{eq:U3}) depends
almost entirely on sieving. An array of 32,000,000 bits represents values
of $q~=~6m+1$ from $m=m_0$ to $m=m_0+31,999,999$. For each ``small" prime
from $5$ to an appropriate maximum, each $q$ is marked as composite when
divisible by a small prime (i.e., the bit is turned on). With a slight program
addition it can be determined if $r=12m+1$ or $s=18m+1$ has a
factor, and if it does then $q$ is also marked as composite even though $q$
itself might actually be prime.
Typically, in the vicinity of $U_3=10^{41}$,
about 18,000 numbers survive this sieving process which takes about 27 seconds
on an Athlon/1.2 GHz computer. No additional tests are required since all
three components of (\ref{eq:U3}) must be prime and therefore the survivors are
Carmichael numbers of the required form. The only additional processing
needed is to determine the sizes of all the survivors and to do appropriate
bookkeeping which takes about 1 second.
This process is repeated for the next block of 32,000,000 $m$'s. It is
easy to use multiple computers to get complete counts since the results
for each block is independent of all other blocks. To extend the count
from $10^{41}$ to $10^{42}$ took about 30 computer-days (Athlon/1.2 GHz).
Compute time for each decade takes about 2.2 times as long as the previous
decade. Thus, extending the count an additional decade takes about the
same time as it took for all the previous counts.
\section{Theoretical Count}
It is interesting and important to try to estimate the the number of
Carmichael numbers of the form $U_3(m)$ that are less than a given $X$.
The famous Hardy-Littlewood conjectures \cite{HL23} will be used as a model.
We follow the theory as described in detail in Riesel's book
\cite[p.\ 60]{HR94}.
Consider a number of the form (\ref{eq:U3}),
\begin{equation}
u=q\cdot r\cdot s,
\quad {\rm where\ } \quad q=6m+1, \quad r=12m+1, \quad s=18m+1.
\end{equation}
If $q$ were chosen at random, by the Prime Number Theorem the probability
of $q$ being prime would be $1/\log q$ asymptotically. However in our case
$q$ can never be divisible
by $2$ or $3$. When a number cannot be divided by a prime, $p$, the
probability of the number being prime increases by the factor $p/(p-1)$.
Thus the probability of $q$ being prime is increased by the factor
$(2/1)(3/2)=3$ and becomes
\begin{equation}
P_q=\frac{3}{\log(6m+1)}.
\end{equation}
As with $q$, $r$ cannot have 2 or 3 as a factor, but its primality is also
affected if $q$ is prime. Normally the chance that a prime $p$ will not
divide $r$ is $(p-1)/p$ because $(q \bmod p)$ has $(p-1)$ values which are
not zero. However, since $r=q+6m$ it is easy to show that if $q$ is prime
then $(r\bmod p)$ has only $(p-2)$ values which are not zero---thus dropping
the probability that $r$ is prime by the factor $(p-2)/(p-1)$.
The correction factor, $C_r(p)$, for $p$ is,
\begin{displaymath}
C_r(p)=\frac{p}{(p-1)}\cdot\frac{(p-2)}{(p-1)}= \frac{p(p-2)}{(p-1)(p-1)}
\end{displaymath}
The full correction factor is the product of these for
$p=5,7,11,13,\cdots \infty $,
\begin{displaymath}
C_r=\prod_5^\infty \frac{p(p-2)}{(p-1)(p-1)} \doteq .880216
\end{displaymath}
and the probability of $r$ being prime becomes,
\begin{equation}
P_r=3\cdot C_r\cdot \frac{1}{\log(12m+1)}=\frac{2.640648}{\log(12m+1)} \ .
\end{equation}
Similarly, the full correction factor for $s$ is
\begin{displaymath}
C_s=\prod_5^\infty \frac{p(p-3)}{(p-1)(p-2)}=.721604
\end{displaymath}
and the probability of $s$ being prime becomes,
\begin{equation}
P_s=3\cdot C_s\cdot \frac{1}{\log(18m+1)}=\frac{2.164812}{\log(18m+1)} \ .
\end{equation}
For a given $m$ the probability of $q$,
$r$ and $s$ being prime simultaneously is,
\begin{equation}
P_{qrs}=P_q\cdot P_r\cdot P_s=\frac{17.14952}{\log(6m+1)
\log(12m+1) \log(18m+1)} \ .
\end{equation}
Summing this probability over all appropriate $m$ gives an estimate for the
number of such Carmichael numbers less than a given $X$. To facilitate the
computation we replace the summation by integration, and replace the
Carmichael number components with,
\begin{displaymath}
\log(6m+1)\log(12m+1)\log(18m+1)=\log^3(a_xm),
\end{displaymath}
where $a_x$ is determined by evaluating the above
expression at $m=M=(X/1296)^{1/3}$,
the maximum value of $m$ corresponding to a given $X$.
The estimate now becomes,
\begin{equation}
E(X)=17.14952\sum_{m=1}^M\frac{1}{\log^3(a_xm)}\approx 17.14952\int_1^M \frac{dm}{\log^3(a_xm)} \ \ .
\end{equation}
To numerically evaluate $E(X)$, integrate by parts twice giving,
\begin{equation}
\label{eq:est}
E(X) \approx \frac{17.14952}{2 a_x} \left[\int^{a_x M} {\frac{dx}{\log(x)}} \ \ - \frac{a_x M}{\log(a_x M)} \ \ -\frac{a_x M}{\log^2 (a_x M)}\right] \ \ .
\end{equation}
The above integral term is the well-known logarithmic integral function,
$L_i(x)$, which is easy to accurately evaluate numerically.
Lower limits are omitted since they have negligible effect on the totals.
\section{Results}
Table 1 shows the actual counts of $(6m+1)(12m+1)(18m+1)$ Carmichael
numbers and the estimated counts from Eq.~(\ref{eq:est}). The errors and
percentage errors are also shown. The estimates are remarkably close to the
actual counts.
Although we do not know the exact
probability distribution of the counts, we can make the reasonable assumption
that they can be approximated by a Poisson distribution since this is true
for almost all distributions of rare phenomena. We can then present the
error as the number of standard deviations, which effectively normalizes
the error. If $N(X)$ is the actual number of Carmichael numbers found up
to $X$, and $E(X)$ is the estimated number then
\begin{displaymath}
{\rm error\ in\ standard\ deviations\ }=\frac{N(X)-E(X)}{\sqrt{E(X)}} \ \ .
\end{displaymath}
This is the last column in Table 1. Almost all these normalized errors
are within one standard deviation, excellent results which support the
accuracy of the theoretical estimating function over a wide range of
of values.
\begin{table}[htb]
\begin{center}
\begin{tabular}{|r|r|r|r|r|r|}
\hline
& & & & \% & error in\\
$X$ & actual & calculated & error \ & error \ & stand. dev\\
\hline
$10^{10}$ & 10& 14& -4& -40.00000& -1.07\\
$10^{11}$ & 16& 21& -5& -31.25000& -1.09\\
$10^{12}$ & 25& 34& -9& -36.00000& -1.57\\
$10^{13}$ & 50& 54& -4& -8.00000& -0.54\\
$10^{14}$ & 86& 89& -3& -3.48837& -0.32\\
$10^{15}$ & 150& 149& 1& 0.66667& 0.08\\
$10^{16}$ & 256& 256& 0& 0.00000& 0.00\\
$10^{17}$ & 436& 447& -11& -2.52294& -0.52\\
$10^{18}$ & 783& 793& -10& -1.27714& -0.36\\
$10^{19}$ & 1435& 1422& 13& 0.90592& 0.34\\
$10^{20}$ & 2631& 2581& 50& 1.90042& 0.98\\
$10^{21}$ & 4765& 4729& 36& 0.75551& 0.52\\
$10^{22}$ & 8766& 8743& 23& 0.26238& 0.25\\
$10^{23}$ & 16320& 16290& 30& 0.18382& 0.24\\
$10^{24}$ & 30601& 30563& 38& 0.12418& 0.22\\
$10^{25}$ & 57719& 57706& 13& 0.02252& 0.05\\
$10^{26}$ & 109504& 109578& -74& -0.06758& -0.22\\
$10^{27}$ & 208822& 209170& -348& -0.16665& -0.76\\
$10^{28}$ & 400643& 401200& -557& -0.13903& -0.88\\
$10^{29}$ & 771735& 772935& -1200& -0.15549& -1.37\\
$10^{30}$ & 1494772& 1495205& -433& -0.02897& -0.35\\
$10^{31}$ & 2903761& 2903388& 373& 0.01285& 0.22\\
$10^{32}$ & 5658670& 5657731& 939& 0.01659& 0.39\\
$10^{33}$ & 11059937& 11061388& -1451& -0.01312& -0.44\\
$10^{34}$ & 21696205& 21692750& 3455& 0.01592& 0.74\\
$10^{35}$ & 42670184& 42665199& 4985& 0.01168& 0.76\\
$10^{36}$ & 84144873& 84141713& 3160& 0.00376& 0.34\\
$10^{37}$ & 66369603& 166363608& 5995& 0.00360& 0.46\\
$10^{38}$ & 329733896& 329724862& 9034& 0.00274& 0.50\\
$10^{39}$ & 655014986& 654988567& 26419& 0.00403& 1.03\\
$10^{40}$ & 1303918824& 1303921334& -2510& -0.00019& -0.07\\
$10^{41}$ & 2601139051& 2601093060& 45991& 0.00177& 0.90\\
$10^{42}$ & 5198859223& 5198788710& 70513& 0.00136& 0.98\\
\hline
\end{tabular}
\caption{Count of $(6m+1)(12m+1)(18m+1)$ Carmichael Numbers up to $X$}
\label{tab:1}
\end{center}
\end{table}
\section{Estimating $C_3(X)$ for large $X$}
The 3-component Carmichael numbers can be expressed in the form
\begin {displaymath}
(am+1)(bm+1)(cm+1),
\ \ \ a**42$ by using the estimates from Eq.~(\ref{eq:est}).
However, it must be remembered that all these results are heuristic,
and although interesting they require more rigorous theory and study. One
area for future research is to relate the above results to the conjectures
and conclusions of the Granville and Pomerance paper \cite{GP02}.
\begin{table}[htb]
\begin{center}
\begin{tabular}{|l|r||r|r||r|r|}
\hline
$X$ & $C_3(X)$ & (1,2,3)& \% & $(1,b,c)$ & \% \\
\hline
$10^3$ & 1&&&& \\
$10^4$ & 7&&&& \\
$10^5$ & 12&&&& \\
$10^8$ & 84 & & & 59 & 70.24 \\
$10^9$ & 172 & & & 122 & 70.93\\
$10^{10}$ & 335 & 10 & 2.985 & 227 & 67.76\\
$10^{11}$ & 590 & 16 & 2.712 & 403 & 68.31\\
$10^{12}$ & 1000 & 25 & 2.500 & 680 & 68.00\\
$10^{13}$ & 1858 & 50 & 2.691 & 1220 & 65.66\\
$10^{14}$ & 3284 & 86 & 2.619 & 2104 & 64.07 \\
$10^{15}$ & 6083 & 150 & 2.466 & 3911 & 64.29\\
$10^{16}$ & 10816 & 256 & 2.368 & 6948 & 64.24\\
$10^{17}$ & 19539 & 436 & 2.331 & 12599 & 64.48\\
$10^{18}$ & 35586 & 783 & 2.200 & 22920 & 64.41\\
$10^{19}$ & 65309 & 1435 & 2.198 & 41997 & 64.32\\
$10^{20}$ & 120625 & 2631& 2.182 & 77413 & 64.22\\
\hline
%\multicolumn {6} {l}
%{\quad }\\
%\multicolumn {6} {l}
%{Note: $C_3(10^{19})$ and $C_3(10^{20})$ from \cite{AGP94}}\\
\end {tabular}
\caption{Count of families of 3-component Carmichael numbers }
\label{tab:2}
\end{center}
\end {table}
\section{Acknowledgements}
The 3-component Carmichael number counts, $C_3(10^n)$, are taken from the
Granville, Pomerance paper \cite{GP02}. These counts were
calculated by Richard Pinch, John Chick, Gordon Davies and Matthew Williams.
%\newcommand{\noopsort}[1]{} \newcommand{\singleletter}[1]{#1}
%\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\bibliographystyle{amsplain}
\begin{thebibliography}{1}
\bibitem{AGP94}
W.~R.~Alford, A.~Granville and C.~Pomerance, There are infinitely many
Carmichael numbers, {\it Ann.\ Math.} \textbf{140} (1994), 703--722.
MR \textbf{95k}:11114
\bibitem {BN97}
R.~Balasubramanian and S.~V.~Nagaraj, Density of Carmichael numbers with
three prime factors, {\it Math.\ Comp.} \textbf{66} (1997), 1705--1708.
MR\textbf {96d:}11110
\bibitem{CH35}
J.~Chernick, On Fermat's simple theorem, {\it Bull.\ Amer.\ Math.\ Soc.},
\textbf{45} (1935), 269--274.
\bibitem{GP02}
A.~Granville and C.~Pomerance, Two contradictory conjectures concerning
Carmichael numbers, {\it Math.\ Comp.} \textbf{71} (2002), 883--908.
\bibitem{HL23}
G.~H.~Hardy and J.~E.~Littlewood, Some problems on partitio numerorum
III. On the expression of a number as a sum of primes, {\it Acta Math.}
\textbf{44} (1923), 1--70.
%\bibitem{HW79}
%G.~H.~Hardy and E.~M.~Wright, \emph{An Introduction to the Theory of Numbers},
% 5th ed., Oxford University Press, 1979.
\bibitem{LN96}
G.~L\"oh and W.~Niebuhr, A new algorithm for constructing large
Carmichael numbers, {\it Math.\ Comp.} \textbf{65}, (1996), 823--836.
\bibitem {ore48}
O.~Ore, \emph {Number Theory and Its History}, McGraw-Hill Book Company, Inc.
1948. Reprinted, Dover Publications, Inc., 1988.
\bibitem {Pinch1}
R.~G.~E.~Pinch, The Carmichael numbers up to $10^{16}$, to appear.
\bibitem {Pinch2}
R.~G.~E.~Pinch, $3$-component Carmichael numbers up to $10^{18}$,
private communication.
%\bibitem{Ribenboim95}
%P.~Ribenboim, \emph{The New Book of Prime Number Records}, 3rd ed.,
% Springer-Verlag, New York, 1995.
\bibitem{HR94}
H.~Riesel, \emph{Prime Numbers and Computer Methods for Factorization},
2nd ed., Birkh\"auser, 1994.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2000 {\it Mathematics Subject Classification}: \ \ 11A99
\noindent \emph{Keywords: Carmichael numbers}
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequence \seqnum{A002997}.)
\vspace*{+.1in}
\noindent
Received August 12, 2002;
revised version received September 16, 2002.
Published in {\it Journal of Integer Sequences} September 23, 2002.
Revised version, November 25, 2002.
\bigskip
\hrule
\bigskip
\noindent
Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterloo.ca/JIS/}.
\end{document}
**