1 Background

Consider a “multiplicative” random walk on the set $\mathbb{Z}/n\mathbb{Z}$ of residues modulo $n$ . In each step of this walk a residue modulo $n$ is chosen, uniformly at random, and the current state is multiplied by it. Because $\mathbb{Z}/n\mathbb{Z}$ does not form a group, but rather a monoid under multiplication, this is not a transitive walk. In fact, it is an absorbing random walk with a single absorbing state, $0\hspace{0.6em}({\rm mod}\hspace{0.2em}n)$ . So if the walk proceeds long enough then, with probability one, the walk will eventually arrive (and stay) at the residue zero.

For example, when $n=6$ this random walk is equivalent to a random walk on the directed graph depicted in Figure 1. In this walk each of the edges leaving a vertex are equally likely to be chosen. Note that it is possible to step from the residues one and five (the units modulo six) to any of the residues modulo six, but this is not true for the other residues, and that the only edge leaving zero is a loop.

In this paper, we are interested in the expected time to absorption, the number of steps it takes on average to reach $0\hspace{0.6em}({\rm mod}\hspace{0.2em}n)$ , if the initial state of the walk is $1\hspace{0.6em}({\rm mod}\hspace{0.2em}n)$ , or equivalently any unit modulo $n$ . For any positive integer $n$ we denote by $a(n)$ the expected time to absorption in the monoid $\mathbb{Z}/n\mathbb{Z}$ , and study the behavior of this arithmetic function. Analyzing the walk depicted for $n=6$ above, one finds, for example, that $a(6)=3.5$ .

The problem of studying random walks on groups has been studied extensively, see for example [Reference Aldous1, Reference Hildebrand9]. Many common random walks can in fact be viewed as walks on groups, for example the walk on the infinite line ( $\mathbb{Z}$ ) or on a cycle ( $\mathbb{Z}/n\mathbb{Z}$ under addition). More recently, several authors have considered random walks on monoids [Reference Gretete8, Reference Mairesse14]. Note that, in the literature, a random walk on a group or monoid is composed of steps which are taken from some generating set of the group (or monoid). In our case we take the generating set to be the entire monoid $\mathbb{Z}/n\mathbb{Z}$ . In the case of a random walk on a group, one would not generally take the entire group as a generating set as it would then be possible to transition between any two states in a single step.

Figure 1

The directed graph depicting the random walk on the residues modulo six.

We could alternatively view our problem as a random walk on the positive integers, $\mathbb{N}$ , in which we repeatedly multiply the current state by an integer chosen uniformly at random from the range $[1,n]$ (or $[1,mn]$ where $m\geqslant 1$ is an integer). Our function $a(n)$ is then the expected number of multiplications before the product is divisible by $n$ .

The behavior of this function turns out to depend sensitively on the largest prime divisors of $n$ . If $n=p_{1}^{\unicode[STIX]{x1D6FC}_{1}}p_{2}^{\unicode[STIX]{x1D6FC}_{2}}\cdots p_{k}^{\unicode[STIX]{x1D6FC}_{k}}$ with $p_{1}>p_{2}>\cdots >p_{k}$ , we denote by

$$\begin{eqnarray}P_{i}(n)=\left\{\begin{array}{@{}ll@{}}p_{i}\quad & 1\leqslant i\leqslant k,\\ 1\quad & i>k,\end{array}\right.\end{eqnarray}$$

and by $B(n)$ the sum of the prime divisors of $n$ taken with multiplicity,

$$\begin{eqnarray}B(n)=\mathop{\sum }_{i=1}^{k}\unicode[STIX]{x1D6FC}_{i}p_{i}.\end{eqnarray}$$

As we will see in §4 our function $a(n)$ is bounded between the functions $P_{1}(n)$ and $B(n)$ . The behavior of these functions (along with a handful of similarly defined functions) has been studied extensively (see [Reference Alladi and Erdős2–Reference Erdős, Ivić and Pomerance6, Reference Kemeny12, Reference Knuth and Trabb Pardo13, Reference Naslund16]), much of it emphasizing how remarkably similar these two functions are. Given that our function is closely related to these two functions, we analyze it similarly.

First, however, in §§2 and 3 we obtain several expressions for $a(n)$ . Theorem 2.2 shows how to calculate $a(n)$ for any integer $n$ , namely

$$\begin{eqnarray}\displaystyle a(n)=\frac{1}{n-\unicode[STIX]{x1D711}(n)}\biggl(n+\mathop{\sum }_{\substack{ d|n \\ d\neq n}}\unicode[STIX]{x1D711}(d)a(d)\biggr). & & \displaystyle \nonumber\end{eqnarray}$$

Unfortunately, this expression is recursive, but we are able to obtain expressions that are not recursive in special cases. For prime powers (Theorem 2.1) we show that $a(p^{k})=k(p-1)+1$ , and for squarefree values of $n$ we show (Theorem 3.1) that

$$\begin{eqnarray}a(n)=\mathop{\sum }_{\substack{ d|n \\ d\neq 1}}(-1)^{\unicode[STIX]{x1D714}(d)+1}\frac{d}{d-\unicode[STIX]{x1D711}(d)}.\end{eqnarray}$$

In §4 we begin our study of the asymptotic behavior of this function by obtaining the average order of $a(n)$ , (Corollary 4.4)

$$\begin{eqnarray}\mathop{\sum }_{n<x}a(n)\sim \frac{\unicode[STIX]{x1D70B}^{2}x^{2}}{12\log x}\end{eqnarray}$$

as $x\rightarrow \infty$ , as a corollary of a result of Alladi and Erdős. This average order is asymptotically the same as both the functions $P_{1}(n)$ and $B(n)$ .

Recall that for functions $f(x),g(x)>0$ the notation $f(x)\sim g(x)$ is used to mean $\lim _{x\rightarrow \infty }(f(x)/g(x))=1$ . We will also say $f(x)=O(g(x))$ or $f(x)\ll g(x)$ to mean $f(x)<Cg(x)$ for some absolute constant $C$ and we write $f(x)=o(g(x))$ as $x\rightarrow \infty$ if $\lim _{x\rightarrow \infty }(f(x)/g(x))=0$ .

Not only does $a(n)$ have the same average order as $P_{1}(n)$ , but in fact we show in Theorem 5.1 that on a set of integers with density about $0.623$ the function $P_{1}(n)$ is a very good approximation to $a(n)$ in the sense that $a(n)=P_{1}(n)+o(1)$ as $n$ goes to infinity over the integers in this set. Surprisingly, however, we find that (with the exception of a set of measure zero) on the compliment of this set, where the approximation above is not true, we have that the difference between $a(n)$ and $P_{1}(n)$ tends to infinity.

As mentioned above, $a(n)$ is bounded between $P_{1}(n)$ and $B(n)$ . In addition to having the same average order asymptotically, Alladi and Erdős show (see Theorem 4.2) that

$$\begin{eqnarray}\mathop{\sum }_{n<x}(B(n)-P_{1}(n))\sim \mathop{\sum }_{n<x}P_{2}(n).\end{eqnarray}$$

In other words, the sum of the prime factors of $n$ , omitting the largest prime factor is completely dominated by the second largest prime factor. In light of this result, we consider the behavior of $a(n)-P_{1}(n)$ . In Theorem 6.1 we show that there exist constants $D_{\ell }$ (whose values are given explicitly in the proof) such that for any fixed integer $N\geqslant 1$

$$\begin{eqnarray}\mathop{\sum }_{n\leqslant x}a(n)-P_{1}(n)=\frac{x^{3/2}}{\log ^{2}x}\mathop{\sum }_{\ell =0}^{N-1}\frac{D_{\ell }}{\log ^{\ell }x}+O_{N}\biggl(\frac{x^{3/2}}{\log ^{N+2}x}\biggr).\end{eqnarray}$$

As in Corollary 6.2 we obtain that

$$\begin{eqnarray}\mathop{\sum }_{n<x}(a(n)-P_{1}(n))\sim \biggl(1-\frac{\unicode[STIX]{x1D70B}}{4}\biggr)\mathop{\sum }_{n<x}P_{2}(n),\end{eqnarray}$$

which we can interpret as saying that, in an average sense, the value of $a(n)$ is approximately the sum of the largest prime factor of $n$ plus an extra contribution of a factor of $(1-\unicode[STIX]{x1D70B}/4)$ times its second largest prime factor.

Figure 2

The directed graph depicting the random walk when $n=p^{k}$ is a prime power. Note that each node in this graph represents all residues that have the same greatest common divisor (gcd) with $n$ rather than individual residues, and that not all edges have the same weight.

Throughout the paper we will use $X$ and $Y$ to denote random variables, $\mathbb{E}[X]$ to denote the expected value of $X$ , and $\mathbb{P}$ to denote the probability of an event occurring.

2 Computing the expected time to reach zero

It does not appear to be possible to write down a general, closed formula for $a(n)$ . We are, however, able to give a recursive formula and estimates that are generally quite accurate. The value of $a(n)$ is rarely an integer, and may never be unless $n$ is a prime power. We begin with a few cases that are easily dealt with.

In the case when $n=p$ is prime, every element of $\mathbb{Z}/p\mathbb{Z}$ except $0\hspace{0.6em}({\rm mod}\hspace{0.2em}p)$ is a unit. As a result there is only one way of reaching zero, namely by randomly choosing the residue zero as a multiple when stepping. This is then a Bernoulli trial with probability of success $1/p$ , and thus the expected time to walk to zero is

$$\begin{eqnarray}a(p)=p.\end{eqnarray}$$

The case $n=p^{k}$ , when $n$ is a prime power, is somewhat more enlightening. As in the prime case, the likelihood, at each step, of randomly selecting a unit (a residue coprime to $p$ ) is $(p-1)/p$ . Since the only way to progress toward the absorbing state is to select a non-unit, we expect to wait for $p$ iterations between “meaningful” steps that bring us closer to zero. Unlike the prime case, however, it is unlikely (though possible) that the first step by a non-unit will take us directly to zero. It is much more likely that we only pick up one or a couple of the necessary copies of $p$ . In essence, we are taking a walk on the graph in Figure 2, in which each loop is weighted with probability $(p-1)/p$ , each edge from $p^{i}$ to $p^{j}$ , $0\leqslant i<j<k$ is weighted with probability $(p-1)/p^{i-j+1}$ and each edge from $p^{i}$ to $p^{k}$ by $1/p^{k-i}$ .

Theorem 2.1. When $n=p^{k}$ is a power of a prime the expected length of a multiplicative random walk on $\mathbb{Z}/p^{k}\mathbb{Z}$ is

(1) $$\begin{eqnarray}a(p^{k})=k(p-1)+1.\end{eqnarray}$$

Proof. When $k=1$ the result is the prime case discussed above. We now proceed by induction, and suppose that equation (1) holds for all exponents less than $k$ . By linearity of expectation we can break the expected time up as

$$\begin{eqnarray}a(p^{k})=\mathbb{E}[\text{time until first step by non-unit}]+\mathbb{E}[\text{time to step from there to zero}].\end{eqnarray}$$

We know, as above, that the expected number of steps until our first non-unit is $p$ , so we need only consider the second. Once we have taken our first step by a non-unit, say to a residue whose greatest common divisor (gcd) with $p^{k}$ is $p^{i}$ , we see that we need to pick up an additional $k-i$ copies of $p$ . Doing so amounts to a walk on $\mathbb{Z}/p^{k-i}\mathbb{Z}$ , which takes time $a(p^{k-i})$ .

Since the probability that our first non-unit step contains exactly $i$ copies of $p$ is $(p-1)/p^{i}$ for $i<k$ and $1/p^{k}$ when $i=k$ , we get that

$$\begin{eqnarray}\displaystyle a(p^{k}) & = & \displaystyle p+\mathop{\sum }_{i=1}^{k-1}\frac{p-1}{p^{i}}a(p^{k-i})+\frac{a(p^{0})}{p^{k}}\nonumber\\ \displaystyle & = & \displaystyle p+\mathop{\sum }_{i=1}^{k-1}\frac{p-1}{p^{i}}((k-i)(p-1)+1).\nonumber\end{eqnarray}$$

Here we have used the induction hypothesis and that $a(1)=0$ . Rewriting this sum, we get that

$$\begin{eqnarray}\displaystyle a(p^{k}) & = & \displaystyle p+\frac{p-1}{p^{k}}\mathop{\sum }_{i=1}^{k-1}p^{k-i}((k-i)(p-1)+1)\nonumber\\ \displaystyle & = & \displaystyle p+\frac{p-1}{p^{k}}\mathop{\sum }_{i=1}^{k-1}p^{i}(i(p-1)+1)\nonumber\\ \displaystyle & = & \displaystyle p+\frac{(p-1)^{2}}{p^{k}}\mathop{\sum }_{i=1}^{k-1}ip^{i}+\frac{p-1}{p^{k}}\mathop{\sum }_{i=1}^{k-1}p^{i}\nonumber\\ \displaystyle & = & \displaystyle p+\frac{(p-1)^{2}}{p^{k}}\biggl(\frac{p-p^{k}}{(1-p)^{2}}-\frac{(k-1)p^{k}}{1-p}\biggr)+\frac{p-1}{p^{k}}\biggl(\frac{p-p^{k}}{1-p}\biggr)\nonumber\\ \displaystyle & = & \displaystyle p+\frac{p-p^{k}}{p^{k}}-(k-1)(1-p)-\frac{p-p^{k}}{p^{k}}\nonumber\\ \displaystyle & = & \displaystyle k(p-1)+1.\nonumber\end{eqnarray}$$

This completes the inductive step and the proof.◻

The residues modulo an arbitrary $n$ can be decomposed into the sets

$$\begin{eqnarray}R_{d}=\{r\in \mathbb{Z}/n\mathbb{Z}:(r,n)=d\}=d\cdot \biggl(\mathbb{Z}/\frac{n}{d}\mathbb{Z}\biggr)^{\times },\end{eqnarray}$$

for each of the divisors $d$ of $n$ . Each such set has size $\unicode[STIX]{x1D711}(n/d)$ . Our random walk on the residues modulo $n$ can also be interpreted as a walk on the classes $R_{d}$ , starting in $R_{1}=(\mathbb{Z}/n\mathbb{Z})^{\times }$ .

The key observation we made at the beginning of this proof to create a recursive formula for $a(p^{k})$ works just as well for arbitrary composite $n$ , although we are not able to solve the recurrence. For arbitrary $n$ , the probability of randomly choosing a non-unit is $(n-\unicode[STIX]{x1D711}(n))/n$ , where $\unicode[STIX]{x1D711}(n)$ is the Euler totient function, hence we expect it will take $n/(n-\unicode[STIX]{x1D711}(n))$ steps before our first such choice. Having done so, the probability that our chosen residue has gcd $d$ with $n$ is $|R_{d}|/(n-|R_{1}|)=\unicode[STIX]{x1D711}(n/d)/(n-\unicode[STIX]{x1D711}(n))$ and thus we have the following recursive formula, which allows us to compute $a(n)$ for all $n$ .

Theorem 2.2. For all $n>1$ the expected length of a random walk on $\mathbb{Z}/n\mathbb{Z}$ is

$$\begin{eqnarray}\displaystyle a(n) & = & \displaystyle \frac{n}{n-\unicode[STIX]{x1D711}(n)}+\mathop{\sum }_{\substack{ d|n \\ d\neq 1}}\frac{\unicode[STIX]{x1D711}(n/d)a(n/d)}{n-\unicode[STIX]{x1D711}(n)}\nonumber\\ \displaystyle & = & \displaystyle \frac{1}{n-\unicode[STIX]{x1D711}(n)}\biggl(n+\mathop{\sum }_{\substack{ d|n \\ d\neq n}}\unicode[STIX]{x1D711}(d)a(d)\biggr).\nonumber\end{eqnarray}$$

3 Squarefree integers

In the case that the integer $n$ is squarefree we can solve the recursion in Theorem 2.2. It is convenient to use different methods, however, which will be useful later. In the squarefree case, reaching the residue $0\hspace{0.6em}({\rm mod}\hspace{0.2em}n)$ amounts to having randomly chosen a residue divisible by each prime dividing $n$ at least once in our walk. For any prime $p$ dividing $n$ , we can let $X_{p}$ be a random variable which counts the number of steps taken before randomly selecting a residue divisible by $p$ . Then all of the random variables $X_{p}$ are independent, geometric random variables with $\mathbb{E}[X_{p}]=p$ and

$$\begin{eqnarray}a(n)=\mathbb{E}\Big[\max _{p|n}\{X_{p}\}\Big].\end{eqnarray}$$

While the expected value of a maximum of random variables is not, in general, well behaved, it is straightforward to obtain a formula in the case of independent, geometric random variables. Note that this is possible despite the fact that our variables are not identically distributed. (Jeske and Blessinger observe [Reference Jeske and Blessinger11] that this formula is surprisingly rare in the literature.)

Theorem 3.1. For $n\geqslant 2$ squarefree

$$\begin{eqnarray}a(n)=\mathop{\sum }_{\substack{ d|n \\ d\neq 1}}(-1)^{\unicode[STIX]{x1D714}(d)+1}\frac{d}{d-\unicode[STIX]{x1D711}(d)}.\end{eqnarray}$$

Proof. Let $X=\max _{p|n}\{X_{p}\}$ . Then

$$\begin{eqnarray}\displaystyle a(n)=\mathbb{E}\Big[\max _{p|n}\{X_{p}\}\Big] & = & \displaystyle \mathop{\sum }_{i=0}^{\infty }\mathbb{P}[X>i]=\mathop{\sum }_{i=0}^{\infty }(1-\mathbb{P}[X\leqslant i])\nonumber\\ \displaystyle & = & \displaystyle \mathop{\sum }_{i=0}^{\infty }\biggl(1-\mathop{\prod }_{p|n}\mathbb{P}[X_{p}\leqslant i]\biggr)\nonumber\\ \displaystyle & = & \displaystyle \mathop{\sum }_{i=0}^{\infty }\biggl(1-\mathop{\prod }_{p|n}\biggl(1-\biggl(\frac{p-1}{p}\biggr)^{i}\biggr)\biggr)\nonumber\\ \displaystyle & = & \displaystyle \mathop{\sum }_{i=0}^{\infty }\mathop{\sum }_{\substack{ d|n \\ d\neq 1}}(-1)^{\unicode[STIX]{x1D714}(d)+1}\frac{\unicode[STIX]{x1D711}(d)^{i}}{d^{i}}\nonumber\\ \displaystyle & = & \displaystyle \mathop{\sum }_{\substack{ d|n \\ d\neq 1}}\frac{(-1)^{\unicode[STIX]{x1D714}(d)+1}}{1-\unicode[STIX]{x1D711}(d)/d}=\mathop{\sum }_{\substack{ d|n \\ d\neq 1}}(-1)^{\unicode[STIX]{x1D714}(d)+1}\frac{d}{d-\unicode[STIX]{x1D711}(d)}.\square\nonumber\end{eqnarray}$$

Note that for $n=p$ this reduces to the equation above, and for $n=pq$ , (where $p\neq q$ ) gives

(2) $$\begin{eqnarray}a(pq)=p+q-\frac{pq}{p+q-1}=p+\frac{q(q-1)}{p+q-1}.\end{eqnarray}$$

This can also be obtained from Theorem 2.2.

4 The average order of the expected time

Because it is necessary to have randomly chosen at least one residue divisible by each prime dividing $n$ and, in particular, we expect the largest prime divisor, $P_{1}(n)$ , to require $P_{1}(n)$ steps, we know that this function serves as a lower bound for $a(n)$ . We can also see relatively easily that the function $B(n)$ , the sum of all the prime divisors of $n$ with multiplicity, gives an upper bound for $a(n)$ .

Lemma 4.1. For any integer $n$ , the function $a(n)$ satisfies the inequality

$$\begin{eqnarray}P_{1}(n)\leqslant a(n)\leqslant B(n)\end{eqnarray}$$

with equality occurring in each case if and only if $n$ is prime.

Now, these functions, $P_{1}(n)$ and $B(n)$ , despite arising as relatively crude lower and upper bounds for $a(n)$ are not so different. As a matter of fact, Alladi and Erdős studied both of them [Reference Alladi and Erdős2], and showed that both have the same average order.

Theorem 4.2 (Alladi and Erdős [Reference Alladi and Erdős2]).

As $x\rightarrow \infty$ ,

$$\begin{eqnarray}\mathop{\sum }_{n<x}P_{1}(n)\sim \mathop{\sum }_{n<x}B(n)\sim \frac{\unicode[STIX]{x1D70B}^{2}x^{2}}{12\log x},\end{eqnarray}$$

and, furthermore, the difference between these two sums is dominated by the contribution of the second largest prime factor,

$$\begin{eqnarray}\biggl(\mathop{\sum }_{n<x}B(n)-\mathop{\sum }_{n<x}P_{1}(n)\biggr)=\mathop{\sum }_{n<x}(B(n)-P_{1}(n))=\mathop{\sum }_{n<x}P_{2}(n)+O\biggl(\frac{x^{4/3}}{\log ^{3}x}\biggr)\end{eqnarray}$$

and that

$$\begin{eqnarray}\mathop{\sum }_{n<x}P_{2}(n)\sim C\frac{x^{3/2}}{(\log x)^{2}}\end{eqnarray}$$

for some positive constant $C$ .

Ivić [Reference Ivić10] noted that the constant $C$ in their result is equal to $8\unicode[STIX]{x1D701}(3/2)/3$ , attributing the result to Balasubramanian. He also showed that the sum of $P_{2}(n)$ admits an asymptotic expansion.

Theorem 4.3 (Ivić [Reference Ivić10]).

There exist constants $A_{l}$ such that for any integer $N\geqslant 1$

$$\begin{eqnarray}\mathop{\sum }_{n\leqslant x}P_{2}(n)=\frac{x^{3/2}}{\log ^{2}x}\mathop{\sum }_{l=0}^{N-1}\frac{A_{l}}{\log ^{l}x}+O_{N}\biggl(\frac{x^{3/2}}{\log ^{N+2}x}\biggr).\end{eqnarray}$$

We will return to Theorem 4.3 in §6. For now, we note that we can easily obtain the average order of $a(n)$ from Theorem 4.2 and Lemma 4.1.

Corollary 4.4. As $x\rightarrow \infty$ ,

$$\begin{eqnarray}\mathop{\sum }_{n<x}a(n)\sim \frac{\unicode[STIX]{x1D70B}^{2}x^{2}}{12\log x}.\end{eqnarray}$$

5 The typical behavior of $a(n)$

In addition to having the same average order, Erdős and Pomerance [Reference Erdős and Pomerance7] show that, on a set of asymptotic density one, $P_{1}(n)\sim B(n)$ . So, in a sense these bounds answer the question of how large $a(n)$ is. But which function is a better estimate of $a(n)$ ? For the majority of integers $n$ , $P_{1}(n)$ turns out to be a remarkably good approximation for $a(n)$ , and in fact the difference between these two functions tends to zero on this set. However, for almost all of the remaining integers, a set which still has positive density, the difference $a(n)-P_{1}(n)$ tends to infinity.

Proof. The set of integers satisfying the inequality $P_{2}(n)<P_{1}(n)^{1/2}$ was studied by Wheeler [Reference Wheeler17], who showed that the density exists and is equal to the constant above. In what follows we disregard those $n$ where any of the following hold:

1. (1) $P_{1}(n)<\log n$ ;

2. (2) $P_{1}(n)^{1/2}/\text{log}\,n<P_{2}(n)<P_{1}(n)^{1/2}\log n$ ;

3. (3) $n$ is divisible by a composite prime power greater than $P_{2}(n)$ .

However, each of these conditions occur only on a set of integers with density zero. (The fact that these sets have density zero follows from standard smooth number estimates (1), from [Reference Wheeler17, Theorem 9] (2), and from the fact that $\sum _{p>x}(1/p^{2})$ tends to zero as $x\rightarrow \infty$ (3), respectively.)

Let $p=P_{1}(n)$ . By linearity of the expectation, we can write

$$\begin{eqnarray}a(n)=\mathbb{E}[X_{p}]+\mathbb{E}[Y],\end{eqnarray}$$

where $X_{p}$ is the random variable counting the number of steps before we randomly choose a residue divisible by $p$ , and $Y$ is the time required to pick up any remaining factors after choosing a residue divisible by $p$ . Now $\mathbb{E}[X_{p}]=p$ , so it suffices to study $\mathbb{E}[Y]$ .

Let $q_{1},q_{2},\ldots$ denote the distinct, maximal prime powers dividing $n/p$ and let the random variables $Y_{q_{i}}$ denote the number of steps in the walk after acquiring a factor of $p$ and before acquiring a factor of $q_{i}$ . So

$$\begin{eqnarray}Y=\max _{i}\{Y_{q_{i}}\}\leqslant \mathop{\sum }_{i}Y_{q_{i}}.\end{eqnarray}$$

In what follows we will assume that $q_{i}$ is prime, as the prime power case will only be smaller. Owing to the memoryless property of the geometric distribution, we have that

$$\begin{eqnarray}\displaystyle \mathbb{E}[Y_{q_{i}}] & = & \displaystyle \mathbb{E}[X_{q_{i}}]P(X_{p}<X_{q_{i}})\nonumber\\ \displaystyle & = & \displaystyle q_{i}\mathop{\sum }_{k=1}^{\infty }P(X_{p}=k)P(X_{q_{i}}>k)\nonumber\\ \displaystyle & = & \displaystyle q_{i}\mathop{\sum }_{k=1}^{\infty }\biggl(1-\frac{1}{p}\biggr)^{k-1}\frac{1}{p}\biggl(1-\frac{1}{q_{i}}\biggr)^{k}\nonumber\\ \displaystyle & = & \displaystyle \frac{q_{i}}{p}\biggl(1-\frac{1}{q_{i}}\biggr)\mathop{\sum }_{k=0}^{\infty }\biggl(1-\frac{1}{p}\biggr)^{k}\biggl(1-\frac{1}{q_{i}}\biggr)^{k}\nonumber\\ \displaystyle & = & \displaystyle \frac{q_{i}-1}{p}\biggl(\frac{1}{1-(1-1/p)(1-1/q_{i})}\biggr)\nonumber\\ \displaystyle & = & \displaystyle \frac{q_{i}-1}{1+p/q_{i}-1/q_{i}}<\frac{q_{i}^{2}}{p}.\nonumber\end{eqnarray}$$

Now, in the first case, where $P_{2}(n)<P_{1}(n)^{1/2}$ , we have that $q_{i}\leqslant P_{2}(n)\leqslant \sqrt{p}/\text{log}\,n$ (since we disregarded the set of integers whose second largest prime factor was smaller than $\sqrt{p}$ by less than a factor of $\log n$ ) and so the expression above is less than $(\log n)^{-2}$ . Since $n$ has at most $\log n$ distinct prime factors, we have that

$$\begin{eqnarray}\displaystyle \mathbb{E}[Y]\leqslant \mathop{\sum }_{i}\mathbb{E}[Y_{q_{i}}]<\frac{\log n}{(\log n)^{2}}<\frac{1}{\log n}=o(1) & & \displaystyle \nonumber\end{eqnarray}$$

as $n\rightarrow \infty$ .

In the second case where $P_{2}(n)^{2}>P_{1}(n)$ , we can assume that $q=P_{2}(n)>p^{1/2}\log n$ , as we also disregarded above the set of integers where this was not the case, and so

$$\begin{eqnarray}\displaystyle \mathbb{E}[Y_{q}] & = & \displaystyle \frac{q-1}{1+p/q-1/q}>\frac{q-1}{1+p/q}\nonumber\\ \displaystyle & \gg & \displaystyle \frac{q}{1+p/q}\gg \frac{q}{p/q}=\frac{q^{2}}{p}>\log ^{2}n.\nonumber\end{eqnarray}$$

Since this goes to infinity as $n$ does, we have that $a(n)-P_{1}(n)\geqslant \mathbb{E}[Y_{q}]$ does as well.◻

The same method of proof used here can also be extended to show, for example, that (but for a set of density zero) on the integers where $P_{3}(n)^{3}<P_{1}(n)\cdot P_{2}(n)$ we have $a(n)=P_{1}(n)+P_{2}(n)^{2}/(P_{1}(n)+P_{2}(n))+o(1)$ as $n\rightarrow \infty$ . Note that the set of integers on which this condition holds both contains and has density strictly greater than the set where $P_{2}(n)^{2}<P_{1}(n)$ .

It similarly follows that for each fixed $k$ there exists a set of integers on which the value of $a(n)$ is approximated, up to an error term that is $o(1)$ , by a function involving only by the largest $k$ prime factors of $n$ , where the density of these sets approaches one as $k$ goes to infinity. However, the expression for $a(n)$ in terms of these prime factors becomes increasingly complicated.

6 The average time spent waiting after the largest prime factor

We know that $P_{1}(n)\leqslant a(n)\leqslant B(n)$ , with equality holding in each case if and only if $n$ is prime. In light of Theorems 4.2 and 4.3 it makes sense to similarly consider the difference $a(n)-P_{1}(n)$ , which also corresponds, by linearity of expectation, to the expected number of steps spent waiting after the random walk has picked up a factor of the largest prime divisor of $n$ .

Theorem 6.1. There exist constants $D_{\ell }$ such that, for any fixed integer $N\geqslant 1$ ,

$$\begin{eqnarray}\mathop{\sum }_{n\leqslant x}(a(n)-P_{1}(n))=\frac{x^{3/2}}{\log ^{2}x}\mathop{\sum }_{\ell =0}^{N-1}\frac{D_{\ell }}{\log ^{\ell }x}+O_{N}\biggl(\frac{x^{3/2}}{\log ^{N+2}x}\biggr).\end{eqnarray}$$

In particular, $D_{0}=(8\unicode[STIX]{x1D701}(3/2)/3)(1-\unicode[STIX]{x1D70B}/4)$ , and an expression that can be used to compute $D_{\ell }$ for any value of $\ell$ is given in the proof (12) below.

Comparing this with Theorem 4.2 and the constant found by Balasubramanian (which can also be obtained by methods similar to the proof of Theorem 6.1) we can get a result about how $a(n)$ depends, in an average sense, on its largest two prime factors.

Corollary 6.2. The difference between $a(n)$ and $P_{1}(n)$ satisfies

$$\begin{eqnarray}\mathop{\sum }_{n\leqslant x}(a(n)-P_{1}(n))\sim \biggl(1-\frac{\unicode[STIX]{x1D70B}}{4}\biggr)\mathop{\sum }_{n\leqslant x}P_{2}(n).\end{eqnarray}$$

Proof of Theorem 6.1.

Note first that if $n=p$ is prime, then $a(p)-P_{1}(p)=0$ , so the primes contribute nothing to this sum. Using $p$ and $q$ to denote prime numbers we can then write

$$\begin{eqnarray}\displaystyle \mathop{\sum }_{n\leqslant x}(a(n)-P_{1}(n)) & = & \displaystyle \mathop{\sum }_{p<x}\mathop{\sum }_{q\leqslant p}\mathop{\sum }_{\substack{ m\leqslant x/pq \\ P_{1}(m)\leqslant q}}(a(pqm)-p)\nonumber\\ \displaystyle & = & \displaystyle \mathop{\sum }_{p<x}\mathop{\sum }_{q\leqslant p}\mathop{\sum }_{\substack{ m\leqslant x/pq \\ P_{1}(m)\leqslant q}}(a(pq)-p+O(a(m)))\nonumber\end{eqnarray}$$

since $a(pq)\leqslant a(pqm)\leqslant a(pq)+a(m)$ . We can bound the error term above as

$$\begin{eqnarray}\displaystyle \mathop{\sum }_{p<x}\mathop{\sum }_{q\leqslant p}\mathop{\sum }_{\substack{ m\leqslant x/pq \\ P_{1}(m)\leqslant q}}a(m) & {\leqslant} & \displaystyle \mathop{\sum }_{p<x}\mathop{\sum }_{q\leqslant p}\mathop{\sum }_{\substack{ m\leqslant x/pq \\ P_{1}(m)\leqslant q}}B(m)\nonumber\\ \displaystyle & = & \displaystyle \sum ^{\prime }_{n\leqslant x}(B(n)-P_{1}(n)-P_{2}(n))=O\biggl(\frac{x^{4/3}}{\log ^{3}x}\biggr)\nonumber\end{eqnarray}$$

using Theorem 4.2. Here $\sum ^{\prime }$ denotes that the sum is over composite integers. Dividing the main sum into two sums based on whether the largest prime divisor divides the integer twice we get that

$$\begin{eqnarray}\displaystyle \mathop{\sum }_{n\leqslant x}(a(n)-P_{1}(n)) & = & \displaystyle \mathop{\sum }_{p\leqslant \sqrt{x}}\mathop{\sum }_{\substack{ m\leqslant x/p^{2} \\ P_{1}(m)\leqslant p}}a(p^{2})-p\nonumber\\ \displaystyle & & \displaystyle +\,\mathop{\sum }_{p<x}\mathop{\sum }_{q<p}\mathop{\sum }_{\substack{ m\leqslant x/pq \\ P_{1}(m)\leqslant q}}a(pq)-p+O(x^{4/3})\nonumber\\ \displaystyle & = & \displaystyle \mathop{\sum }_{p\leqslant \sqrt{x}}\mathop{\sum }_{\substack{ m\leqslant x/p^{2} \\ P_{1}(m)\leqslant p}}(p-1)\nonumber\\ \displaystyle & & \displaystyle +\,\mathop{\sum }_{p<x}\mathop{\sum }_{q<p}\mathop{\sum }_{\substack{ m\leqslant x/pq \\ P_{1}(m)\leqslant q}}\frac{q(q-1)}{p+q-1}+O(x^{4/3}).\nonumber\end{eqnarray}$$

The first sum above is

$$\begin{eqnarray}\displaystyle \mathop{\sum }_{p\leqslant \sqrt{x}}\mathop{\sum }_{\substack{ m\leqslant x/p^{2} \\ P_{1}(m)\leqslant p}}(p-1)\leqslant \mathop{\sum }_{p\leqslant \sqrt{x}}p\biggl\lfloor\frac{x}{p^{2}}\biggr\rfloor\leqslant \mathop{\sum }_{p\leqslant \sqrt{x}}\frac{x}{p}=O(x\log \log x), & & \displaystyle \nonumber\end{eqnarray}$$

so it can be absorbed into the error term. This leaves the second sum, which we simplify and reorder as

(3) $$\begin{eqnarray}\displaystyle & & \displaystyle \mathop{\sum }_{p<x}\mathop{\sum }_{q<p}\mathop{\sum }_{\substack{ m\leqslant x/pq \\ P_{1}(m)\leqslant q}}\frac{q(q-1)}{p+q-1}\nonumber\\ \displaystyle & & \displaystyle \quad =\mathop{\sum }_{p<x}\mathop{\sum }_{q<p}\mathop{\sum }_{\substack{ m\leqslant x/pq \\ P_{1}(m)\leqslant q}}\biggl(\frac{q^{2}}{p+q}-\frac{q}{p+q-1}+\frac{q^{2}}{(p+q)(p+q-1)}\biggr)\nonumber\\ \displaystyle & & \displaystyle \quad =\mathop{\sum }_{p<x}\mathop{\sum }_{q<p}\mathop{\sum }_{\substack{ m\leqslant x/pq \\ P_{1}(m)\leqslant q}}\frac{q^{2}}{p+q}+O(x)\nonumber\\ \displaystyle & & \displaystyle \quad =\mathop{\sum }_{m\leqslant x/6}\mathop{\sum }_{\substack{ p<x/m \\ p>P_{1}(m)}}\mathop{\sum }_{\substack{ q<p \\ q\leqslant x/mp \\ q\geqslant P_{1}(m)}}\frac{q^{2}}{p+q}+O(x)\nonumber\\ \displaystyle & & \displaystyle \quad =\mathop{\sum }_{m\leqslant x/6}\mathop{\sum }_{\substack{ p\leqslant \sqrt{x/m} \\ p>P_{1}(m)}}\mathop{\sum }_{\substack{ q<p \\ q\geqslant P_{1}(m)}}\frac{q^{2}}{p+q}+\mathop{\sum }_{m\leqslant x/6}\mathop{\sum }_{\substack{ \sqrt{x/m}<p<x/m \\ p>P_{1}(m)}}\mathop{\sum }_{\substack{ q\leqslant x/mp \\ q\geqslant P_{1}(m)}}\frac{q^{2}}{p+q}+O(x)\nonumber\\ \displaystyle & & \displaystyle \quad =S_{1}+S_{2}+O(x).\end{eqnarray}$$

We evaluate the two sums $S_{1}$ and $S_{2}$ separately. Taking first $S_{1}$ , we find that the sum is dominated by small values of $m$ . The contribution to $S_{1}$ by those $m\geqslant x^{\unicode[STIX]{x1D716}}$ for any fixed small $0<\unicode[STIX]{x1D716}<1/4$ is

$$\begin{eqnarray}\displaystyle \mathop{\sum }_{x^{\unicode[STIX]{x1D716}}\leqslant m\leqslant x/6}\mathop{\sum }_{\substack{ p\leqslant \sqrt{x/m} \\ p>P_{1}(m)}}\mathop{\sum }_{\substack{ q<p \\ q\geqslant P_{1}(m)}}\frac{q^{2}}{p+q} & {\leqslant} & \displaystyle \mathop{\sum }_{x^{\unicode[STIX]{x1D716}}<m\leqslant x/6}\mathop{\sum }_{\substack{ p\leqslant \sqrt{x/m}}}\mathop{\sum }_{\substack{ q<p}}q\nonumber\\ \displaystyle & \ll & \displaystyle \mathop{\sum }_{x^{\unicode[STIX]{x1D716}}\leqslant m\leqslant x/6}\mathop{\sum }_{\substack{ p\leqslant \sqrt{x/m}}}\frac{p^{2}}{\log p}\nonumber\\ \displaystyle & \ll & \displaystyle \mathop{\sum }_{x^{\unicode[STIX]{x1D716}}\leqslant m\leqslant x/6}\biggl(\frac{x}{m}\biggr)^{3/2}=O(x^{(3-\unicode[STIX]{x1D716})/2}),\nonumber\end{eqnarray}$$

and likewise the contribution from either $p$ or $q\leqslant x^{\unicode[STIX]{x1D716}}$ is insignificant, so we can write

(4) $$\begin{eqnarray}S_{1}=\mathop{\sum }_{m<x^{\unicode[STIX]{x1D716}}}\mathop{\sum }_{\substack{ x^{\unicode[STIX]{x1D716}}<p\leqslant \sqrt{x/m}}}\mathop{\sum }_{\substack{ x^{\unicode[STIX]{x1D716}}<q<p}}\frac{q^{2}}{p+q}+O(x^{(3-\unicode[STIX]{x1D716})/2}).\end{eqnarray}$$

We treat the inner sum using partial summation

$$\begin{eqnarray}\displaystyle \mathop{\sum }_{\substack{ x^{\unicode[STIX]{x1D716}}<q<p}}\frac{q^{2}}{p+q}=\int _{x^{\unicode[STIX]{x1D716}}}^{p}\frac{s^{2}}{(p+s)\log s}\,ds+O(p^{2}\text{e}^{-\sqrt{\log p}}). & & \displaystyle \nonumber\end{eqnarray}$$

We tackle the integral by expanding the fraction as a geometric series

$$\begin{eqnarray}\frac{s^{2}}{(p+s)\log s}=\frac{s^{2}}{p\log s}\mathop{\sum }_{i=0}^{\infty }\biggl(-\frac{s}{p}\biggr)^{i}\end{eqnarray}$$

(which converges for all $s<p$ ) and integrate term by term,

$$\begin{eqnarray}\displaystyle \int _{x^{\unicode[STIX]{x1D716}}}^{p}\frac{s^{2}}{(p+s)\log s}ds & = & \displaystyle \mathop{\sum }_{i=0}^{\infty }\biggl(\frac{(-1)^{i}}{p^{i+1}}\int _{x^{\unicode[STIX]{x1D716}}}^{p}\frac{s^{i+2}}{\log s}\,ds\biggr)\nonumber\\ \displaystyle & = & \displaystyle \mathop{\sum }_{i=0}^{\infty }\biggl(\frac{(-1)^{i}}{p^{i+1}}(\text{li}(p^{i+3})-\text{li}(x^{\unicode[STIX]{x1D716}(i+3)}))\biggr)\nonumber\\ \displaystyle & = & \displaystyle \mathop{\sum }_{i=0}^{\infty }\biggl(\frac{(-1)^{i}}{p^{i+1}}\biggl(\frac{p^{i+3}}{\log p^{i+3}}\biggl(\mathop{\sum }_{k=0}^{N-1}\frac{k!}{\log ^{k}p^{i+3}}\nonumber\\ \displaystyle & & \displaystyle +\,O_{N}\biggl(\frac{1}{\log ^{N}p^{i+3}}\biggr)\biggr)+O\biggl(\frac{x^{\unicode[STIX]{x1D716}(i+3)}}{\unicode[STIX]{x1D716}(i+3)\log x}\biggr)\biggr)\biggr)\nonumber\\ \displaystyle & = & \displaystyle \frac{p^{2}}{\log p}\!\mathop{\sum }_{i=0}^{\infty }\!\mathop{\sum }_{k=0}^{N-1}\biggl(\frac{(-1)^{i}k!}{(i+3)^{k+1}\log ^{k}p}\biggr)+O_{N}\biggl(\frac{p^{2}}{\log ^{N+1}p}\biggr).\nonumber\end{eqnarray}$$

Here we have used the asymptotic expansion for $\text{li}(x)$ , where $N\geqslant 0$ is a fixed integer. Plugging this into (4) and applying partial summation to the variable $p$ , we obtain

(5) $$\begin{eqnarray}\displaystyle S_{1} & = & \displaystyle \mathop{\sum }_{m<x^{\unicode[STIX]{x1D716}}}\biggl(\mathop{\sum }_{x^{\unicode[STIX]{x1D716}}<p<\sqrt{x/m}}\biggl(\frac{p^{2}}{\log p}\mathop{\sum }_{i=0}^{\infty }\mathop{\sum }_{k=0}^{N-1}\biggl(\frac{(-1)^{i}k!}{(i+3)^{k+1}\log ^{k}p}\biggr)\nonumber\\ \displaystyle & & \displaystyle +\,O_{N}\biggl(\frac{p^{2}}{\log ^{N+1}p}\biggr)\biggr)\biggr)\nonumber\\ \displaystyle & = & \displaystyle \mathop{\sum }_{m<x^{\unicode[STIX]{x1D716}}}\biggl(\int _{x^{\unicode[STIX]{x1D716}}}^{\sqrt{x/m}}\frac{t^{2}}{\log ^{2}t}\mathop{\sum }_{i=0}^{\infty }\mathop{\sum }_{k=0}^{N-1}\biggl(\frac{(-1)^{i}k!}{(i+3)^{k+1}\log ^{k}t}\biggr)\,dt\nonumber\\ \displaystyle & & \displaystyle +\,O_{N}\biggl(\frac{(x/m)^{3/2}}{\log ^{N+2}(x/m)}\biggr)\biggr).\end{eqnarray}$$

Integrating by parts one finds that

$$\begin{eqnarray}\displaystyle \int \frac{t^{2}}{\log ^{k+2}t}\,dt & = & \displaystyle \frac{3^{k+1}}{(k+1)!}\text{li}(t^{3})-t^{3}\mathop{\sum }_{h=0}^{k}\frac{3^{h}(k-h)!}{(k+1)!\log ^{h+1}t}+C\nonumber\\ \displaystyle & = & \displaystyle t^{3}\mathop{\sum }_{h=k+1}^{N}\frac{3^{k-h}h!}{(k+1)!\log ^{h+1}t}+O_{N}\biggl(\frac{t^{3}}{\log ^{N+2}t}\biggr)\nonumber\end{eqnarray}$$

since the sum in the first line above simply subtracts off the first $k+1$ terms in the asymptotic expansion of $(3^{k+1}/(k+1)!)\text{li}(t^{3})$ . Using this to evaluate the integral in (5) we obtain

$$\begin{eqnarray}\displaystyle & & \displaystyle \mathop{\sum }_{i=0}^{\infty }\mathop{\sum }_{k=0}^{N-1}\biggl(\frac{(-1)^{i}k!}{(i+3)^{k+1}}\biggl(t^{3}\mathop{\sum }_{h=k+1}^{N}\frac{3^{k-h}h!}{(k+1)!\log ^{h+1}t}\nonumber\\ \displaystyle & & \displaystyle \qquad +\,O_{N}\biggl(\frac{t^{3}}{\log ^{N+2}t}\biggr)\biggr)\biggr)\biggr|_{t=x^{\unicode[STIX]{x1D716}}}^{t=\sqrt{x/m}}.\nonumber\end{eqnarray}$$

The lower limit of integration can easily be absorbed into the error term, so we need only concern the upper limit. Evaluating this expression there, it becomes

(6) $$\begin{eqnarray}\displaystyle & & \displaystyle \mathop{\sum }_{i=0}^{\infty }\mathop{\sum }_{k=0}^{N-1}\biggl(\frac{(-1)^{i}k!}{(i+3)^{k+1}}\biggl(\frac{x}{m}\biggr)^{3/2}\mathop{\sum }_{h=k+1}^{N}\frac{3^{k-h}h!2^{h+1}}{(k+1)!\log ^{h+1}(x/m)}\biggr)\nonumber\\ \displaystyle & & \displaystyle =2\biggl(\frac{x}{m}\biggr)^{3/2}\mathop{\sum }_{i=0}^{\infty }(-1)^{i}\mathop{\sum }_{h=1}^{N}\frac{2^{h}h!}{\log ^{h+1}(x/m)}\mathop{\sum }_{k=0}^{h-1}\frac{3^{k-h}}{(k+1)(i+3)^{k+1}}\nonumber\\ \displaystyle & & \displaystyle =2\biggl(\frac{x}{m}\biggr)^{3/2}\mathop{\sum }_{h=0}^{N-1}\frac{2^{h+1}h!}{\log ^{h+2}(x/m)}\mathop{\sum }_{k=0}^{h}\frac{3^{k-h-1}}{k+1}\mathop{\sum }_{i=3}^{\infty }\frac{(-1)^{i+1}}{i^{k+1}}.\end{eqnarray}$$

We therefore get the estimate

$$\begin{eqnarray}\displaystyle S_{1} & = & \displaystyle 2\mathop{\sum }_{m<x^{\unicode[STIX]{x1D716}}}\biggl(\biggl(\frac{x}{m}\biggr)^{3/2}\biggl(\mathop{\sum }_{h=0}^{N-1}\frac{2^{h+1}h!}{\log ^{h+2}(x/m)}\mathop{\sum }_{k=0}^{h}\frac{3^{k-h-1}}{k+1}\mathop{\sum }_{i=3}^{\infty }\frac{(-1)^{i+1}}{i^{k+1}}\nonumber\\ \displaystyle & & \displaystyle +\,O_{N}\biggl(\frac{1}{\log ^{N+2}(x/m)}\biggr)\biggr)\biggr).\nonumber\end{eqnarray}$$

We now treat $S_{2}$ . As was the case with $S_{1}$ , we can ignore the contribution from those $m>x^{\unicode[STIX]{x1D716}}$ , $q\geqslant x^{\unicode[STIX]{x1D716}}$ or $p>x^{1-\unicode[STIX]{x1D716}}$ , so

(7) $$\begin{eqnarray}S_{2}=\mathop{\sum }_{m<x^{\unicode[STIX]{x1D716}}}\mathop{\sum }_{\substack{ \sqrt{x/m}<p<x^{1-\unicode[STIX]{x1D716}}}}\mathop{\sum }_{\substack{ x^{\unicode[STIX]{x1D716}}<q<x/mp}}\frac{q^{2}}{p+q}+O(x^{(3-\unicode[STIX]{x1D716})/2}).\end{eqnarray}$$

We also treat the innermost sum similarly to $S_{1}$ , resulting in an integration similar to (5) but with different limits of integration:

$$\begin{eqnarray}\displaystyle \mathop{\sum }_{\substack{ x^{\unicode[STIX]{x1D716}}<q<x/mp}}\frac{q^{2}}{p+q} & = & \displaystyle \int _{x^{\unicode[STIX]{x1D716}}}^{x/mp}\frac{s^{2}}{(p+s)\log s}\,ds=\mathop{\sum }_{i=0}^{\infty }\biggl(\frac{(-1)^{i}}{p^{i+1}}\int _{x^{\unicode[STIX]{x1D716}}}^{x/mp}\frac{s^{i+2}}{\log s}\,ds\biggr)\nonumber\\ \displaystyle & = & \displaystyle \mathop{\sum }_{i=0}^{\infty }\biggl(\frac{(-1)^{i}}{p^{i+1}}\biggl(\text{li}\biggl(\biggl(\frac{x}{mp}\biggr)^{i+3}\biggr)-\text{li}(x^{\unicode[STIX]{x1D716}(i+3)})\biggr)\biggr)\nonumber\\ \displaystyle & = & \displaystyle \mathop{\sum }_{i=0}^{\infty }\biggl(\frac{(-1)^{i}}{p^{i+1}}\biggl(\text{li}\biggl(\biggl(\frac{x}{mp}\biggr)^{i+3}\biggr)\biggr)\biggr)+O\biggl(\frac{x^{3\unicode[STIX]{x1D716}}}{p}\biggr).\nonumber\end{eqnarray}$$

Expanding the main term above using the asymptotic expansion for the logarithmic integral we obtain

(8) $$\begin{eqnarray}\displaystyle & & \displaystyle \mathop{\sum }_{i=0}^{\infty }\biggl(\frac{(-1)^{i}}{p^{i+1}}\biggl(\mathop{\sum }_{k=0}^{N-1}\frac{x^{i+3}k!}{(mp)^{i+3}\log ((x/mp)^{i+3})^{k+1}}\biggr)\biggr)\nonumber\\ \displaystyle & & \displaystyle \qquad +\,O_{N}\biggl(\mathop{\sum }_{i=0}^{\infty }\frac{(-1)^{i}x^{i+3}}{p^{i+1}(mp)^{i+3}\log ^{N+1}(x/mp)^{i+3}}\biggr)\nonumber\\ \displaystyle & & \displaystyle =p^{2}\mathop{\sum }_{i=0}^{\infty }\biggl(\frac{x}{mp^{2}}\biggr)^{i+3}\nonumber\\ \displaystyle & & \displaystyle \qquad \times \,\mathop{\sum }_{k=0}^{N-1}\biggl(\frac{(-1)^{i}k!}{(i+3)^{k+1}\log ^{k+1}(x/m)(1-\log p/\text{log}(x/m))^{k+1}}\biggr)\nonumber\\ \displaystyle & & \displaystyle \qquad +\,O_{N}\biggl(\frac{x^{3}}{m^{3}p^{4}\log ^{N+1}(x/mp)}\biggr)\nonumber\\ \displaystyle & & \displaystyle =p^{2}\mathop{\sum }_{i=3}^{\infty }\biggl(\frac{x}{mp^{2}}\biggr)^{i}\mathop{\sum }_{k=0}^{N-1}\biggl(\frac{(-1)^{i+1}k!}{i^{k+1}\log ^{k+1}(x/m)}\mathop{\sum }_{j=0}^{\infty }\biggl(\binom{k+j}{j}\biggl(\frac{\log p}{\log (x/m)}\biggr)^{j}\biggr)\biggr)\nonumber\\ \displaystyle & & \displaystyle \qquad +\,O_{N}\biggl(\frac{(x/m)^{3}}{p^{4}\log ^{N+1}(x/mp)}\biggr).\end{eqnarray}$$

Here we have used the series expansion $(1/(1-x))^{k+1}=\sum _{j=0}^{\infty }(\binom{k+j}{j}x^{j})$ . Inserting this into (7), and applying partial summation to $p$ we get that

(9) $$\begin{eqnarray}\displaystyle S_{2} & = & \displaystyle \mathop{\sum }_{m<x^{\unicode[STIX]{x1D716}}}\biggl(\int _{\sqrt{x/m}}^{x^{1-\unicode[STIX]{x1D716}}}\frac{t^{2}}{\log t}\mathop{\sum }_{i=3}^{\infty }\biggl(\frac{x}{mt^{2}}\biggr)^{i}\mathop{\sum }_{k=0}^{N-1}\frac{(-1)^{i+1}k!}{i^{k+1}\log ^{k+1}(x/m)}\nonumber\\ \displaystyle & & \displaystyle \times \,\mathop{\sum }_{j=0}^{\infty }\biggl(\binom{k+j}{j}\biggl(\frac{\log t}{\log (x/m)}\biggr)^{j}\biggr)\,dt+O_{N}\biggl(\frac{(x/m)^{3/2}}{\log ^{N+2}(x/m)}\biggr)\biggr)\nonumber\\ \displaystyle & = & \displaystyle \mathop{\sum }_{m<x^{\unicode[STIX]{x1D716}}}\biggl(\mathop{\sum }_{i=3}^{\infty }\biggl((-1)^{i+1}\biggl(\frac{x}{m}\biggr)^{i}\mathop{\sum }_{k=0}^{N-1}\biggl(\frac{(-1)^{i+1}k!}{i^{k+1}\log ^{k+1}(x/m)}\int _{\sqrt{x/m}}^{x^{1-\unicode[STIX]{x1D716}}}\frac{1}{t^{2i-2}\log t}\nonumber\\ \displaystyle & & \displaystyle \times \,\mathop{\sum }_{j=0}^{\infty }\biggl(\binom{k+j}{j}\biggl(\frac{\log t}{\log (x/m)}\biggr)^{j}\biggr)\,dt\biggr)\biggr)\nonumber\\ \displaystyle & & \displaystyle +\,O_{N}\biggl(\frac{(x/m)^{3/2}}{\log ^{N+2}(x/m)}\biggr)\biggr).\end{eqnarray}$$

Using the fact that

(10) $$\begin{eqnarray}\int \frac{\log ^{j-1}p}{t^{2i-2}}\,dt=\left\{\begin{array}{@{}ll@{}}\text{li}(t^{-2i+3})+C\quad & \text{if }j=0,\\ -\displaystyle \frac{\log ^{j-1}t}{(2i-3)t^{2i-3}}\mathop{\sum }_{l=0}^{j-1}\frac{j!}{(j-l)!(2i-3)^{l}\log ^{l}t}+C\quad & \text{if }j\geqslant 1,\end{array}\right.\end{eqnarray}$$

the integral in the expression above becomes

$$\begin{eqnarray}\displaystyle & & \displaystyle \biggl(\text{li}\biggl(\frac{1}{t^{2i-3}}\biggr)-\frac{1}{t^{2i-3}}\mathop{\sum }_{j=1}^{\infty }\biggl(\binom{k+j}{j}\biggl(\frac{1}{\log (x/m)}\biggr)^{j}\nonumber\\ \displaystyle & & \displaystyle \qquad \times \,\mathop{\sum }_{l=0}^{j-1}\frac{j!\log ^{j-1}t}{(j-l)!(2i-3)^{l+1}\log ^{l}t}\biggr)\biggr)\biggr|_{t=\sqrt{x/m}}^{t=x^{1-\unicode[STIX]{x1D716}}}.\nonumber\end{eqnarray}$$

When evaluated at $t=x^{1-\unicode[STIX]{x1D716}}$ , the above expression can be absorbed into the existing error term, so we need only evaluate this expression when $t=\sqrt{x/m}$ , in which case it becomes

(11) $$\begin{eqnarray}\displaystyle & & \displaystyle -\biggl(\text{li}\biggl(\biggl(\frac{x}{m}\biggr)^{-(2i-3)/2}\biggr)-\biggl(\frac{x}{m}\biggr)^{-(2i-3)/2}\mathop{\sum }_{j=1}^{\infty }\biggl(\binom{k+j}{j}\frac{1}{2^{j-1}\log (x/m)}\nonumber\\ \displaystyle & & \displaystyle \qquad \times \,\mathop{\sum }_{l=0}^{j-1}\frac{j!2^{l}}{(j-l)!(2i-3)^{l+1}\log ^{l}(x/m)}\biggr)\biggr)\nonumber\\ \displaystyle & & \displaystyle =-\biggl(\text{li}\biggl(\biggl(\frac{x}{m}\biggr)^{-(2i-3)/2}\biggr)-\biggl(\frac{x}{m}\biggr)^{-(2i-3)/2}\mathop{\sum }_{l=0}^{\infty }\frac{2^{l+1}}{(2i-3)^{l+1}\log ^{l+1}(x/m)}\nonumber\\ \displaystyle & & \displaystyle \qquad \times \,\mathop{\sum }_{j=l+1}^{\infty }\biggl(\binom{k+j}{j}\frac{j!}{2^{j}(j-l)!}\biggr)\biggr).\end{eqnarray}$$

The sum over $j$ can be evaluated as $(2^{k+1}-2^{-l})(l+k)!/k!$ , and the sum over $l$ can be truncated at $N-k-1$ , with the remainder of the sum being absorbed into the existing error term, $O_{N}((x/m)^{3/2}/\text{log}^{N+2}\,(x/m))$ . Use the asymptotic expansion of the logarithmic integral one more time, again truncating at $N-k-1$ , turns the expression in (11) into

$$\begin{eqnarray}\displaystyle & & \displaystyle \biggl(\frac{x}{m}\biggr)^{-(2i-3)/2}\mathop{\sum }_{l=0}^{N-k-1}\biggl(\frac{2}{(2i-3)^{l+1}\log ^{l+1}(x/m)}\nonumber\\ \displaystyle & & \displaystyle \qquad \times \,\biggl(l!(-1)^{l}2^{l}+\frac{(2^{l+k+1}-1)(l+k)!}{k!}\biggr)\biggr).\nonumber\end{eqnarray}$$

Inserting this back into (9) in place of the integral, and reindexing so that the summation runs over the exponent on the logarithm we get that the main term is

$$\begin{eqnarray}\displaystyle & & \displaystyle \mathop{\sum }_{m<x^{\unicode[STIX]{x1D716}}}\biggl(\frac{x}{m}\biggr)^{3/2}\mathop{\sum }_{i=3}^{\infty }\mathop{\sum }_{h=0}^{N-1}\biggl(\frac{(-1)^{i+1}}{\log ^{h+2}(x/m)}\mathop{\sum }_{k=0}^{h}\biggl(\frac{2}{i^{k+1}(2i-3)^{h-k+1}}\nonumber\\ \displaystyle & & \displaystyle \qquad \times \,(k!(h-k)!(-1)^{h-k}2^{h-k}+(2^{h+1}-1)h!)\biggr)\biggr).\nonumber\end{eqnarray}$$

Combining that with the corresponding estimate (6), we have that the entire main term of the sum that we are interested in (3) is equal to

$$\begin{eqnarray}\displaystyle & & \displaystyle \mathop{\sum }_{m\leqslant x/6}\biggl(\frac{x}{m}\biggr)^{3/2}\mathop{\sum }_{h=0}^{N-1}\frac{1}{\log ^{h+2}(x/m)}\mathop{\sum }_{k=0}^{h}\mathop{\sum }_{i=3}^{\infty }\frac{2(-1)^{i+1}}{i^{k+1}}\nonumber\\ \displaystyle & & \displaystyle \qquad \times \,\biggl(\frac{2^{h+1}3^{k-h-1}h!}{(k+1)}+\frac{(k!(h-k)!(-2)^{h-k}+(2^{h+1}-1)h!)}{(2i-3)^{h+1-k}}\biggr)\nonumber\end{eqnarray}$$

with an error term of $O_{N}((x/m)^{3/2}/\text{log}^{N+2}\,(x/m))$ . Note that the quantity given by the double summation over $k$ and $i$ is a constant depending only on $h$ , which we call $C_{h}$ . Thus,

$$\begin{eqnarray}\displaystyle & & \displaystyle \mathop{\sum }_{n\leqslant x}(a(n)-P_{1}(n))\nonumber\\ \displaystyle & & \displaystyle \quad =x^{3/2}\mathop{\sum }_{m\leqslant x^{\unicode[STIX]{x1D716}}}\biggl(\frac{1}{m^{3/2}}\mathop{\sum }_{h=0}^{N-1}\frac{C_{h}}{\log ^{h+2}(x/m)}+O_{N}\biggl(\frac{1}{m^{3/2}\log ^{N+2}(x/m)}\biggr)\biggr)\nonumber\\ \displaystyle & & \displaystyle \quad =x^{3/2}\mathop{\sum }_{h=0}^{N-1}C_{h}\mathop{\sum }_{m\leqslant x^{\unicode[STIX]{x1D716}}}\frac{1}{m^{3/2}}\frac{1}{\log ^{h+2}(x/m)}+O_{N}\biggl(\frac{x^{3/2}}{\log ^{N+2}x}\biggr).\nonumber\end{eqnarray}$$

Since

$$\begin{eqnarray}\displaystyle \mathop{\sum }_{m\leqslant x^{\unicode[STIX]{x1D716}}}\frac{1}{m^{3/2}\log ^{h+2}(x/m)} & = & \displaystyle \mathop{\sum }_{m\leqslant x^{\unicode[STIX]{x1D716}}}\frac{1}{m^{3/2}\log ^{h+2}x}\biggl(\frac{1}{1-\log m/\text{log}\,x}\biggr)^{h+2}\nonumber\\ \displaystyle & = & \displaystyle \mathop{\sum }_{m\leqslant x^{\unicode[STIX]{x1D716}}}\frac{1}{m^{3/2}\log ^{h+2}x}\mathop{\sum }_{j=0}^{\infty }\binom{h+1+j}{j}\biggl(\frac{\log m}{\log x}\biggr)^{j}\nonumber\\ \displaystyle & = & \displaystyle \mathop{\sum }_{j=0}^{\infty }\frac{\binom{h+j+1}{j}}{\log ^{h+j+2}x}\mathop{\sum }_{m\leqslant x^{\unicode[STIX]{x1D716}}}\frac{\log ^{j}m}{m^{3/2}}\nonumber\\ \displaystyle & = & \displaystyle \mathop{\sum }_{j=0}^{N-h-1}\frac{\binom{h+j+1}{j}}{\log ^{h+j+2}x}(-1)^{j}\unicode[STIX]{x1D701}^{(j)}\biggl(\frac{3}{2}\biggr)\nonumber\\ \displaystyle & & \displaystyle +\,O_{N}\biggl(\frac{1}{\log ^{N+2}x}\biggr),\nonumber\end{eqnarray}$$

where $\unicode[STIX]{x1D701}^{(j)}(3/2)$ denotes the $j$ th derivative of the zeta function at $3/2$ , we can conclude that

$$\begin{eqnarray}\displaystyle \mathop{\sum }_{n\leqslant x}(a(n)-P_{1}(n)) & = & \displaystyle x^{3/2}\mathop{\sum }_{h=0}^{N-1}C_{h}\mathop{\sum }_{j=0}^{N-h-1}\frac{\binom{h+j+1}{j}}{\log ^{h+j+2}x}(-1)^{j}\unicode[STIX]{x1D701}^{(j)}\biggl(\frac{3}{2}\biggr)\nonumber\\ \displaystyle & & \displaystyle +\,O_{N}\biggl(\frac{x^{3/2}}{\log ^{N+2}x}\biggr)\nonumber\\ \displaystyle & = & \displaystyle x^{3/2}\mathop{\sum }_{\ell =0}^{N-1}\frac{1}{\log ^{\ell +2}x}\mathop{\sum }_{h=0}^{\ell }\binom{\ell +1}{\ell -h}C_{h}(-1)^{j}\unicode[STIX]{x1D701}^{(\ell -h)}\biggl(\frac{3}{2}\biggr)\nonumber\\ \displaystyle & & \displaystyle +\,O_{N}\biggl(\frac{x^{3/2}}{\log ^{N+2}x}\biggr)\nonumber\\ \displaystyle & = & \displaystyle x^{3/2}\mathop{\sum }_{\ell =0}^{N-1}\frac{D_{\ell }}{\log ^{\ell +2}x}+O_{N}\biggl(\frac{x^{3/2}}{\log ^{N+2}x}\biggr)\nonumber\end{eqnarray}$$

where

(12) $$\begin{eqnarray}\displaystyle D_{\ell } & = & \displaystyle 2\mathop{\sum }_{h=0}^{\ell }\binom{\ell +1}{\ell -h}\unicode[STIX]{x1D701}^{(\ell -h)}\biggl(\frac{3}{2}\biggr)\mathop{\sum }_{k=0}^{h}\mathop{\sum }_{i=3}^{\infty }\frac{(-1)^{\ell -h+i+1}}{i^{k+1}}\nonumber\\ \displaystyle & & \displaystyle \times \,\biggl(\frac{2^{h+1}h!}{3^{h-k+1}(k+1)}+\frac{(k!(h-k)!(-2)^{h-k}+(2^{h+1}-1)h!)}{(2i-3)^{h+1-k}}\biggr).\end{eqnarray}$$

In the case $\ell =0$ this reduces to

$$\begin{eqnarray}\displaystyle D_{0} & = & \displaystyle 2\unicode[STIX]{x1D701}\biggl(\frac{3}{2}\biggr)\mathop{\sum }_{i=3}^{\infty }\frac{(-1)^{i+1}}{i}\biggl(\frac{2}{3}+\frac{2}{2i-3}\biggr)\nonumber\\ \displaystyle & = & \displaystyle 2\unicode[STIX]{x1D701}\biggl(\frac{3}{2}\biggr)\mathop{\sum }_{i=3}^{\infty }(-1)^{i+1}\biggl(\frac{2}{3i}+\biggl(-\frac{2}{3i}+\frac{4}{3(2i-3)}\biggr)\biggr)\nonumber\\ \displaystyle & = & \displaystyle \frac{8\unicode[STIX]{x1D701}(3/2)}{3}\mathop{\sum }_{i=3}^{\infty }\frac{(-1)^{i+1}}{2i-3}=\frac{8\unicode[STIX]{x1D701}(3/2)}{3}\biggl(1-\frac{\unicode[STIX]{x1D70B}}{4}\biggr).\square\nonumber\end{eqnarray}$$

7 Open questions and acknowledgements

There are many remaining questions and directions that this research could be further pursued. A few examples of potentially interesting questions are given below.

Computations so far have failed to find any examples of such an integer.