\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}

\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{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}

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

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

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

\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 The Reciprocal Sum of Even Pseudoprimes} \\
\ \\
\large
Xuyan Cheng\\
Department of Computer Science and Engineering\\
The Ohio State University\\
Columbus, OH 43201\\
USA\\
\href{mailto:cheng.2119@osu.edu}{\tt cheng.2119@osu.edu} \\

\ \\
Paul Kinlaw\\
College of Arts and Sciences\\
The University of Maine at Presque Isle\\
Presque Isle, ME 04769\\
USA\\
\href{mailto:paulkinlaw1@gmail.com}{\tt paulkinlaw1@gmail.com} \\

\ \\
Duc Nguyen\\
Department of Mathematics\\
Dickinson College\\
28N College St. \\
Carlisle, PA 17013\\
USA\\
\href{mailto:nguyenduc150202@gmail.com}{\tt nguyenduc150202@gmail.com} 
\end{center}

\vskip .2 in

\begin{abstract}
A pseudoprime is a composite integer $N$ that mimics the behavior of primes by satisfying the congruence $2^N\equiv \modd{2} {N}$ in Fermat's little theorem. This paper focuses on the subset of even pseudoprimes and obtains an upper bound for the sum of their reciprocals. Our approach combines analytic arguments with computational verification, showing that this sum is less than 0.0059.
\end{abstract}


\section{Introduction}

By Fermat's little theorem, if $a$ is an integer and $p$ is a prime, then $a^p\equiv \modd{a} {p}$.  However, for each $a\ge 2$, the congruence also holds for some composite moduli called \textit{base-$a$ (Fermat) pseudoprimes}.  It is well known that for each $a\ge 2$, there are infinitely many pseudoprimes.  The base-$2$ pseudoprimes are also called \textit{pseudoprimes} for short.  We study even pseudoprimes, that is, even numbers $N>2$ such that $2^N\equiv \modd{2} {N}$. The smallest even pseudoprime is $161038$ and Beeger \cite{beeger1951} proved that there are infinitely many.  The first $1318$ even pseudoprimes have been computed by Alekseyev (extending work of Pinch), providing an exhaustive list up to $2\cdot 10^{15}$. This sequence is referenced as \seqnum{A006935} in the On-Line Encyclopedia of Integer Sequences \cite{oeis}. Pomerance and Wagstaff \cite{pomerance2021} later extended the exhaustive search up to $10^{16}$, and there are $727$ even pseudoprimes in the range $2\cdot 10^{15}<N\le 10^{16}$.

Let $\mathcal{E}=\{161038,215326,2568226,\ldots\}$ denote the set of all even pseudoprimes.  We prove the following bounds on the sum of reciprocals of even pseudoprimes.

\begin{theorem}\label{mainthm}
We have
    \begin{displaymath}
        0.000011 < \sum_{N\in \mathcal{E}}\frac{1}{N} < 0.0059.
    \end{displaymath}
\end{theorem}
\noindent In particular, this determines the numerical value of the reciprocal sum to two decimal places as $0.00\ldots$.  It is known \cite{bayless2017,kinlaw2023} that the reciprocal sum of odd pseudoprimes is less than $0.0911$.  Thus, as a corollary, the sum of reciprocals of all base-$2$ pseudoprimes is less than $0.1$.  

\section{Notation and preliminary lemmas}

Throughout the paper, $x$ denotes a real variable, $x_0 = e^{36}$, $p$ denotes a prime variable (with or without subscripts), and $\log x$ denotes the natural logarithm.  We let $Y_0 = 6.5\cdot 10^7$.  We also define $y_k = e^{1.56\sqrt{k}}$ and $z_k = e^{k/2}/(2\sqrt{2})$ for $k\ge 36$.  We let $a_1 = 0.4$ and $a_2 = 0.48$.  For a prime $p>2$, let the expression $\ell_2(p)$ denote the multiplicative order of $2$ mod $p$, that is, the smallest positive integer such that $2^{\ell_2(p)}\equiv \modd{1} {p}$.  In general, if $2^k\equiv \modd{1} {p}$ for some integer $k\ge 0$, then $\ell_2(p) \mid k$.  In particular, by Fermat's little theorem, $\ell_2(p) \mid p-1$.  

Note that $N=2n\in \mathcal{E}$ if and only if $n>1$ and
\begin{equation}\label{n}
    2^{2n-1}\equiv \modd{1} {n} .
\end{equation}

In particular, $n$ must be odd.  We have the following additional properties of even pseudoprimes.

\begin{lemma}\label{pl2p}
    For every odd prime $p$ dividing an even pseudoprime $N$, we have
    \begin{equation}\label{pl2pcongruence}
        N\equiv \modd{p} {p\ell_2(p)}.
    \end{equation}
    Moreover, $\ell_2(p)$ is odd, $p\equiv \pm \modd{1} {8}$, and $p\le N/14$.
\end{lemma}

\begin{remark}
    The congruence Eq.~\eqref{pl2pcongruence} above holds for all pseudoprimes.
\end{remark}

Before proving Lemma \ref{pl2p}, we note the following corollary, which follows from the fact that any even pseudoprime is of the form $2p_1\cdots p_r$, where each $p_i\equiv \pm \modd{1} {8}$.

\begin{corollary}\label{cor1}
    If $N$ is an even pseudoprime then $N\equiv 2~\text{or}~\modd{14} {16}$.
\end{corollary}

\begin{proof}[Proof of Lemma \ref{pl2p}]
    For an even pseudoprime $N=2n$, we have $2^{2n-1}\equiv \modd{1} {n}$ by 
    Eq.~\eqref{n}. Therefore, if $p \mid n$, then $2^{2n-1}\equiv \modd{1} {p}$, and thus $\ell_2(p) \mid 2n-1$, so that $2n\equiv \modd{1} {\ell_2(p)}$.  Therefore, $\ell_2(p)$ is odd. Also, $p\equiv \modd{1} {\ell_2(p)}$ by Fermat's little theorem, so by the last two congruences we have $2n\equiv \modd{p} {\ell_2(p)}$.  Also, $2n\equiv \modd{p} {p}$ (as both sides are $\modd{0} {p}$).  Moreover, $\gcd(p,\ell_2(p))=1$ because $\ell_2(p) \mid p-1$.  Therefore, $N=2n$ satisfies the congruence $N\equiv \modd{p} {p\ell_2(p)}$.

Note also that $N>p$ because $N$ is composite.  Next, note that we have $\ell_2(p) \mid (p-1)/2$ because $\ell_2(p)$ is odd.  Therefore, by Euler's criterion, $(2|p)\equiv 2^{(p-1)/2}\equiv \modd{1} {p}$, where $(2|p)$ is the Legendre symbol.  Thus $(2|p)=1$, so $p\equiv \pm \modd{1} {8}$.  We now show that $p\le N/14$.  The congruence $2^{2n-1}\equiv \modd{1} {n}$, which holds for $n=N/2$, implies that $n$ is odd, so that $N=2mp$ for some odd $m\ge 1$.  Moreover, $m\ne 1$, for otherwise $N=2p$ and thus $2^{2p-1}\equiv \modd{1} {p}$, which is impossible since by Fermat's little theorem, $2^{2p-2}\equiv \modd{1} {p}$.  Also, $m\ne 3,5$ because the odd prime factors $p$ of $N$ are of the form $\pm \modd{1} {8}$. Therefore, $m\ge 7$.
\end{proof}

We use the fact that pseudoprimes are almost squarefree, in a sense made precise by the following lemma.

\begin{lemma}\label{sqfr}
    If $N$ is an even pseudoprime and $p^2\mid N$ for a prime $p$, then $p$ is a \textit{Wieferich prime}, i.e., $2^{p-1}\equiv \modd{1} {p^2}$. 
 In particular, $p\ge 3511$.
\end{lemma}

\begin{proof}
    The first assertion holds for all pseudoprimes by an argument similar to previous work \cite[Lemma 2]{bayless2017}.  The second assertion follows from the fact that the two smallest Wieferich primes are $1093$ and $3511$, together with the fact that $1093\equiv \modd{5} {8}$, and so by Lemma \ref{pl2p} an even pseudoprime cannot be divisible by $1093$.
\end{proof}

We also use the following bounds of Dusart \cite{dusart2016} on the prime counting function $\pi(x)$.

\begin{lemma}\label{primepi}
We have
\begin{displaymath}
    \frac{x}{\log x}\left(1+\frac{1}{\log x}\right) \le \pi(x) \le \frac{x}{\log x}\left(1+\frac{1.2762}{\log x}\right),
\end{displaymath}
where the lower bound holds for all $x\ge 599$ and the upper bound holds for all $x>1$.
\end{lemma}

We use partial summation (Abel's summation identity) \cite[Theorem 4.2]{apostol2013} to represent sums in terms of integrals.

\begin{lemma}\label{abel}
    Let $\{a_n\}_{n\ge 1}$ be a sequence of real or complex numbers, and let $f$ have a continuous derivative on the interval $[x_1,x]$, $0<x_1 < x$.  Let $A(t) = \sum_{n\le t}a_n$.  Then 
    \begin{displaymath}
        \sum_{x_1<n\le x}a_n f(n) = A(x)f(x)-A(x_1)f(x_1) - \int_{x_1}^x A(t)f'(t)~dt.
    \end{displaymath}
    In particular, if $\mathcal{A}$ is a set of natural numbers and we define $a_n=1$ if $n\in \mathcal{A}$ and $a_n=0$ otherwise, then the above equality holds where $A$ is the counting function of the set $\mathcal{A}$. 
\end{lemma}

We also use a result of Nguyen and Pomerance \cite[Lemmas 2.9--2.10, Remark 2.1]{nguyen2019} on the reciprocal sum of integers $n > x$ free of prime factors exceeding a given bound $y$.  (Such numbers are called $y$-\textit{smooth} or $y$-\textit{friable}.) Let the expression $P(n)$ denote the largest prime factor of $n$,~~$(n>1)$, with the convention $P(1)=1$.  For $2\le y < x$ and $s>0$, let 
\begin{displaymath}
\zeta(s,y) = \sum_{P(n)\le y}\frac{1}{n^s},
\end{displaymath}
where the sum is over all positive integers $n$ which are products only of primes less than or equal to $y$.  Note that we have
\begin{displaymath}
\zeta(s,y) = \sum_{P(n)\le y}\frac{1}{n^s} = \prod_{p\le y}\left(1+\frac{1}{p^s}+\frac{1}{p^{2s}}+\cdots\right)= \prod_{p\le y}\left(1+\frac{1}{p^s-1}\right),
\end{displaymath}
where the first equality holds by unique prime factorization, and the second equality holds by summing the geometric series.  Also, let
\begin{displaymath}
\zeta^*(s,y) = \mathop{\sum_{P(n)\le y}}_{2\,\nmid\, n,~n~\text{squarefree}}\frac{1}{n^s} = \prod_{3\le p\le y}\left(1+\frac{1}{p^s}\right)
\end{displaymath}
denote the restriction to $y$-smooth numbers which are odd and squarefree (that is, not divisible by $p^2$ for any prime $p$). 
 Define
\begin{displaymath}
S(x,y) = \mathop{\sum_{n>x}}_{P(n)\le y}\frac{1}{n},\quad S^*(x,y) = \mathop{\sum_{n>x}}_{2\,\nmid\, n,\, n~\text{squarefree},\, P(n)\le y}\frac{1}{n}.
\end{displaymath}

\begin{lemma}[Nguyen and Pomerance, \cite{nguyen2019}]\label{smooth}
For $2\le y < x$ and $0<s<1$, we have
\begin{equation}\label{smooth1}
S(x,y) \le x^{-s}\zeta(1-s,y).
\end{equation}
Let $u=\log x/\log y$ and $s=\log(u\log u)/\log y$.  For $u\ge 3$ and $s\le 1/3$, we have
\begin{equation}\label{smooth2}
S(x,y) \le x^{-s}\zeta(1-s,y) < 25e^{(1+\epsilon)u}(u\log u)^{-u}(2^{s}-1)^{-1},
\end{equation}
where $\epsilon = 2.3\cdot 10^{-8}$. 
\end{lemma} 

\begin{remark}\label{sfandalmostsf}
Following \cite[Remark 2.1]{nguyen2019}, for $2\le y < x$ and $0<s<1$, we have
\begin{equation}\label{smoothsf}
   S^*(x,y) \le x^{-s}\zeta^*(1-s,y). 
\end{equation}

We note that more generally, for a given prime $p$, if the sum $S(x,y)$ is restricted by the assumption that $p^2\, \nmid\, n$, then we can replace the factor $1+1/(p^s-1)$ with $1+1/p^s$ in the product defining $\zeta(s,y)$.  Similarly, given the stronger restriction $p\, \nmid\, n$, we can remove the factor $1+1/(p^s-1)$ in the product defining $\zeta(s,y)$.
\end{remark}

For fixed real numbers $0\le a < b\le 1$, we define $\mathcal{Q}_{a,b}=\{p>2: 
2 \,\nmid\, \ell_2(p)~\text{and}~p^a < \ell_2(p) \le p^b\}$.  We let $Q_{a,b}(x)=|\mathcal{Q}_{a,b}\cap [1,x]|$.  Recall that $a_1=0.4$ and $a_2=0.48$.  
We use the following modification of previous work \cite[Inequality (8)]{kinlaw2023}.

\begin{lemma}\label{Q}
We have 
\begin{displaymath}
    Q_{0,a_1}(x) < Mx^{2a_1}
\end{displaymath}
for all $x\ge 0$, where $M=0.00754$.  Moreover, $Q_{a_1,a_2}(x) < Mx^{2a_2}$ for all $x\ge 337$.
\end{lemma}

\begin{proof}
    We prove the claim for $Q_{0,a_1}$, noting that an analogous argument deals with the case of $Q_{a_1,a_2}$. (For $x>e^{23}$, we use the trivial inequality $Q_{a_1,a_2}\le Q_{0,a_2}$.)  We find by a computer check in Pari/GP \cite{pari2022} that the claim holds for all $x\le e^{23}$,
$Q_{0,a_1}(e^{23})=638$, and 
\begin{displaymath}
\mathop{\prod_{p\in \mathcal{Q}_{0,a_1}}}_{p\le e^{23}}p > e^D
\end{displaymath}
where $D=12895$.  Let $x>e^{23}$.  If $p\le x$ and $p\in \mathcal{Q}_{0,a_1} $, then $p \mid 2^m-1$ for some odd $m>1$ such that $m < p^{a_1} \le x^{a_1}$, so that
\begin{displaymath}
\mathop{\prod_{p\in \mathcal{Q}_{0,a_1}}}_{p\le x} p \mid  \mathop{\prod_{m\le x^{a_1}}}_{2 \, \nmid\, m}(2^m-1).
\end{displaymath}
Therefore,
\begin{equation}\label{primeproductestimate}
\begin{aligned}
\mathop{\prod_{p\in \mathcal{Q}_{0,a_1}}}_{p\le x} p
    &\le \mathop{\prod_{m\le x^{a_1}}}_{2\, \nmid\, m}(2^m-1) \\
    &\le \exp\left(\log 2\mathop{\sum_{m\le x^{a_1}}}_{2\, \nmid\, m}m\right)
    \le \exp\left(\log 2\left(\frac{x^{a_1}+1}{2}\right)^2\right) \\
    &\le \exp\left(\frac{\log 2}{4}(1.00021)x^{2a_1}\right)
    \le \exp(0.17333x^{2a_1}).
\end{aligned}
\end{equation}

Here, we used the formula $1+3+5+\cdots+(2j-1)=j^2$ for the sum of the first $j$ odd numbers, with $j=\lfloor(x^{a_1}+1)/2\rfloor$.  Also,
\begin{displaymath}
\mathop{\prod_{p\in \mathcal{Q}_{0,a_1}}}_{p\le x} p = \mathop{\prod_{p\in \mathcal{Q}_{0,a_1}}}_{p\le e^{23}} p \mathop{\prod_{p\in \mathcal{Q}_{0,a_1}}}_{e^{23}<p\le x} p > e^{D}(e^{23})^{Q_{0,a_1}(x)-Q_{0,a_1}(e^{23})},
\end{displaymath}
where the lower bound on the rightmost product is obtained by replacing each factor $p$ with $e^{23}$.  We therefore have
\begin{displaymath}
Q_{0,a_1}(x) \le Q_{0,a_1}(e^{23})-D/23+0.17333x^{2a_1}/23 = 638-12895/23+0.17333x^{2a_1}/23
\end{displaymath}
for all $x\ge e^{23}$.  Simplifying, we complete the proof of Lemma \ref{Q}.\qedhere
\end{proof}

\section{The reciprocal sum of even pseudoprimes}

To bound the reciprocal sum we split $\mathcal{E}$ into two ranges.  The small range consists of $N\in \mathcal{E}$ such that $N\le 10^{16}$.  Using the exhaustive list for $N\le 2\cdot 10^{15}$, and noting that there are $727$ terms in the interval $(2\cdot 10^{15},10^{16}]$, contributing less than $727/(2\cdot 10^{15})$ to the reciprocal sum, we obtain 
\begin{equation}\label{smallrange}
    \mathop{\sum_{N\in \mathcal{E}}}_{N\le 10^{16}}\frac{1}{N} = 0.0000118853\ldots.
\end{equation}
We are grateful to Mark Royer for computing this sum to high precision using Python.

The large range consists of $N\in \mathcal{E}$ such that $N>x_0$, where $x_0 = e^{36}$.  Note that $10^{16} > e^{36}$, so there is no gap between the small and large ranges.  Recall that $Y_0=6.5\cdot 10^7$, $y_k=e^{1.56\sqrt{k}}$, and $z_k = e^{k/2}/(2\sqrt{2})$, $k\ge 36$.  We determine an upper bound by splitting $\mathcal{E}\cap (e^{36},\infty)$ into intervals $(e^k,e^{k+1})$, $k\ge 36$.  First, we partition $\mathcal{E}$ into five subsets depending on the relative sizes of $p=P(N)=P(n)$ and $\ell_2(p)$ as follows:

\begin{displaymath}
\begin{aligned}
\mathcal{A}_1 &= \{N\in \mathcal{E}: p\le y_{\lfloor \log N\rfloor}\}\\
\mathcal{A}_2 &= \{N\in \mathcal{E}: e^{36}<N\le e^{130}, y_{\lfloor \log N\rfloor}<p\le \min(Y_0,z_k)\}\\
\mathcal{A}_3 &= \{N\in \mathcal{E}\setminus \mathcal{A}_2: p > y_{\lfloor \log N\rfloor},~\text{and}~p\in \mathcal{Q}_{0,a_1}\}\\
\mathcal{A}_4 &= \{N\in \mathcal{E}\setminus \mathcal{A}_2: p > y_{\lfloor \log N\rfloor},~\text{and}~p\in \mathcal{Q}_{a_1,a_2}\}\\
\mathcal{A}_5 &= \{N\in \mathcal{E}\setminus \mathcal{A}_2: p > y_{\lfloor \log N\rfloor},~\text{and}~p\in \mathcal{Q}_{a_2,1}\}.\\
\end{aligned}
\end{displaymath}

We further partition $\mathcal{A}_2$ into the cases $36\le k\le 38$, $y_k < p\le z_k$ and $39\le k\le 130, y_k < p\le Y_0$.  For $2\le i\le 5$ we further partition $\mathcal{A}_i$ into the cases $39\le k\le 130, Y_0 < p\le z_k$, $k\ge 131, y_k < p\le z_k$, and $k\ge 36, p>z_k$.  This partition is inspired by previous work \cite[Theorem 9.11]{dekoninck2023}, \cite[Theorem 1]{kinlaw2023} on the reciprocal sum of odd pseudoprimes.  

We first bound the sum over $N = 2n\in \mathcal{A}_1\cap (e^k,e^{k+1})$, $k\ge 36$.  Recall that $n$ is odd, and by Lemma \ref{pl2p}, $n$ is not divisible by any prime $p$ such that $\ell_2(p)$ is even.  Moreover, by Lemma \ref{sqfr}, $n$ is not divisible by $p^2$ for any prime $p<3511$.  Using Remark \ref{sfandalmostsf}, we find that
\begin{displaymath}
\mathop{\sum_{N=2n\in \mathcal{A}_1}}_{N > x_0}\frac{1}{N} = \frac{1}{2}\mathop{\sum_{2n\in \mathcal{A}_1}}_{n > \frac{x_0}{2}}\frac{1}{n} = \frac{1}{2}\sum_{k\ge 36}\mathop{\sum_{2n\in \mathcal{A}_1}}_{\frac{e^{k}}{2}<n\le \frac{e^{k+1}}{2}}\frac{1}{n} < \frac{0.004024+0.002251}{2} < 0.003138.
\end{displaymath}
Specifically, the term $0.004024$ comes from the range $36\le k\le 120$ using 
Eq.~\eqref{smooth1} and Remark \ref{sfandalmostsf} with $s=\log(e^{0.8}u\log u)/\log y$, and the term $0.002251$ comes from the range $k>120$ using Eq.~\eqref{smooth2} and Remark \ref{sfandalmostsf}.

We now turn to the cases $\mathcal{A}_i$, $i=2,3,4,5$.  By Lemma \ref{pl2p} and Corollary \ref{cor1}, we have
\begin{equation}\label{keybound}
    \mathop{\sum_{N\in \mathcal{E}\setminus \mathcal{A}_1}}_{N>x_0}\frac{1}{N}\le  \ \sum_{k\ge 36}\mathop{\sum_{p>y_k}}_{2\, \nmid\, \ell_2(p)}\ \sum_{\substack{e^k<N\le e^{k+1}\\ N\equiv  \modd{p} {p\ell_2(p)}\\ N\equiv \pm \modd{2} {16}\\ N>p}}\frac{1}{N}.
\end{equation}
We split this sum into cases depending on the values of $k$ and $p$.

The condition $N>p$ is redundant since $N$ is even (and composite), however, it is useful in the following argument.  If we set aside the condition $N\equiv \pm \modd{2} {16}$, we obtain an estimate that works well for large values of $p$, specifically $p> z_k$.  The counting function
\begin{displaymath}
    g_p(t):= |\{N\le t: N\equiv \modd{p} {p\ell_2(p)}~\text{and}~N>p\}|
\end{displaymath}
of numbers exceeding $p$ that are congruent to $p$ mod $p\ell_2(p)$ satisfies
\begin{equation}\label{floorformula}
    g_p(t)= \left\lfloor \frac{t-p}{p\ell_2(p)}\right\rfloor,~~~(t\ge p).
\end{equation}
Thus by partial summation (Lemma \ref{abel}) we have
\begin{displaymath}
\begin{aligned}
    \sum_{\substack{e^k<N\le e^{k+1}\\ N\equiv \modd{p} {p\ell_2(p)}\\ N>p}}\frac{1}{N} &= \frac{g_p(e^{k+1})}{e^{k+1}} - \frac{g_p(e^{k})}{e^{k}} +\int_{e^k}^{e^{k+1}}\frac{g_p(t)}{t^2}~dt\\
    &\le \frac{g_p(e^{k+1})}{e^{k+1}} - \frac{g_p(e^{k})}{e^{k}} +\int_{e^k}^{e^{k+1}}\frac{1}{t^2}\left(\frac{t-p}{p\ell_2(p)}\right)~dt.\\
\end{aligned}
\end{displaymath}
Integrating directly, we have

\begin{displaymath}
    \int_{e^k}^{e^{k+1}}\frac{1}{t^2}\left(\frac{t-p}{p\ell_2(p)}\right)~dt = \frac{1}{p\ell_2(p)} + \frac{e^{-(k+1)}-e^{-k}}{\ell_2(p)}.
\end{displaymath}
This allows us to obtain the following upper bound.

\begin{displaymath}
\begin{aligned}
    F_p(k): = \sum_{\substack{e^k<N\le e^{k+1}\\ N\equiv \modd{p} {p\ell_2(p)}\\ N>p}}\frac{1}{N} \le \frac{1}{e^{k+1}}\left\lfloor \frac{e^{k+1}-p}{p\ell_2(p)}\right\rfloor - \frac{1}{e^{k}} \left\lfloor\frac{e^{k}-p}{p\ell_2(p)}\right\rfloor+\frac{1}{p\ell_2(p)} + \frac{e^{-(k+1)}-e^{-k}}{\ell_2(p)}.
\end{aligned}
\end{displaymath}

Removing the second and fourth terms, which are nonpositive, we obtain the following proposition.

\begin{proposition}\label{prop2}
For odd primes $p$, we have 
\begin{displaymath}
    F_p(k) = \sum_{\substack{e^k<N\le e^{k+1}\\ N\equiv \modd{p} {p\ell_2(p)}\\ N>p}}\frac{1}{N} \le \frac{2}{p\ell_2(p)}.
\end{displaymath}
\end{proposition}

Next, we obtain an improvement when $p\le z_k := e^{k/2}/\sqrt{8}$ by using the condition $N\equiv 2~\text{or}~\modd{14} {16}$.  We also have
$N\equiv \modd{p} {p\ell_2(p)}$, and additionally, $\gcd(p\ell_2(p),16)=1$ when $p$ and $\ell_2(p)$ are odd.  Thus by the Chinese remainder theorem, $N$ lies within two residue classes modulo $16p\ell_2(p)$.  The counting function is therefore
\begin{displaymath}
    f_p(t) := |\{N\le t: N\equiv \modd{p} {p\ell_2(p)}, N\equiv \pm \modd{2} {16}\}|\le 2\left(\frac{t}{16p\ell_2(p)}+1\right).
\end{displaymath}
Also,
\begin{displaymath}
    f_p(t) \ge  2\left\lfloor\frac{t}{16p\ell_2(p)}\right\rfloor.
\end{displaymath}
Using the upper bound for $f_p(t)$ and proceeding as above, we have
\begin{displaymath}
\begin{aligned}
    \sum_{\substack{e^k<N\le e^{k+1}\\ N\equiv \modd{p} {p\ell_2(p)}\\ N\equiv \pm \modd{2} {16}}}\frac{1}{N} &=\frac{f_p(e^{k+1})}{e^{k+1}} - \frac{f_p(e^{k})}{e^{k}} +\int_{e^k}^{e^{k+1}}\frac{f_p(t)}{t^2}~dt\\
    &\le \frac{1}{4p\ell_2(p)}+\frac{2}{e^k}-\frac{f_p(e^k)}{e^k}.
\end{aligned}
\end{displaymath}
Now $f_p(e^k)\ge 2$ when $16p\ell_2(p)\le e^k$.  In particular, with $\ell_2(p)$ odd, we have $\ell_2(p)\le (p-1)/2$, so the inequality $16p\ell_2(p)\le e^k$ holds for $p\le z_k$.  

On the other hand, we have
\begin{displaymath}
    f_p(t) \ge  2\left\lfloor\frac{t}{16p\ell_2(p)}\right\rfloor\ge 2\left(\frac{t}{16p\ell_2(p)}-1\right).
\end{displaymath}

This gives
\begin{displaymath}
\begin{aligned}
    \sum_{\substack{e^k<N\le e^{k+1}\\ N\equiv \modd{p} {p\ell_2(p)}\\ N\equiv \pm \modd{2} {16}}}\frac{1}{N} &\le \frac{1}{8p\ell_2(p)}+\frac{4}{e^k}.
\end{aligned}
\end{displaymath}

In the case of $\mathcal{A}_3$ and $\mathcal{A}_4$, for $p\le z_k$, we also have $\ell_2(p) < p^{0.4}$ and $\ell_2(p) < p^{0.48}$, respectively.  

We summarize these bounds in the following Proposition.
\begin{proposition}\label{improvement}
If $p$ and $\ell_2(p)$ are odd, then we have
\begin{displaymath}
    \begin{aligned}
    \sum_{\substack{e^k<N\le e^{k+1}\\ N\equiv \modd{p} {p\ell_2(p)}\\ N\equiv \pm \modd{2} {16}}}\frac{1}{N} &\le \frac{1}{4p\ell_2(p)}
\end{aligned}
\end{displaymath}
whenever $16p\ell_2(p)\le e^k$, and in particular when $p\le z_k$.  Moreover,
\begin{displaymath}
    \begin{aligned}
    \sum_{\substack{e^k<N\le e^{k+1}\\ N\equiv \modd{p} {p\ell_2(p)}\\ N\equiv \pm \modd{2} {16}}}\frac{1}{N} &\le \frac{1/8+4e^{-k}p\ell_2(p)}{p\ell_2(p)}.
\end{aligned}
\end{displaymath}
When $p\le z_k$ and $\ell_2(p)<p^{0.4}$ (respectively, $\ell_2(p)<p^{0.48}$), this is bounded above by $c_k/(p\ell_2(p))$ (respectively, $d_k/(p\ell_2(p))$) where $c_k = 1/8+(4/8^{0.7})e^{-0.3k}$ and $d_k = 1/8+(4/8^{0.74})e^{-0.26k}$.
\end{proposition}




We now consider $\mathcal{A}_2$.  We apply Proposition \ref{improvement} to bound 

\begin{displaymath}
    \mathop{\sum_{N\in \mathcal{A}_2}}_{N > x_0}\frac{1}{N} \le  \sum_{36\le k\le 38}\mathop{\sum_{y_k < p\le z_k}}_{2\, \nmid\, \ell_2(p)}\frac{1}{4p\ell_2(p)} + \sum_{39\le k\le 130}\mathop{\sum_{y_k < p\le Y_0}}_{2\, \nmid\, \ell_2(p)}\frac{1}{4p\ell_2(p)} < 0.000070
\end{displaymath}
by direct computation.

We next consider $\mathcal{A}_3$.  Note that $p \mid 2^{\ell_2(p)}-1$, so that $\ell_2(p)>\log p/\log 2$.  We therefore have
\begin{displaymath}
\mathop{\sum_{y_k < p \le z_k}}_{p\in \mathcal{Q}_{0,a_1}}\frac{1}{p\ell_2(p)}\le \log 2\mathop{\sum_{p>y_k}}_{p\in \mathcal{Q}_{0,a_1}}\frac{1}{p\log p}.
\end{displaymath}
By partial summation (Lemma \ref{abel}), the rightmost sum above is equal to
\begin{displaymath}
\log 2\left(-\frac{Q_{0,a_1}(y_k)}{y_k\log y_k}+\int_{y_k}^\infty \frac{(1+\log t)Q_{0,a_1}(t)}{t^2\log^2 t}dt\right).
\end{displaymath}
By Lemma \ref{Q}, $Q_{0,a_1}(t)\le Mt^{0.8}$ for all $t>0$, where $M=0.00754$. We therefore have
\begin{equation}\label{a2}
\begin{aligned}
\mathop{\sum_{p>y_k}}_{p\in \mathcal{Q}_{0,a_1}}\frac{1}{p\ell_2(p)} &\le M\log 2\int_{y_k}^\infty \frac{1+\log t}{t^{2-2a_1}\log^2 t}dt\\
&= M\log 2\left(-2a_1\text{Ei}((2a_1-1)\log y_k)+\frac{y_k^{2a_1-1}}{\log y_k}\right),
\end{aligned}
\end{equation}
where $$\text{Ei}(x) = \int_{-\infty}^x \frac{e^t}{t} dt$$ is the exponential integral function.  An analogous bound holds with $Y_0$ in place of $y_k$.  Similarly, for primes $p > z_k$, we may apply Proposition \ref{prop2}.  Let
\begin{displaymath}
B_3(z) := M\log 2\left(-2a_1\text{Ei}((2a_1-1)\log z)+\frac{z^{2a_1-1}}{\log z}\right).
\end{displaymath}

We have
\begin{displaymath}
\begin{aligned}
    \mathop{\sum_{N\in \mathcal{A}_3}}_{N>x_0}\frac{1}{N}&\le \sum_{39\le k\le 130}c_k B_3(Y_0) + \sum_{k\ge 131} c_k B_3(y_k)+ \sum_{k\ge 36} 2 B_3(z_k).
\end{aligned}
\end{displaymath}  

We next consider $\mathcal{A}_4$.  By Lemma \ref{Q} we have
$Q_{a_1,a_2}(x)\le M x^{2a_2}$ for all $x\ge 337$, where $M=0.00754$.  Since $p\in \mathcal{Q}_{a_1,a_2}$, we also have $\ell_2(p)>p^{a_1}$.  Therefore,

\begin{displaymath}
\mathop{\sum_{y_k < p\le z_k}}_{p\in \mathcal{Q}_{a_1,a_2}}\frac{1}{p\ell_2(p)}\le \mathop{\sum_{p>y_k}}_{p\in \mathcal{Q}_{a_1,a_2}}\frac{1}{p^{1+a_1}}.
\end{displaymath}
By partial summation (Lemma \ref{abel}), the rightmost sum above is equal to
\begin{equation}\label{a3}
\begin{aligned}
-\frac{{Q}_{a_1,a_2}(y_k)}{y_k^{1+a_1}}+(1+a_1)\int_{y_k}^\infty \frac{{Q}_{a_1,a_2}(t)}{t^{2+a_1}}dt&\le (1+a_1)M \int_{y_k}^\infty \frac{dt}{t^{2+a_1-2a_2}}\\
&=\frac{(1+a_1)M}{(1+a_1-2a_2)y_k^{1+a_1-2a_2}}.
\end{aligned}
\end{equation}
An analogous bound holds with $Y_0$ in place of $y_k$, and with $z_k$ in place of $y_k$.  Let $B_{4}(z):=(1+a_1)M/((1+a_1-2a_2)z^{1+a_1-2a_2})$.  By Propositions \ref{prop2} and \ref{improvement}, we have
\begin{displaymath}
\begin{aligned}
\mathop{\sum_{N\in \mathcal{A}_4}}_{N>x_0} \frac{1}{N} &\le \sum_{39\le k\le 130}d_kB_4(Y_0) + \sum_{k\ge 131}d_kB_4(y_k) + \sum_{k\ge 36} 2 B_4(z_k).
\end{aligned}
\end{displaymath}

For $\mathcal{A}_5$,  we have by partial summation (Lemma \ref{abel}) with $f(t)=1/t^{1+a_2}$ that
\begin{equation}\label{a4}
\sum_{y_k < p \le z_k}\frac{1}{p\ell_2(p)} \le \sum_{p>y_k}\frac{1}{p^{1+a_2}} = -\frac{\pi(y_k)}{y_k^{1+a_2}}+(1+a_2)\int_{y_k}^\infty \frac{\pi(t)}{t^{2+a_2}}dt.
\end{equation}
By Lemma \ref{primepi}, this is bounded above by

\begin{equation}\label{a4expression}
\begin{aligned}
&-\frac{1}{y_k^{a_2}\log y_k}-\frac{1}{y_k^{a_2}\log^2 y_k}+(1+a_2)\int_{y_k}^\infty \left(\frac{1}{\log t}+\frac{1.2762}{\log^2 t}\right)\frac{dt}{t^{1+a_2}}\\
\end{aligned}
\end{equation}

and the integral evaluates to 
\begin{displaymath}
-\text{Ei}(-a_2\log y_k)+1.2762\left(a_2\text{Ei}(-a_2\log y_k)+\frac{1}{y_k^{a_2}\log y_k}\right).
\end{displaymath}
As before, an analogous bound holds with $Y_0$ in place of $y_k$, and with $z_k$ in place of $y_k$.  Let
\begin{displaymath}
    B_{5}(z):= -\frac{1+1/\log z}{z^{a_2}\log z}+(1+a_2)\int_{z}^\infty \left(\frac{1}{\log t}+\frac{1.2762}{\log^2 t}\right)\frac{dt}{t^{1+a_2}}.
\end{displaymath}
Proceeding as we did with $\mathcal{A}_4$, we use Propositions \ref{prop2} and \ref{improvement} to bound the contribution to the reciprocal sum as

\begin{displaymath}
\begin{aligned}
\mathop{\sum_{N\in \mathcal{A}_5}}_{N>x_0} \frac{1}{N} &\le \sum_{39\le k\le 130}0.25B_5(Y_0) + \sum_{k\ge 131}0.25B_5(y_k) + \sum_{k\ge 36}2B_5(z_k).
\end{aligned}
\end{displaymath}

Summing the contributions from the small range along with the five cases in the large range $k\ge 36$, we obtain the following upper bound:

\begin{displaymath}
\begin{aligned}
\sum_{N\in \mathcal{E}}\frac{1}{N}
    &\le 0.000012 + 0.003138 + 0.000070 \\
    &\quad + \sum_{39\le k\le 130}(c_kB_3(Y_0)+d_kB_4(Y_0)+0.25B_5(Y_0))\\
    &\quad + \sum_{k\ge 131}(c_kB_3(y_k)+d_kB_4(y_k)+0.25B_5(y_k))\\
    &\quad + \sum_{k\ge 36}(2B_3(z_k)+2B_4(z_k)+2B_5(z_k))\\
    &< 0.000012 + 0.003138 + 0.000070 + 0.000925 + 0.000535 + 0.001185\\
    &< 0.0059.
\end{aligned}
\end{displaymath}



This completes the proof of Theorem \ref{mainthm}.

\section{Acknowledgments}
We thank Linh Hoang for assistance and feedback, as well as Mark Royer for computing the sum in Eq.~\eqref{smallrange} to high precision.  We also thank the anonymous referee for helpful feedback. 

\begin{thebibliography}{10}

\bibitem{apostol2013}
Tom~M. Apostol, {\em Introduction to Analytic Number Theory}, Springer Science
  \& Business Media, 2013.

\bibitem{bayless2017}
J.~Bayless and P.~Kinlaw, Explicit bounds for the sum of reciprocals of
  pseudoprimes and {C}armichael numbers, {\em J. Integer Sequences} {\bf 20}
  (2017), \href{https://cs.uwaterloo.ca/journals/JIS/VOL20/Bayless/bayless3.html}{Article 17.6.4}.

\bibitem{beeger1951}
N.~G. W.~H. Beeger, On even numbers $m$ dividing $2^m - 2$, {\em Amer. Math.
  Monthly} {\bf 58}  (1951), 553--555.

\bibitem{dusart2016}
P.~Dusart, Explicit estimates of some functions over primes,
{\em Ramanujan J.} {\bf 45} (2018), 227--251.

\bibitem{oeis}
N.~J. A.~Sloane et~al., The {O}n-{L}ine {E}ncyclopedia of {I}nteger
  {S}equences, \url{https://oeis.org}, 2026.

\bibitem{pari2022}
The~PARI Group, Pari/gp version 2.13.3, \url{http://pari.math.u-bordeaux.fr/},
  2022.

\bibitem{kinlaw2023}
P.~Kinlaw, The reciprocal sums of pseudoprimes and {C}armichael numbers, {\em
  Math. Comp.}, to appear.

\bibitem{dekoninck2023}
Jean-Marie~De Koninck and Florian Luca, {\em Analytic Number Theory: Exploring
  the Anatomy of Integers}, Vol. 134 of {\em Graduate Studies in Mathematics},
  Amer. Math. Society, 2023.

\bibitem{nguyen2019}
H.~Nguyen and C.~Pomerance, The reciprocal sum of the amicable numbers, {\em
  Math. Comp.} {\bf 88} (2019), 1503--1526.

\bibitem{pomerance2021}
C.~Pomerance and S.~Wagstaff, Some thoughts on pseudoprimes, {\em Bull. Cl.
  Sci. Math. Nat. Sci. Math.} {\bf 46} (2021), 53--72.

\end{thebibliography}
\bigskip
\hrule
\bigskip

\noindent 2020 {\it Mathematics Subject Classification}:
Primary 11N25; Secondary 11N37.

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

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequence
\seqnum{A006935}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received October 24 2024;
revised versions received October 25 2024; November 4 2025; December 19 2025. 
Published in {\it Journal of Integer Sequences}, January 26 2026.

\bigskip
\hrule
\bigskip

\noindent
Return to \href{https://cs.uwaterloo.ca/journals/JIS/}{Journal of Integer Sequences home page}.


\end{document}

                                                                                


