\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), \ \ \ a42$ 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}