\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\usepackage{mathrsfs}
%\usepackage{cite}
%\usepackage{authblk}
%\usepackage{blindtext}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf 
Explicit Bounds for the Sum of Reciprocals of \\
\vskip .1in
Pseudoprimes and Carmichael Numbers
}
\vskip 1cm
\large
Jonathan Bayless and Paul Kinlaw \\
Husson University\\
1 College Circle\\
Bangor, ME 04401\\
USA\\
\href{mailto:baylessj@husson.edu}{\tt baylessj@husson.edu}\\
\href{mailto:kinlawp@husson.edu}{\tt kinlawp@husson.edu}
\end{center}

\vskip .2 in



\def\modd#1 #2{#1\ \mbox{\rm (mod}\ #2\mbox{\rm )}}


\begin{abstract}
From a 1956 paper of Erd\H{o}s, we know that the base-two pseudoprimes and the Carmichael numbers both have a convergent sum of reciprocals.  We prove that the values of these sums are less than $33$ and $28$, respectively.
\end{abstract}

\section{Introduction}

By Fermat's little theorem, if $p$ is a prime number then for all $a
\in \mathbb{Z}$ we have $a^{p}\equiv a$ (mod $p$).  However, a number $p$
satisfying this property need not be a prime.  For all $a \in
\mathbb{Z}$, a \emph{base-$a$ Fermat pseudoprime} (or briefly, an
\emph{$a$-pseudoprime}) is a composite number $n$ such that
$\gcd(a,n)=1$ and $a^{n}\equiv a$ (mod $n$).  A \emph{Carmichael
number} is an odd composite number $n$ for which $a^{n}\equiv a$ (mod
$n$) for all integers $a$, and so is an $a$-pseudoprime for all $a$
with $\gcd(a,n)=1$.

Let $\mathscr{P}_2=\{341,561,645,1105,\ldots\}$ be the set of 2-pseudoprimes, also called \emph{Poulet} or \emph{Sarrus} numbers, and let $P_2(x)=\left|\{n\in \mathscr{P}_2: n\le x\}\right|$ be the corresponding counting function.  Let $\mathscr{C}=\{561, 1105, 1729,\ldots\}$ be the set of Carmichael numbers and write its counting function as $C(x)=\left|\{n\in \mathscr{C}: n\le x\}\right|$.  Erd\H{o}s \cite{erdos1956pseudoprimes} proved that for sufficiently large $x$, we have
\begin{displaymath}
P_2(x)<x/\exp(c_1\sqrt{\log x\log\log x})
\end{displaymath}
and
\begin{displaymath}
C(x)<x/\exp\left(\frac{c_2\log x\log\log\log x}{\log\log x}\right)
\end{displaymath}
for constants $c_1,c_2>0$.  This implies that both sets have asymptotic density zero, as well as the stronger statement that both sets have a bounded sum of reciprocals.  Pomerance \cite{Pomerance} improved these bounds, showing that
\begin{displaymath}
P_2(x)<x/\exp\left(\frac{\log x\log\log\log x}{2\log\log x}\right)
\end{displaymath}
for all sufficiently large $x$, and that the constant $c_2$ in the above bound on $C(x)$ may be taken as $1$.

In the other direction, it is well known that there are infinitely many
pseudoprimes with respect to a given base.  In 1994 Alford, Granville
and Pomerance \cite{alford1994there} proved that there are infinitely
many Carmichael numbers.  In particular, they proved that
$C(x)>x^{2/7}$ for sufficiently large $x$.  Their work has since been
improved by Harman \cite{Harman} to show that for large $x$, the
inequality $C(x) > x^{\alpha}$ holds for some constant $\alpha > 1/3$.

In this paper we determine explicit upper and lower bounds for the sum of reciprocals of 2-pseudoprimes, as well as for the sum of reciprocals of Carmichael numbers. This extends previous work  \cite{bayless2011sum, bayless2013reciprocal, phipaper, Hanh} on reciprocal sums.  See \cite{bayless2013reciprocal} for a discussion of reciprocal sums and their importance in number theory.

\section{Preliminary lemmas}

We state several preliminary lemmas.  Throughout the paper $m,n$ and $k$ denote positive integers, $p$ denotes a prime number, $\pi(x)$ is the prime counting function, $\log x$ denotes the natural logarithm and $P(n)$ denotes the largest prime factor of $n$.  Put $x_0=\exp(100)$ and $y_0=\exp(10)$.  We begin with Korselt's criterion \cite[Thm.\ 3.4.6]{CP} which provides a useful characterization of Carmichael numbers.

\begin{lemma}[Korselt's Criterion]\label{korselt} \ A positive integer $n$ is a Carmichael number if and only if it is composite, squarefree, and for each prime $p|n$ we have $p-1|n-1$.
\end{lemma}

It follows from Korselt's criterion that Carmichael numbers are odd and have at least three different prime factors.

The following lemma involves certain divisibility properties possessed by all $2$-pseudoprimes.  In particular, it shows that if a $2$-pseudoprime $n$ is divisible by $p^2$ for a prime $p$, then $p$ must be a \emph{Wieferich prime}, that is,
$$2^{p-1}\equiv \modd{1} {p^2}.$$  It follows that $p$ is greater than or equal to $1093$, the smallest Wieferich prime, see \cite[p.\ 31]{CP}.

\begin{lemma}\label{pseudoprimeproperties}
Let $n$ be a $2$-pseudoprime.  If $p^2|n$ then $p$ is a Wieferich prime.  Furthermore, if $7|n$ then $n\equiv \modd{1} {3}$.
\end{lemma}

\begin{proof}
Suppose that $p^2|n$ and let $k$ be the order of $2$ in $(\mathbb{Z}/p^2\mathbb{Z})^\times$.  Thus $k|\varphi(p^2)=p(p-1)$.  Now $2^{n-1}\equiv 1$ (mod $n$), so $2^{n-1}\equiv 1$ (mod $p^2$), and thus $k|n-1$, so $k$ does not divide $p$.  Thus $k|p-1$, so that $2^{p-1}\equiv 1$ (mod $p^2$).  This completes the proof of the first assertion.

For the second assertion, we have $2^{n-1}\equiv 1$ (mod $n$), so if $7|n$ then $2^{n-1}\equiv 1$ (mod $7$).  The order of $2$ modulo $7$ is $3$, so $3|n-1$.
\end{proof}

We will also use explicit versions of several classical theorems.  The following modification of \cite[Thm.\ 3.2]{apostol2013introduction} gives fairly sharp explicit bounds on the partial sums of the harmonic series.

\begin{lemma}\label{harmonicsum}
For all $x \ge 1$,
\begin{displaymath}
\left|\sum_{n\le x}\frac{1}{n}-(\log x+\gamma)\right|<\frac{1}{x}
\end{displaymath}
where $\gamma=0.5772156649\ldots$ denotes Euler's constant.
\end{lemma}

We will also use the following modification of \cite[Lem.\ 6.2]{phipaper} to bound the sum of reciprocals of numbers in a certain interval and residue class.
\begin{lemma}\label{residueclasses}
Let $a\in \mathbb{Z}$ and $\displaystyle d=2\prod_{i=2}^9 p_i^2$, where $p_i$ denotes the $i$-th prime number. We have
\begin{displaymath}
\mathop{\sum_{n\equiv a(d)}}_{10^{19}<n\le x_0}\frac{1}{n}<\frac{56.25587}{d}.
\end{displaymath}
\end{lemma}

\begin{proof}
Let $b=(10^{19}-d+1)/d$ and $c=x_0/d$.  Without loss of generality, we may assume that $a\in \{0,\ldots,d-1\}$.  By Lemma \ref{harmonicsum} we have
\begin{displaymath}
\sum_{b<k\le c}\frac{1}{dk+a}\le \frac{1}{d}\left(100-\log(10^{19}-d+1)+\frac{1}{c}+\frac{1}{b}\right)<\frac{56.25587}{d}.\qedhere
\end{displaymath}
\end{proof}

We will use Dusart's bounds \cite[Thm.\ 5.6]{dusart} on the sum of reciprocals of prime numbers up to $x$.
\begin{lemma}\label{mertens}
For all $x\ge 2278383$, we have
\begin{displaymath}
\left|\sum_{p\le x}\frac{1}{p}-(\log\log x+B)\right|<\frac{0.2}{\log^3 x},
\end{displaymath}
where $B=0.2614972128476\ldots$ denotes the Mertens constant.
\end{lemma}

We will also use Dusart's bounds \cite[Cor.\ 5.2 \& Thm.\ 5.9]{dusart}.

\begin{lemma}\label{dusart1}
For all $x>1$ we have
\begin{displaymath}
\pi(x)\le \frac{x}{\log x}\left(1+\frac{1}{\log x}+\frac{2.53816}{\log^2 x}\right),
\end{displaymath}
and for all $x\ge 599$ we have
\begin{displaymath}
\pi(x)\ge \frac{x}{\log x}\left(1+\frac{1}{\log x}\right).
\end{displaymath}
\end{lemma}

\begin{lemma}\label{dusart2}
For all $x\ge 2278382$, we have
\begin{displaymath}
\prod_{p \le x} \left( 1- \frac{1}{p}\right) \ge \frac{\exp(-\gamma)}{\log x} \left(1-\frac{0.2}{\log^3 x}\right).
\end{displaymath}
\end{lemma}

We will also use the following result \cite[Lem.\ 9.6]{de2012analytic}.

\begin{lemma} \label{LDLem1}
Let $f$ be a multiplicative function such that $f(n) \ge 0$ for all $n$, and such that there exist constants $A$ and $B$ such that for all $x > 1$, we have
\begin{equation}\label{LDLem1Eqn}
\sum_{p \le x} f(p) \log p \le Ax \qquad \textrm{ and } \qquad \sum_{p} \sum_{\alpha \ge 2} \frac{f\left(p^{\alpha}\right)}{p^{\alpha}} \log p^{\alpha} \le B.
\end{equation}
Then, for $x > 1$, we have
\begin{displaymath}
\sum_{n \le x} f(n) \le (A + B + 1) \frac{x}{\log x} \sum_{n \le x} \frac{f(n)}{n}.
\end{displaymath}
\end{lemma}

The following lemma makes the implied constants in \cite[Lem.\ 9.7]{de2012analytic} explicit and modifies \cite[Lem.\ 2.4]{phipaper}.

\begin{lemma}\label{LDLem3}
Let $f$ be a multiplicative function such that $0 \le f(p^{\alpha}) \le \exp\left( \frac{2\alpha}{3} \right)$ for all primes $p$ and integers $\alpha \ge 1$, and such that $f\left( p^{\alpha} \right) = p^{2 \alpha/(3 \log y)}$ for all $p\le y$.  Then for all $x \ge x_0$ and $y\ge y_0$, we have
\begin{displaymath}
\sum_{n \le x} f(n) \le 9.68765388 x \prod_{p \le x} \left( \left(1 - \frac{1}{p} \right) \sum_{\alpha \ge 0} \frac{f(p^{\alpha})}{p^{\alpha}} \right).
\end{displaymath}
\end{lemma}

\begin{proof}
We wish to apply Lemma \ref{LDLem1}, and so we first establish values of $A$ and $B$ to use in inequality \eqref{LDLem1Eqn} above.  We have
\begin{equation} \label{Eqn1}
\sum_{p \le x} f(p) \log p \le \exp(2/3) \theta(x) \le 1.00000075 \exp(2/3) x \le 1.94773551 x,
\end{equation}
using the bound $\theta(x) < 1.00000075x$ for all $x > 0$ \cite[Cor.\ 2]{platttrudgian}.  We also have $y\ge y_0$ and
\begin{displaymath}
f\left( p^{\alpha} \right) = p^{2\alpha/(3 \log y)}
\end{displaymath}
whenever $p \le y$.  For brevity, let $g(t)=(f(t)\cdot \log t)/t$.  We have
\begin{displaymath}
\sum_p \sum_{\alpha \ge 2} g\left(p^{\alpha}\right) = \sum_{p<y_0}\sum_{\alpha \ge 2} g\left(p^{\alpha}\right) + \sum_{p>y_0} \sum_{\alpha \ge 2} g\left(p^{\alpha}\right).
\end{displaymath}
Starting to bound the sum with $p=2$, observe that
\begin{displaymath}
\begin{aligned}
\sum_{\alpha \ge 2} g\left(2^{\alpha}\right) &\le \sum_{\alpha \ge 2} \frac{\alpha (\log 2) \cdot 2^{\alpha/15}}{2^{\alpha}} = \log 2 \sum_{\alpha \ge 2} \alpha \left(2^{1/15-1} \right)^{\alpha}\\
&< 1.23661725.
\end{aligned}
\end{displaymath}
Here we used the fact that
\begin{displaymath}
\sum_{\alpha\ge 2}\alpha r^{\alpha -1} = \frac{2r-r^2}{(1-r)^2}
\end{displaymath}
for $|r|<1$.  By similar reasoning,
\begin{displaymath}
\sum_{3\le p<y_0}\sum_{\alpha \ge 2} g\left(p^{\alpha}\right) <1.25448156.
\end{displaymath}
Let $h(t)=(2-e^{2/3}/t)(\log t)/(t-e^{2/3})^2$.  By partial summation we have
\begin{displaymath}
\begin{aligned}
\sum_{p>y_0} \sum_{\alpha \ge 2} g\left(p^{\alpha}\right)& \le e^{4/3} \sum_{p>y_0} \frac{(2-e^{2/3}/p)\log p}{(p-e^{2/3})^2}\\
&=e^{4/3}\left(-h(y_0)\pi(y_0)-\int_{y_0}^\infty \pi(t)h'(t)~dt\right)\\
&<e^{4/3}\left(-h(y_0)\pi(y_0)+\int_{y_0}^\infty \frac{\pi(t)\cdot 2(2-\frac{e^{2/3}}{t})\log t~dt}{(t-e^{2/3})^3}\right)\\
&<e^{4/3}\left(-h(y_0)\pi(y_0)+\int_{y_0}^\infty \frac{2t\cdot 1.1253816(2-\frac{e^{2/3}}{t})~dt}{(t-e^{2/3})^3}\right)\\
&= e^{4/3} \left(-0.00010166 + \frac{1.1253816 \cdot \left(4e^{10} - 3 e^{2/3}\right)}{\left(e^{2/3}-e^{10}\right)^2}\right)\\
&<0.00038973.
\end{aligned}
\end{displaymath}
Here we used Lemma \ref{dusart1}.  Furthermore, for all $x\ge x_0$ we have
\begin{displaymath}
1.781072775 \prod_{p \le x} \left( 1 - \frac{1}{p}\right) \ge \frac{1}{\log x}.
\end{displaymath}
by Lemma \ref{dusart2}.  Applying Lemma \ref{LDLem1} with $A=1.94773551$ and $B=2.49148854$, and noting that $A+B+1=5.43922405$ and $5.43922405 \cdot 1.781072775 < 9.68765388$, we complete the proof of the lemma.\qedhere
\end{proof}

We now prove the following explicit upper bound on de Bruijn's function $\Psi(x,y)$, defined as the number of numbers up to $x$ that are \emph{$y$-smooth} (that is, free of prime factors exceeding $y$).

\begin{lemma}\label{psilemma}
For all $x\ge x_0$ and $y\ge y_0$, we have
\begin{displaymath}
\Psi(x,y)\le 31.928253x^{1-1/(2\log y)}.
\end{displaymath}
\end{lemma}

\begin{proof}
We follow \cite[Thm.\ 9.5]{de2012analytic}.  By Rankin's method, if $\beta > 0$, then
\begin{equation} \label{FirstPsiBound}
\Psi(x,y) \le x^{3/4} + \sum_{n \le x} \left( \frac{n}{x^{3/4}} \right)^{\beta} \chi_y(n),
\end{equation}
where $\chi_y(n) = 1$ if $P(n) \le y$ and $\chi_y(n) = 0$ if $P(n)>y$.  Set $\beta = \frac{2}{3 \log y}$.  By Lemma \ref{LDLem3}, we have that
\begin{equation} \label{Rankin1Eqn}
\sum_{n \le x} n^{\beta} \chi_y(n) \le 9.68765388 x \prod_{p \le y} \left( \left(1-p^{-1}\right) \sum_{\alpha \ge 0} p^{\alpha(\beta-1)}\right).
\end{equation}

Now, for any given value of $p$,
\begin{displaymath}
\left(1-\frac{1}{p} \right) \sum_{\alpha \ge 0} p^{\alpha (\beta-1)} = \left(1-\frac{1}{p} \right) \frac{1}{1-p^{\beta-1}}=\frac{p-1}{p-p^{\beta}} = 1 +\frac{ p^{\beta} - 1}{p-p^{\beta}}.
\end{displaymath}
For $p\le 13$, the product contributes a factor less than $1.18817106$ to the product in inequality \eqref{Rankin1Eqn}.  Bounding this second term for $p > 13$, we see that
\begin{displaymath}
\frac{p^{\beta}-1}{p-p^{\beta}} =  \frac{p}{p-p^{\beta}} \cdot \frac{p^{\beta}-1}{p} < 1.07648742 \cdot \frac{p^{\beta}-1}{p}
\end{displaymath}
since for $p\ge 17$,
\begin{displaymath}
\frac{p}{p-p^{\beta}} \le \left( \frac{17}{17-17^{1/15}} \right) < 1.07648742.
\end{displaymath}
For $0 < t \le \frac{2}{3}$ we have $e^t - 1 \le 1.4216011t$ and therefore we may bound
\begin{displaymath}
\begin{aligned}
\sum_{p=17}^y 1.07648742 \cdot \frac{p^{\beta}-1}{p} &= \sum_{p=17}^y 1.07648742 \cdot \frac{\exp\left( \log p^{\beta}\right)-1}{p}\\
&\le 1.4216011\cdot 1.07648742\beta \sum_{p \le y}\frac{\log p}{p} \\
&< 1.4216011\cdot 1.07648742\beta \log y.
\end{aligned}
\end{displaymath}
Here we used Rosser and Schoenfeld's bound (3.23), \cite[p.\ 70]{barkley1962approximate},
\begin{displaymath}
\sum_{p \le y} \frac{\log p}{p} < \log y -1.3325 + \frac{1}{\log y} < \log y
\end{displaymath}
for $y \ge 32$.  We therefore have inequality \eqref{Rankin1Eqn} bounded above by
\begin{displaymath}
9.68765388\cdot 1.18817106e^{1.4216011\cdot 1.07648742\beta \log y} \le 31.9282527.
\end{displaymath}

Using this in inequality \eqref{FirstPsiBound} for $x\ge x_0$ gives the bound
\begin{displaymath}
\Psi(x,y) \le x^{3/4} + 31.9282527 x^{1-1/(2\log y)} \le 31.928253 x^{1-1/(2\log y)}.\qedhere
\end{displaymath}
\end{proof}

\section{The sum of reciprocals of base-two pseudoprimes}

We prove explicit bounds on the sum of reciprocals of 2-pseudoprimes by expanding Luca and De Koninck's proof \cite[Prop.\ 9.11]{de2012analytic} of the following result.  
\begin{proposition}
For all $c<1/(2\sqrt{2})$ we have $P_2(x) \ll x \exp\left( -c\sqrt{\log x}\right)$.
\end{proposition}
By partial summation, it follows that the sum of reciprocals is convergent.  

\begin{theorem}\label{pseudoprimereciprocalsum}
The sum of the reciprocals of base-two pseudoprimes satisfies
\begin{displaymath}
0.0152608<\sum_{n\in \mathscr{P}_2}\frac{1}{n}<33.
\end{displaymath}
\end{theorem}

To prove Theorem \ref{pseudoprimereciprocalsum} we split the 2-pseudoprimes into three ranges. 

\subsection{The small range}

We first compute the reciprocal sum over $n\le 10^{19}$.  Feitsma \cite{Feitsma} has computed an exhaustive list of all 2-pseudoprimes $n\le 10^{19}$.  We use this information to directly compute the reciprocal sum from the 2-pseudoprimes $n\le 10^{12}$ to seven decimal places as
\begin{displaymath}
\mathop{\sum_{n\in \mathscr{P}_2}}_{n\le 10^{12}}\frac{1}{n}=0.0152608\ldots.
\end{displaymath}
For each $k=12,\ldots,18$, the contribution to the reciprocal sum from 2-pseudoprimes $n$ such that $10^k<n\le 10^{k+1}$ is bounded above by the number of such $n$ times $10^{-k}$.  We thus obtain
\begin{displaymath}
\mathop{\sum_{n\in \mathscr{P}_2}}_{n\le 10^{19}}\frac{1}{n}\le 0.0152612.
\end{displaymath}

\subsection{The middle range}

We now bound the reciprocal sum over $n$ such that $10^{19}<n\le x_0$.  By Lemma \ref{pseudoprimeproperties}, all $2$-pseudoprimes are odd and not divisible by the square of 
any prime $p<1093$.  Therefore, they must lie in one of
\begin{displaymath}
D=\prod_{i=2}^9 (p_i^2-1)
\end{displaymath}
residue classes modulo $d$, where $d$ is as defined in Lemma \ref{residueclasses}.  Also by Lemma \ref{pseudoprimeproperties}, no $2$-pseudoprime is congruent to $0$ or $14$ modulo $21$.  Therefore we may rule out $30$ more residue classes modulo $3^27^2$.  Thus $2$-pseudoprimes must lie in one of $$D'=354\cdot 24\cdot 120\cdot 168\cdot 288\cdot 360\cdot 528$$ residue classes modulo $d$.  Therefore by Lemma \ref{residueclasses}, we have
\begin{displaymath}
\mathop{\sum_{n\in \mathscr{P}}}_{10^{19}<n\le x_0}\frac{1}{n}<\frac{56.25587D'}{d}<21.196317.
\end{displaymath}
We may also remove the contribution to the sum from prime numbers.  By Lemma \ref{mertens}, we have
\begin{displaymath}
\sum_{10^{19}<p\le x_0}\frac{1}{p}>0.826696.
\end{displaymath}
The sum in the middle range is therefore bounded above by
\begin{displaymath}
21.196317-0.826696=20.369621.
\end{displaymath}

\subsection{The large range}

Finally, we bound the reciprocal sum over $2$-pseudoprimes $n>x_0$.  Let $x>x_0$ and define $y=\exp(\sqrt{\log x})$, with $y_0=y(x_0)=\exp(10)$.  For ease of notation, write $p=P(n)$ and define $t_p$ as the multiplicative order of $2$ modulo $p$.  Define the set $\mathcal{Q} = \{ p : t_p < p^{1/4}\}$, and let $Q(x) = |\{p \in \mathcal{Q}: p \le x\}|$.  Each $2$-pseudoprime $n > x_0$ falls into exactly one of the following categories:
\begin{enumerate}
\item $p \le y$,
\item $p > y$ and $p \in \mathcal{Q}$,
\item $p > y$ and $p \not\in \mathcal{Q}$.
\end{enumerate}
For each $1 \le i \le 3$, write $\mathscr{A}_i$ for the set of $2$-pseudoprimes $n\le x$ satisfying property $i$ above and put $A_i(x)=|\{n \in \mathscr{A}_i : n \le x\}|$.

Observe that $A_1(x) = \Psi(x,y)$.  By Lemma \ref{psilemma} we have $$\Psi(x,y)\le 31.928253x/\exp(u/2)$$ where $\displaystyle u=\frac{\log x}{\log y}=\frac{\log x}{\sqrt{\log x}}=\sqrt{\log x}$.
We thus have 
\begin{displaymath}
A_1(x)\le \frac{31.928253x}{\exp\left(0.5\sqrt{\log x}\right)}
\end{displaymath}
for $x>x_0$.  Therefore, by partial summation, 
\begin{displaymath}
\begin{aligned}
\mathop{\sum_{n\in \mathscr{A}_1}}_{n>x_0}\frac{1}{n}&\le \int_{x_0}^\infty \frac{31.928253~dt}{t\exp\left(0.5\sqrt{\log t}\right)}=\int_{100}^\infty \frac{31.928253~dw}{\exp(\sqrt{w/4})}\\
&=31.928253\left[4e^{-\sqrt{w}/2}(\sqrt{w}+2)\right]_{\infty}^{100}<10.326283.
\end{aligned}
\end{displaymath}
Here we used substitution followed by integration by parts.

We now consider the second set, $\mathscr{A}_2$.  We first show that $$Q(x)<0.01588\sqrt{x}$$ for all $x$.  A computer check shows that the claim holds for $x\le e^{22}$, that $Q(e^{22})=26$, and that
\begin{displaymath}
\mathop{\prod_{p\in \mathcal{Q}}}_{p \le e^{22}}p>e^{496.34447}.
\end{displaymath}
Assume that $x>e^{22}$.  We have
\begin{displaymath}
\begin{aligned}
\mathop{\prod_{p\in \mathcal{Q}}}_{p \le x} p<\prod_{t<x^{1/4}}2^t=\exp\left(\log 2\sum_{t<x^{1/4}}t\right)\le \exp\left(0.34799x^{1/2}\right),
\end{aligned}
\end{displaymath}
while also
\begin{displaymath}
\mathop{\prod_{p\in \mathcal{Q}}}_{p \le x}p=\mathop{\prod_{p\in \mathcal{Q}}}_{p \le e^{22}}p\mathop{\prod_{p\in \mathcal{Q}}}_{e^{22}<p \le x}p>e^{496.34447}\left(e^{22}\right)^{Q(x)-26}=e^{22Q(x)-75.65553},
\end{displaymath}
so that $Q(x)<0.01588x^{1/2}$ for all $x$ as claimed. We thus have
\begin{displaymath}
A_2(x)<\sum_{2\le m<x/y}0.01588\left(\frac{x}{m}\right)^{1/2}\le 0.01588x^{1/2}\int_1^{x/y} \frac{dt}{t^{1/2}}<\frac{0.03176x}{y^{1/2}}.
\end{displaymath}

By partial summation, we therefore have
\begin{displaymath}
\mathop{\sum_{n\in \mathscr{A}_2}}_{n>x_0}\frac{1}{n}\le \int_{x_0}^\infty \frac{0.03176~dt}{t\exp(\sqrt{(\log t)/4})}=\int_{100}^\infty \frac{0.03176~dw}{\exp(\sqrt{w/4})}<0.0102719.
\end{displaymath}

 Let $n\in \mathscr{A}_3$ and let $p=P(n)$.  Then $t_p\ge p^{1/4}>y^{1/4}$.  Following \cite{erdos1956pseudoprimes} we show that for such $n$ we have $n\equiv p$ (mod $pt_p$).  We clearly have $n\equiv p$ (mod $p$).  We also have $n\equiv p$ (mod $t_p$).  To see this, note that $n-p=(n-1)-(p-1)$.  We have $t_p|p-1$ by Fermat's little theorem, and $t_p|n-1$ since $n$ is a $2$-pseudoprime and $p|n$.  Since $t_p<p$ we have $\gcd(p,t_p)=1$, and thus also $n\equiv p$ (mod $pt_p$) as claimed.  Thus the number of such $n$ is bounded above by $x/(pt_p)+1$.  Also $n>p$ (since $p$ is not a pseudoprime), so the number of such $n$ is in fact bounded above by $x/(pt_p)$.  Thus the number of $2$-pseudoprimes in $\mathscr{A}_3$ satisfies
 \begin{displaymath}
 A_3(x)\le \sum_{p>y}\frac{x}{pt_p}\le x\sum_{p>y}\frac{1}{p^{5/4}}.
 \end{displaymath}
 By Lemma \ref{dusart1} we have $t/(\log t)\cdot (1+1/\log t)\le \pi(t)\le 1.1253816t/\log t$ for $t\ge y_0$.  Thus by partial summation we have
 \begin{displaymath}
 \begin{aligned}
 A_3(x)&\le x\left(-\frac{\pi(y)}{y^{5/4}}+\frac{5}{4}\int_y^\infty \frac{\pi(t)}{t^{9/4}}dt\right)\\
 &\le x\left(-\frac{1+1/\log y}{y^{1/4}\log y}+\frac{5(1.1253816)}{4}\int_y^\infty \frac{dt}{(\log t)t^{5/4}}\right)\\
 &=x\left(-\frac{1+1/\log y}{y^{1/4}\log y}-\frac{5.626908}{4}\text{Ei}\left(-\frac{\log y}{4}\right)\right)\\
 &=x\left(-\frac{1+1/\sqrt{\log x}}{\sqrt{\log x}\cdot \exp{\sqrt{(\log x)/16}}}-1.406727\cdot \text{Ei}\left(-\frac{\sqrt{\log x}}{4}\right)\right),
 \end{aligned}
 \end{displaymath}
where
\begin{displaymath}
\text{Ei}(x)=-\int_{-x}^\infty \frac{e^{-t}}{t}dt
\end{displaymath}
denotes the exponential integral function.  By another application of partial summation, we thus have
\begin{displaymath}
\begin{aligned}
\mathop{\sum_{n\in \mathscr{A}_3}}_{n>x_0}\frac{1}{n}&\le -\int_{x_0}^\infty \left(\frac{1+1/\sqrt{\log t}}{t\sqrt{\log t}\cdot \exp(\sqrt{(\log t)/16})}+\frac{1.406727\cdot \text{Ei}\left(-\frac{\sqrt{\log t}}{4}\right)}{t}\right)dt\\
&=-\int_{100}^\infty \frac{(1+1/\sqrt{w})~dw}{\sqrt{w}\cdot \exp(\sqrt{w/16})}-1.406727\int_{100}^\infty \text{Ei}\left(-\frac{\sqrt{w}}{4}\right)dw\\
&=-8e^{-2.5}+2\text{Ei}(-2.5)+1.406727\left(100\text{Ei}(-2.5)+56e^{-2.5}\right)\\
&<2.2550278.
\end{aligned}
\end{displaymath}
Here we substituted $w=\log t$ and used integration by parts. Adding the contributions from the small, middle and large ranges, we obtain
\begin{displaymath}
0.0152612+20.369621+12.5915827<32.9765,
\end{displaymath}
completing the proof of Theorem \ref{pseudoprimereciprocalsum}.

\section{The sum of reciprocals of the Carmichael numbers}

\begin{theorem}\label{Carmichaelreciprocalsum}
The sum of reciprocals of Carmichael numbers satisfies
\begin{displaymath}
0.004706<\sum_{n\in \mathscr{C}}\frac{1}{n}<27.8724.
\end{displaymath}
\end{theorem}

To prove Theorem \ref{Carmichaelreciprocalsum}, we modify the small, middle and large ranges from the proof of Theorem \ref{pseudoprimereciprocalsum} above.

\subsection{The small range: $n\le 10^{21}$}  A table of all $10000$ Carmichael numbers up to $1713045574801$ has been computed by R.~Pinch, \cite{Pinch,Pinch2}.  Their contribution to the reciprocal sum is easily computed to be $0.004706\ldots$.  Pinch also determined that there are $20128200$ additional Carmichael numbers up to $10^{21}$. Therefore an upper bound for the sum of reciprocals of all Carmichael numbers $n\le 10^{21}$ is given by 

\begin{displaymath}
0.004707+20128200/1713045574803<0.0047188.
\end{displaymath}

\subsection{The middle range: $10^{21}<n\le x_0=\exp(100)$}   
We will use the following slight modification of Lemma \ref{residueclasses}, whose proof is nearly identical.

\begin{lemma}\label{residueclasses2}
Let $a\in \mathbb{Z}$ and $\displaystyle d'=2\prod_{i=2}^{10} p_i^2$, where $p_i$ denotes the $i$-th prime number. We have
\begin{displaymath}
\mathop{\sum_{n\equiv a(d')}}_{10^{21}<n\le x_0}\frac{1}{n}<\frac{51.6882395}{d'}.
\end{displaymath}
\end{lemma}

Since Carmichael numbers are odd and squarefree by Lemma \ref{korselt}, they must lie in one of 
\begin{displaymath}
E=\prod_{i=2}^{10}(p_i^2-1)
\end{displaymath}
residue classes modulo $d'$.

We may also remove the contribution to the sum from prime numbers.  By Lemma \ref{mertens} we have
\begin{displaymath}
\sum_{10^{21}<p\le x_0}\frac{1}{p}>0.7266133.
\end{displaymath}

It follows from Lemma \ref{korselt} that Carmichael numbers have at least three prime factors, so we may also remove the contribution to the sum from odd, squarefree numbers in the middle range with exactly two prime factors. Let $\pi_2(x)=|\{n=pq\le x: p<q\}|$ denote the counting function of squarefree numbers with exactly two prime factors.  Similarly, let $\pi_2^*(x)=|\{n=pq\le x: 2<p<q\}|$ denote the counting function of odd squarefree numbers with exactly two prime factors.  By a slight modification of Bayless and Klyve's lower bound \cite{BaylessKlyve} on $\pi_2(x)$, we are able to show that for all $x\ge 10^{21}$, we have
\begin{displaymath}
\pi_2^*(x)\ge \frac{x(\log\log x-0.300711)}{\log x}.
\end{displaymath}
Letting $A^*$ denote the set of odd squarefree numbers with exactly two prime factors, we therefore obtain by partial summation that
\begin{displaymath}
\mathop{\sum_{10^{21}<n\le x_0}}_{n\in A^*}\frac{1}{n}\ge \frac{\log\log x_0-0.300711}{100}-\frac{\log\log 10^{21}-0.300711}{\log 10^{21}}+I,
\end{displaymath}
where
\begin{displaymath}
\begin{aligned}
I&=\int_{10^{21}}^{x_0}\frac{(\log\log t-0.300711)dt}{t\log t}=\int_{\log 10^{21}}^{100} \frac{(\log w-0.300711) dw}{w}\\
&=\left[\frac{\log^2 w}{2}-0.300711\log w\right]_{\log10^{21}}^{100}.
\end{aligned}
\end{displaymath}
It follows that 
\begin{displaymath}
\mathop{\sum_{10^{21}<n\le x_0}}_{n\in A^*}\frac{1}{n}> 2.8327533.
\end{displaymath}

Therefore, the contribution to the reciprocal sum from the middle range is bounded above by $$51.6882395E/d'-0.7266133-2.8327533<17.5412697.$$

\subsection{The large range: $n>x_0$} Finally, we bound the reciprocal sum over Carmichael numbers $n>x_0$.  Let $x>x_0$ and recall our definitions $y=\exp(\sqrt{\log x})$ and $y_0=y(x_0)=\exp(10)$.  Write $p=P(n)$.  We split the Carmichael numbers $n>x_0$ into two categories.  
\begin{enumerate}
\item $p \le y$
\item $p > y$.
\end{enumerate}
For $i=1,2$, write $\mathscr{B}_i$ for the set of Carmichael numbers $n\le x$ satisfying property $i$ above and put $B_i(x)=|\{n \in \mathscr{B}_i : n \le x\}|$.

By the same argument in the proof of Theorem \ref{pseudoprimereciprocalsum} above, we have
\begin{displaymath}
B_1(x)=\Psi(x,y)\le \frac{31.928253x}{\exp\left(0.5\sqrt{\log x}\right)}
\end{displaymath}
by Lemma \ref{psilemma}, and
\begin{displaymath}
\mathop{\sum_{n\in \mathscr{B}_1}}_{n>x_0}\frac{1}{n}<10.326283.
\end{displaymath}
We next determine an upper bound for $B_2(x)$.  Observe that if $p|n$ for a Carmichael number $n$, then $n\equiv p$ (mod $p(p-1)$).  To see this, we clearly have $p|n-p$.  Furthermore, since $n-p=(n-1)-(p-1)$ and since $p-1|n-1$ by Lemma \ref{korselt}, we have $p-1|n-p$.  It follows that 
$n\equiv p$ (mod $p(p-1)$), since $\gcd(p,p-1)=1$.

Therefore, the number of Carmichael numbers $n\le x$ which are divisible by a given prime $p$ is bounded above by $x/(p(p-1))$.  We therefore have
\begin{displaymath}
B_2(x)\le \sum_{p>y}\frac{x}{p(p-1)}=x\sum_{p>y}\frac{1}{p(p-1)}.
\end{displaymath}
By partial summation, we have
\begin{displaymath}
\begin{aligned}
\sum_{p>y}\frac{1}{p(p-1)}&=-\frac{\pi(y)}{y(y-1)}+\int_y^\infty \frac{\pi(t)(2t-1)~dt}{t^2(t-1)^2}\\
&\le -\frac{\pi(y)}{y^2}+\int_y^\infty \frac{0.112539\cdot 2t~dt}{t(t-1)^2}\\
&\le -\frac{1}{y\log y}\left(1+\frac{1}{\log y}\right)+\int_y^\infty \frac{0.11255\cdot 2~dt}{t^2}\\
&=\frac{0.2251}{y}-\frac{1}{y\log y}\left(1+\frac{1}{\log y}\right).
\end{aligned}
\end{displaymath}
Here we used Lemma \ref{dusart1} to bound \begin{displaymath}
\frac{t}{\log t}\left(1+\frac{1}{\log t}\right)\le \pi(t)\le 0.112539t
\end{displaymath} for all $t\ge y_0$.  Therefore, for all $x\ge x_0$ we have  
\begin{displaymath}
B_2(x)\le \frac{x}{y}\left(0.2251-\frac{1}{\log y}\left(1+\frac{1}{\log y}\right)\right).
\end{displaymath}
It follows by another application of partial summation that
\begin{displaymath}
\begin{aligned}
\mathop{\sum_{n\in \mathscr{B}_2}}_{n>x_0}\frac{1}{n}&\le \int_{x_0}^\infty \frac{1}{t\exp\sqrt{\log t}}\left(0.2251-\frac{1}{\sqrt{\log t}}\left(1+\frac{1}{\sqrt{\log t}}\right)\right)dt\\
&=\int_{100}^\infty \frac{1}{\exp\sqrt{w}}\left(0.2251-\frac{1}{\sqrt{w}}\left(1+\frac{1}{\sqrt{w}}\right)\right)dw<0.000126.
\end{aligned}
\end{displaymath}

Adding the contributions from the small, middle and large ranges, we obtain $0.0047188+17.5412697+10.326409<27.8724,$ completing the proof of Theorem \ref{Carmichaelreciprocalsum}.

\section{Concluding remarks}

It will take more work to substantially sharpen the upper bound on the sum of reciprocals of $2$-pseudoprimes.  In fact, the result is close to optimal for the arguments used, in the following sense.

Reworking the arguments for different choices of the cutoff $x=x_0$ for the large range, the coefficients appearing in the bounds for each case tend to vary relatively slowly.  Therefore we may attempt to roughly optimize the bound by minimizing the function
\begin{displaymath}
f(x)=0.0152612+0.37679(\log x-\log (10^{19}-d+1))-I+I_1+I_2+I_3,
\end{displaymath}
which represents the major contributions from the small, middle and large ranges to the reciprocal sum, where $d$ is as defined in Lemma \ref{residueclasses}, and
\begin{displaymath}
I=\log\log x-\log\log 10^{19}-\frac{0.2}{\log^3 x}-\frac{0.2}{\log^3 10^{19}},
\end{displaymath}
\begin{displaymath}
I_1=\int_{\log x}^\infty \frac{31.928253~dw}{\exp(\sqrt{w/4})},
\end{displaymath}
\begin{displaymath}
I_2=\int_{\log x}^\infty \frac{0.03176~dw}{\exp\sqrt{w/4}},
\end{displaymath}
\begin{displaymath}
I_3=-\int_{\log x}^\infty \left(\frac{1+1/\sqrt{w}}{\sqrt{w}\cdot\exp(\sqrt{w/16})}+1.406727\cdot \text{Ei}\left(-\frac{\sqrt{w}}{4}\right)\right)dw.
\end{displaymath}
Applying the fundamental theorem of calculus and again substituting $w=\log x$, the derivative is given by
\begin{displaymath}
f'(x)=\frac{1}{x}\left(0.37679-J-J_1-J_2+J_3\right),
\end{displaymath}
where
\begin{displaymath}
J=\frac{1}{w}+\frac{0.6}{w^4},
\end{displaymath}
\begin{displaymath}
J_1=\frac{31.928253}{\exp(\sqrt{w/4})},
\end{displaymath}
\begin{displaymath}
J_2=\frac{0.03176}{\exp(\sqrt{w/4})},
\end{displaymath}
and
\begin{displaymath}
J_3=\frac{1+1/\sqrt{w}}{\sqrt{w}\cdot\exp(\sqrt{w/16})}+1.406727\cdot \text{Ei}\left(-\frac{\sqrt{w}}{4}\right).
\end{displaymath}
Solving graphically for $w$, we find that the critical point is approximately $w\approx 79$ so that $x\approx \exp(79)$, and we have $f(\exp(79))\approx 32$.  This indicates that our cutoff of $x_0=\exp(100)$ for the large range is close to optimal for the method of argument used, especially keeping in mind that lowering the cutoff to $x_0=\exp(79)$ will in fact raise the constants appearing in the various upper bounds for the large range.

Furthermore, adjusting the coefficient in our definition of $y=e^{\sqrt{c \log x}}$ and reconsidering the argument, our choice of $c=1$ used above gave better bounds than larger or smaller values of $c$ that we also considered.  However, it may be possible to further optimize the choice of coefficients, including those used in the proof of Lemma \ref{psilemma} bounding the count of smooth numbers.

Another possible way to improve this bound would be to find a way to effectively utilize more information about the $2$-pseudoprimes.  For instance, more specific residue classes in the middle range could be ruled out using an inclusion-exclusion argument.

Perhaps the bound on the sum of reciprocals of Carmichael numbers could be further optimized by utilizing more information about them, as well as optimizing the cutoff $x_0$.  Another possibility for improving the bound for the sum of reciprocals of Carmichael numbers in the middle range is to use an inclusion-exclusion argument to remove not only the odd squarefree numbers with exactly two prime factors, but also the ones which fall in certain specific residue classes that can be ruled out.

Furthermore, Damg{\aa}rd et al \cite[Thm.\ 5]{DLP} proved that for all $x\ge 1$, the number $N(x)$ of Carmichael numbers up to $x$ with exactly three prime factors satisfies the upper bound
\begin{displaymath}
N(x)\le 0.25\sqrt{x}(\log x)^{11/4}.
\end{displaymath}
Obtaining an explicit lower bound on the count of odd, squarefree numbers up to $x$ having exactly three prime factors would therefore allow one to remove the contribution from all such numbers in the middle range and replace it using this tighter bound.

\section{Acknowledgments}
The authors would like to thank the referees for suggestions improving both the writing and the mathematics of this paper.

\begin{thebibliography}{99}

\bibitem{alford1994there}
W. R. Alford, A. Granville, and C. Pomerance,  There are infinitely many Carmichael numbers.  \textit{Ann. of Math.} \textbf{139} (1994), 703--722.

\bibitem{apostol2013introduction}
T. Apostol,  \textit{Introduction to Analytic Number Theory}, Springer Science \& Business Media, 2013.

\bibitem{phipaper}
J. Bayless and P. Kinlaw,  On consecutive coincidences of Euler's function. \textit{Int. J. Number Theory} \textbf{12} (2015), 1011--1026.

\bibitem{bayless2011sum}
J. Bayless and D. Klyve,  On the sum of reciprocals of amicable numbers.  \textit{Integers} \textbf{11} (2011), 315--322.

\bibitem{bayless2013reciprocal}
J. Bayless and D. Klyve,  Reciprocal sums as a knowledge metric: theory, computation, and perfect numbers.  \textit{Amer. Math. Monthly} \textbf{120} (2013), 822--831.

\bibitem{BaylessKlyve}
J. Bayless and D. Klyve, Sums over primitive sets with a fixed number of prime factors.  \textit{Submitted.}

\bibitem{CP}
R. Crandall and C. Pomerance, \textit{Prime Numbers: A Computational
Perspective}, Lecture Notes in Statistics,
Vol.~182, Springer Science \& Business Media, 2006.

\bibitem{DLP}
I. Damg{\aa}rd, P. Landrock, and C. Pomerance, Average case error estimates for the strong probable prime test. {\it Math.~Comp.} \textbf{61} (1993), 177--194.

\bibitem{de2012analytic}
J. M. De Koninck and F. Luca,  \textit{Analytic Number Theory:
Exploring the Anatomy of Integers}, Graduate Studies in Mathematics,
Vol.~134, Amer. Math. Soc., 2012.

\bibitem{dusart}
P. Dusart,  Explicit estimates of some functions over primes.
\textit{Ramanujan J.} (2016), 1--25.

\bibitem{erdos1956pseudoprimes}
P. Erd\H{o}s,  On pseudoprimes and Carmichael numbers.  \textit{Publ. Math. Debrecen} \textbf{4} (1956), 201--206.

\bibitem{Feitsma}
J. Feitsma, Pseudoprimes, 2013, \url{http://www.janfeitsma.nl/math/psp2/index}.

\bibitem{Harman}
G. Harman,  Watt's mean value theorem and Carmichael numbers. \textit{Int. J. Number Theory} \textbf{4} (2008), 241--248.

\bibitem{Hanh}
H. Nguyen, The reciprocal sum of the amicable numbers. Dartmouth
College undergraduate honors thesis, Hanover, NH, 2014.

\bibitem{Pinch}
R. Pinch, The Carmichael numbers up to $10^{21}$, \textit{Proceedings
of the Conference on Algorithmic Number Theory, Turku Centre for
Computer Science} \textbf{7} (2007), 129--131.

\bibitem{Pinch2}
R. Pinch, Tables relating to Carmichael numbers, 2005,\\
\url{http://www.chalcedon.demon.co.uk/rgep/cartable.html}.

\bibitem{platttrudgian}
D. Platt and T. Trudgian,  On the first sign change of $\theta(x)-x$.
{\it Math.~Comp.} \textbf{85} (2016), 1539--1547.

\bibitem{Pomerance}
C. Pomerance, On the distribution of pseudoprimes. \textit{Math.~Comp.}
\textbf{37} (1981), 587--593.

\bibitem{barkley1962approximate}
J. B. Rosser and L. Schoenfeld, Approximate formulas for some functions
of prime numbers. \textit{Illinois J. Math.} \textbf{6} (1962),
64--94.

\bibitem{schoenfeld1976sharper}
L. Schoenfeld,  Sharper bounds for the Chebyshev functions $\theta(x)$
and $\psi(x)$. II, {\it Math.~Comp.} \textbf{6} (1976), 243--269.
\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 11N25; Secondary 11Y99.

\noindent \emph{Keywords: } Carmichael number, pseudoprime, reciprocal sum, smooth number.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A001567} and \seqnum{A002997}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received April 7 2017;
revised versions received  May 31 2017; June 7 2017.
Published in {\it Journal of Integer Sequences}, June 25 2017.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}


.