2.1 Sums of digits of integers in different bases

Let $a,b\geqslant 2$ be fixed multiplicatively independent integers. Senge and Straus [Reference Senge and Straus18] have shown that there are only finitely many positive integers $n$ such that the sum of digits of $n$ in both bases $a$ and $b$ is at most $K$ , with $K$ any fixed number. Stewart [Reference Stewart19] makes this effective and for all $n>25$ gives a lower bound

(2.1) $$\begin{eqnarray}s_{a}(n)+s_{b}(n)>\frac{\log _{2}n}{\log _{3}n+C(a,b)}-1,\end{eqnarray}$$

where $C(a,b)$ is some constant depending on $a$ and $b$ .

The constant $C(a,b)$ is not made explicit in [Reference Stewart19]. Here we do so, as this is important for our purposes, and may also be of independent interest. As in [Reference Stewart19], our approach is based on lower bounds for linear forms in logarithms, where we use the bound of Matveev [Reference Matveev16]. We only need it for logarithms of rational numbers rather than in its full generality for logarithms of algebraic numbers. We note that for us only the asymptotic dependence of $C(a,b)$ on $a$ and $b$ is important, but we also use this as an opportunity to derive a completely explicit expression for $C(a,b)$ .

Let $\unicode[STIX]{x1D70C}=r/s$ be a rational number in a reduced form, that is, with $\gcd (r,s)=1$ and $s\geqslant 1$ . Then its height is defined as

$$\begin{eqnarray}h(\unicode[STIX]{x1D70C})=h(r/s)=\max \{\log |r|,\log s\}.\end{eqnarray}$$

Let $\unicode[STIX]{x1D6FC}_{1},\ldots ,\unicode[STIX]{x1D6FC}_{l}$ be rational numbers not zero or $\pm 1$ . We put $A_{i}=h(\unicode[STIX]{x1D6FC}_{i})$ for $i=1,\ldots ,l$ . We let $d_{1},\ldots ,d_{l}$ be non-zero integers and denote $\max \{|d_{1}|,\ldots ,|d_{l}|\}$ by $D$ . Let

(2.2) $$\begin{eqnarray}\unicode[STIX]{x1D6EC}=\mathop{\prod }_{i=1}^{l}\unicode[STIX]{x1D6FC}_{i}^{d_{i}}-1.\end{eqnarray}$$

The result below follows from [Reference Matveev16, Corollary 2.3], and the details have been worked out as [Reference Bugeaud, Mignotte and Siksek5, Theorem 9.4].

Lemma 2.1. If $\unicode[STIX]{x1D6EC}\neq 0$ , then

$$\begin{eqnarray}\log |\unicode[STIX]{x1D6EC}|>-1.4\cdot 30^{l+3}l^{4.5}(1+\log D)\mathop{\prod }_{i=1}^{l}A_{i}.\end{eqnarray}$$

We are now ready to present a more explicit version of inequality (2.1).

Lemma 2.2. Assume that $a$ and $b$ are coprime integers ${\geqslant}2$ . Let $B\geqslant \max \{a,b\}$ . Then for all $n>\exp (10^{15}(\log B)^{4})$ the inequality

$$\begin{eqnarray}s_{a}(n)+s_{b}(n)>\frac{\log _{2}n}{\log _{3}n+C(a,b)}\end{eqnarray}$$

holds with $C(a,b)=\log (2\cdot 10^{12}(\log B)^{2})$ .

Proof. We follow [Reference Stewart19, pp. 66–69] with the appropriate modifications. Consider the following $a$ -ary and $b$ -ary expansions of $n>B^{4}$ :

$$\begin{eqnarray}\displaystyle n & = & \displaystyle a_{1}a^{m_{1}}+a_{2}a^{m_{2}}+\cdots +a_{r}a^{m_{r}},\quad a_{i}\in \{1,\ldots ,a-1\},\;1\leqslant i\leqslant r,\nonumber\\ \displaystyle n & = & \displaystyle b_{1}b^{\ell _{1}}+b_{2}b^{\ell _{2}}+\cdots +b_{t}b^{\ell _{t}},\quad b_{i}\in \{1,\ldots ,b-1\},\;1\leqslant i\leqslant t,\nonumber\end{eqnarray}$$

where

$$\begin{eqnarray}m_{1}>\cdots >m_{r}\geqslant 0\quad \text{and}\quad \ell _{1}>\ell _{2}>\cdots >\ell _{t}\geqslant 0.\end{eqnarray}$$

We put

$$\begin{eqnarray}\unicode[STIX]{x1D717}=c_{0}\log _{2}n,\end{eqnarray}$$

where $c_{0}$ is an explicit constant depending on $B$ that is to be chosen later. We now consider the intervals

$$\begin{eqnarray}\unicode[STIX]{x1D6E9}_{1}=[1,\unicode[STIX]{x1D717}),\qquad \unicode[STIX]{x1D6E9}_{2}=[\unicode[STIX]{x1D717},\unicode[STIX]{x1D717}^{2}),\ldots ,\unicode[STIX]{x1D6E9}_{k}=[\unicode[STIX]{x1D717}^{k-1},\unicode[STIX]{x1D717}^{k}),\end{eqnarray}$$

where $k$ satisfies the inequalities

(2.3) $$\begin{eqnarray}\unicode[STIX]{x1D717}^{k}\leqslant \frac{\log n}{4\log B}<\unicode[STIX]{x1D717}^{k+1}.\end{eqnarray}$$

Since $n\geqslant B^{4}$ , we have that $k\geqslant 1$ in (2.3). We now show that for an appropriate $c_{0}$ and sufficiently large $n$ each interval $\unicode[STIX]{x1D6E9}_{s}$ contains either a term of the form $m_{1}-m_{i}$ for $i=2,\ldots ,r$ or a term of the form $\ell _{1}-\ell _{j}$ for $j=2,\ldots ,t$ . Let us suppose that it is not so. Then for some $1\leqslant s\leqslant k$ , the interval $\unicode[STIX]{x1D6E9}_{s}$ does not contain any $m_{1}-m_{i}$ and any $\ell _{1}-\ell _{j}$ . So, let $u,v$ be given by

(2.4) $$\begin{eqnarray}\begin{array}{@{}c@{}}m_{1}-m_{u}<\unicode[STIX]{x1D717}^{s-1},\qquad m_{1}-m_{u+1}\geqslant \unicode[STIX]{x1D717}^{s},\\ \ell _{1}-\ell _{v}<\unicode[STIX]{x1D717}^{s-1},\qquad \ell _{1}-\ell _{v+1}\geqslant \unicode[STIX]{x1D717}^{s}.\end{array}\end{eqnarray}$$

In the case $m_{1}-m_{r}<\unicode[STIX]{x1D717}^{s-1}$ , we choose $u=r$ . Similarly, we choose $v=t$ in the case $\ell _{1}-\ell _{t}<\unicode[STIX]{x1D717}^{s-1}$ . Note that

$$\begin{eqnarray}m_{1}=\biggl\lfloor\frac{\log n}{\log a}\biggr\rfloor\geqslant \frac{\log n}{\log a}-1>\frac{\log n}{4\log B}>\unicode[STIX]{x1D717}^{k}\geqslant \unicode[STIX]{x1D717}^{s}\end{eqnarray}$$

(because $n>B^{4}$ ) and a similar inequality holds for $\ell _{1}$ . Write

$$\begin{eqnarray}n=a^{m_{u}}\unicode[STIX]{x1D6FC}_{a}+\unicode[STIX]{x1D701}_{a}\quad \text{and}\quad n=b^{\ell _{v}}\unicode[STIX]{x1D6FD}_{b}+\unicode[STIX]{x1D701}_{b},\end{eqnarray}$$

with

$$\begin{eqnarray}\displaystyle \unicode[STIX]{x1D6FC}_{a}=a_{1}a^{m_{1}-m_{u}}+\cdots +\unicode[STIX]{x1D6FC}_{a}\quad \text{and}\quad \unicode[STIX]{x1D6FD}_{b}=b_{1}b^{\ell _{1}-\ell _{v}}+\cdots +\unicode[STIX]{x1D6FD}_{b}. & & \displaystyle \nonumber\end{eqnarray}$$

Clearly, $\unicode[STIX]{x1D701}_{a}\in [0,a^{m_{u+1}+1})$ and $\unicode[STIX]{x1D701}_{b}\in [0,b^{\ell _{v+1}+1})$ . If $u=r$ , then $\unicode[STIX]{x1D701}_{a}=0$ . Similarly, if $v=t$ , then $\unicode[STIX]{x1D701}_{b}=0$ . We then have

(2.5) $$\begin{eqnarray}|\unicode[STIX]{x1D6FC}_{a}a^{m_{u}}-\unicode[STIX]{x1D6FD}_{b}b^{\ell _{v}}|\leqslant \max \{\unicode[STIX]{x1D701}_{a},\unicode[STIX]{x1D701}_{b}\}.\end{eqnarray}$$

We show that the left-hand side of (2.5) is non-zero. In order to do so, recall that

$$\begin{eqnarray}m_{1}-m_{u}\leqslant \unicode[STIX]{x1D717}^{s-1}<\unicode[STIX]{x1D717}^{k}<\frac{\log n}{4\log B},\end{eqnarray}$$

so

$$\begin{eqnarray}\displaystyle m_{u} & = & \displaystyle m_{1}-(m_{1}-m_{u})>\biggl\lfloor\frac{\log n}{\log a}\biggr\rfloor-\frac{\log n}{4\log B}\nonumber\\ \displaystyle & {\geqslant} & \displaystyle \frac{\log n}{\log a}-1-\frac{\log n}{4\log B}\geqslant \frac{3\log n}{4\log a}-1>\frac{\log n}{2\log a},\nonumber\end{eqnarray}$$

provided $n>B^{4}$ . In particular, $a^{m_{u}}>\sqrt{n}$ . A similar argument shows that $b^{\ell _{v}}>\sqrt{n}$ . Since $a$ and $b$ are coprime, it follows that if the left-hand side of (2.5) is zero, then $a^{m_{u}}\unicode[STIX]{x1D6FC}_{a}=b^{\ell _{v}}\unicode[STIX]{x1D6FD}_{b}$ , so $a^{m_{u}}\mid \unicode[STIX]{x1D6FD}_{b}$ and $b^{\ell _{v}}\mid \unicode[STIX]{x1D6FC}_{a}$ . In particular, both $\unicode[STIX]{x1D6FC}_{a}$ and $a^{m_{u}}$ exceed $\sqrt{n}$ , so

$$\begin{eqnarray}n=a^{m_{u}}\unicode[STIX]{x1D6FC}_{a}+\unicode[STIX]{x1D701}_{a}\geqslant a^{m_{u}}\unicode[STIX]{x1D6FC}_{a}>\sqrt{n}\cdot \sqrt{n}=n,\end{eqnarray}$$

a contradiction. Since the left-hand side of (2.5) is non-zero, the right-hand side of it is non-zero also. In particular, at least one of the inequalities $u<r$ or $v<t$ holds and

(2.6) $$\begin{eqnarray}|\unicode[STIX]{x1D6FC}_{a}a^{m_{u}}-\unicode[STIX]{x1D6FD}_{b}b^{\ell _{v}}|\leqslant \max \{\unicode[STIX]{x1D701}_{a},\unicode[STIX]{x1D701}_{b}\}<\max \{a^{m_{u+1}+1},b^{\ell _{v+1}+1}\}\end{eqnarray}$$

(with the convention that in the maximum the term which is not defined is simply omitted). Assuming that the maximum on the right-hand side of (2.6) is $b^{\ell _{v+1}+1}$ , and putting $(U,V)=(\unicode[STIX]{x1D6FC}_{a},\unicode[STIX]{x1D6FD}_{b})$ , we divide both sides of (2.6) by $Vb^{\ell _{v}}$ , getting

(2.7) $$\begin{eqnarray}|(U/V)a^{m_{u}}b^{-\ell _{v}}-1|<\frac{b^{\ell _{v+1}+1}}{b^{\ell _{v}}\unicode[STIX]{x1D6FD}_{b}}\leqslant \frac{1}{b^{\ell _{v}-\ell _{v+1}-1}}.\end{eqnarray}$$

A similar inequality holds when the maximum on the right-hand side of (2.6) is $a^{m_{u+1}+1}$ , namely

(2.8) $$\begin{eqnarray}|(V/U)a^{-m_{u}}b^{\ell _{v}}-1|<\frac{1}{a^{m_{1}-m_{u+1}-1}}.\end{eqnarray}$$

So, we are all set to apply Lemma 2.1 to find a lower bound on the left-hand side of (2.7) or (2.8).

We take

$$\begin{eqnarray}l=3,\qquad \unicode[STIX]{x1D6FC}_{1}=U/V,\qquad \unicode[STIX]{x1D6FC}_{2}=a,\qquad \unicode[STIX]{x1D6FC}_{3}=b\end{eqnarray}$$

and

$$\begin{eqnarray}(d_{1},d_{2},d_{3})=\unicode[STIX]{x1D700}(1,m_{u},-l_{v}),\end{eqnarray}$$

where $\unicode[STIX]{x1D700}\in \{\pm 1\}$ . More precisely, we set:

• ∙ $\unicode[STIX]{x1D700}=1$ if in (2.6) we have $\max \{a^{m_{u+1}+1},b^{\ell _{v+1}+1}\}=b^{\ell _{v+1}+1}$ , and thus (2.7) holds;

• ∙ $\unicode[STIX]{x1D700}=-1$ if in (2.6) we have $\max \{a^{m_{u+1}+1},b^{\ell _{v+1}+1}\}=a^{m_{u+1}+1}$ , and thus (2.8) holds.

As $a$ and $b$ are multiplicatively independent, these events are clearly mutually exclusive.

Obviously, we have

$$\begin{eqnarray}\max \{m_{u},\ell _{v}\}=\max \biggl\{\biggl\lfloor\frac{\log n}{\log a}\biggr\rfloor,\biggl\lfloor\frac{\log n}{\log b}\biggr\rfloor\biggr\}\leqslant \frac{\log n}{\log 2}<2\log n,\end{eqnarray}$$

so we can take $D=2\log n$ . Furthermore, $A_{2}=\log a$ and $A_{3}=\log b$ . As for $A_{1}$ , we have

$$\begin{eqnarray}\displaystyle h(\unicode[STIX]{x1D6FC}_{1}) & {\leqslant} & \displaystyle \max \{\log \unicode[STIX]{x1D6FC}_{a},\log \unicode[STIX]{x1D6FD}_{b}\}\leqslant \max \{\log (a^{m_{1}-m_{u}+1}),\log (b^{\ell _{1}-\ell _{v}+1})\}\nonumber\\ \displaystyle & {\leqslant} & \displaystyle \max \{m_{1}-m_{u}+1,\ell _{1}-\ell _{v}+1\}\log B\leqslant (\unicode[STIX]{x1D717}^{s-1}+1)\log B\nonumber\\ \displaystyle & {\leqslant} & \displaystyle 2\unicode[STIX]{x1D717}^{s-1}\log B,\nonumber\end{eqnarray}$$

so we take $A_{1}=2\unicode[STIX]{x1D717}^{s-1}\log B$ . Now Lemma 2.1 combined with inequalities (2.7) or (2.8) tells us that

$$\begin{eqnarray}\displaystyle & & \displaystyle -1.4\times 30^{6}\times 3^{4.5}(1+\log (2\log n))2\unicode[STIX]{x1D717}^{s-1}\log a\log b\log B\nonumber\\ \displaystyle & & \displaystyle \quad <-\min \{\log (a^{m_{1}-m_{u+1}-1}),\log (b^{\ell _{1}-\ell _{v+1}-1})\}.\nonumber\end{eqnarray}$$

Assuming that $n>230$ (so that $2\log _{2}n>1+\log (2\log n)$ ), we derive

$$\begin{eqnarray}\displaystyle & & \displaystyle \min \{(m_{1}-m_{u+1}-1)\log a,(\ell _{1}-\ell _{v}-1)\log b\}\nonumber\\ \displaystyle & & \displaystyle \quad <6\cdot 10^{11}\unicode[STIX]{x1D717}^{s-1}(\log a)(\log b)(\log B)(\log _{2}n).\nonumber\end{eqnarray}$$

Since

$$\begin{eqnarray}\min \{m_{1}-m_{u+1}-1,\ell _{1}-\ell _{v+1}-1\}\geqslant \unicode[STIX]{x1D717}^{s}-1>\frac{\unicode[STIX]{x1D717}^{s}}{2}\end{eqnarray}$$

for $s\geqslant 1$ (by inequality (2.4)), we see that

$$\begin{eqnarray}\frac{\unicode[STIX]{x1D717}^{s}}{2}<6\cdot 10^{11}\unicode[STIX]{x1D717}^{s-1}(\log B)^{2}\log _{2}n,\end{eqnarray}$$

giving

$$\begin{eqnarray}\unicode[STIX]{x1D717}<12\cdot 10^{11}(\log B)^{2}\log _{2}n,\end{eqnarray}$$

which is false if we choose $c_{0}=2\cdot 10^{12}(\log B)^{2}$ . The starting value for $n$ , such that $k\geqslant 1$ , remains to be proved. That is,

$$\begin{eqnarray}\unicode[STIX]{x1D717}<\frac{\log n}{4\log B}.\end{eqnarray}$$

This is equivalent to

(2.9) $$\begin{eqnarray}\frac{\log n}{\log _{2}n}>4c_{0}\log B.\end{eqnarray}$$

Note that $4c_{0}\log B=8\cdot 10^{12}(\log B)^{3}$ . The inequality

$$\begin{eqnarray}\frac{x}{\log x}>A\end{eqnarray}$$

is fulfilled when $x>2A\log A$ provided $A>e$ . We now take $A=10^{13}(\log B)^{3}$ and we see that (2.9) holds, provided that

$$\begin{eqnarray}\log n>2\cdot 10^{13}(\log B)^{3}(13\log 10+3\log _{2}B).\end{eqnarray}$$

Since $\log _{2}B<\log B$ , $B\geqslant 3$ and $13\log 10+3<33$ , it follows that the desired inequality holds for $\log n>10^{15}(\log B)^{4}$ . Thus, indeed each interval $\unicode[STIX]{x1D6E9}_{s}$ for $s=1,\ldots ,k$ contains one of $m_{1}-m_{i}$ , or $\ell _{1}-\ell _{j}$ for $i=1,\ldots ,r$ , or $j=1,\ldots ,t$ . Hence, $r-1+s-1\geqslant k$ . Therefore,

$$\begin{eqnarray}\displaystyle s_{a}(n)+s_{b}(n) & {\geqslant} & \displaystyle r+s\geqslant k+2=(k+1)+1\nonumber\\ \displaystyle & {>} & \displaystyle \frac{\log ((\log n)/(4\log B))}{\log \unicode[STIX]{x1D717}}+1\nonumber\\ \displaystyle & = & \displaystyle \frac{\log _{2}n+(\log \unicode[STIX]{x1D717}-\log (4\log B))}{\log _{3}n+\log c_{0}}.\nonumber\end{eqnarray}$$

Clearly, $\unicode[STIX]{x1D717}>4\log B$ . Thus, the inequality

$$\begin{eqnarray}s_{a}(n)+s_{b}(n)>\frac{\log _{2}n}{\log _{3}n+C}\end{eqnarray}$$

holds with $C=\log (2\cdot 10^{12}(\log B)^{2})$ , which concludes the proof.◻

2.2 The proof of Theorem 1.3

Let $\unicode[STIX]{x1D700}>0$ be arbitrary. We consider the primes $p\leqslant B$ with $B=\log _{2}n$ . Then, as $n\rightarrow \infty$ , we have

$$\begin{eqnarray}C=\log (2\cdot 10^{12}(\log B)^{2})=2\log _{4}n+O(1).\end{eqnarray}$$

Further, we need to check that $n>\exp (10^{15}(\log B)^{4})$ . This is equivalent to $\log n>10^{15}(\log _{3}n)^{4}$ , which holds for all $n>\exp (10^{18})$ . Thus, assuming $n$ is this large, for any two distinct primes $p,q\leqslant B$ , it follows by inequality (2.1) that, as $n\rightarrow \infty$ ,

$$\begin{eqnarray}s_{p}(n)+s_{q}(n)>(1+o(1))\frac{\log _{2}n}{\log _{3}n}\end{eqnarray}$$

holds uniformly for primes $p,q$ in the interval $[2,B]$ . If, in particular, we take $P=(1/2-\unicode[STIX]{x1D700})\log _{2}n/\text{log}_{3}\,n$ , then it follows that for every $n>n_{\unicode[STIX]{x1D700}}$ , there is at most one prime $q\leqslant \log _{2}n$ such that

$$\begin{eqnarray}s_{q}(n)<P.\end{eqnarray}$$

For all other primes $p\leqslant \log _{2}n$ , we then have $s_{p}(n)\geqslant P$ . So, if, in addition, we also have $p<P$ , then $s_{p}(n)\geqslant P>p$ , so $p\mid \mathfrak{P}_{n}$ . Thus, indeed, for all $\unicode[STIX]{x1D700}>0$ , there exists $n_{\unicode[STIX]{x1D700}}$ such that if $n>n_{\unicode[STIX]{x1D700}}$ , then all primes $p<(1/2-\unicode[STIX]{x1D700})\log _{2}n/\text{log}_{3}\,n$ divide $\mathfrak{P}_{n}$ with at most one exception.

3.1 Fractional parts of reciprocals of primes

In what follows, for a real number $x$ we write $\lfloor x\rfloor$ and $\{x\}$ for its integer and fractional parts, respectively. We now use the following result from [Reference Baker and Harman2, Proposition 2].

Lemma 3.1. For all $v$ and $w$ that satisfy

$$\begin{eqnarray}v^{37/20}\leqslant w\leqslant v^{2},\end{eqnarray}$$

and are sufficiently large, we have

$$\begin{eqnarray}\#\biggl\{p:2v<p<3v,\biggl\{\frac{w}{p}\biggr\}\geqslant 1-\frac{w}{16v^{2}}\biggr\}\gg \frac{w}{v\log w}.\end{eqnarray}$$

3.2 Concluding the proof

We now derive one of our main technical results.

Lemma 3.2. For all $n$ and $v$ that satisfy

$$\begin{eqnarray}v^{37/20}\leqslant n\leqslant v^{2},\end{eqnarray}$$

and are sufficiently large, we have

$$\begin{eqnarray}\#\{p:2v<p<3v,p\mid \mathfrak{P}_{n}^{+}\}\gg \frac{n}{v\log n}.\end{eqnarray}$$

Proof. Let $p$ be a prime counted in Lemma 3.1 taken with $w=n$ , that is,

$$\begin{eqnarray}1>\biggl\{\frac{n}{p}\biggr\}\geqslant 1-\frac{n}{16v^{2}}.\end{eqnarray}$$

Clearly, $p^{2}>4v^{2}>n$ . Thus, writing $n$ in base $p$ , we have $n=ap+b$ , where

$$\begin{eqnarray}a=\lfloor n/p\rfloor \geqslant n/p-1,\end{eqnarray}$$

and

$$\begin{eqnarray}b=p\biggl\{\frac{n}{p}\biggr\}\geqslant p-\frac{np}{16v^{2}}.\end{eqnarray}$$

Thus,

$$\begin{eqnarray}\displaystyle s_{p}(n) & = & \displaystyle a+b\geqslant p+\frac{n}{p}-\frac{np}{16v^{2}}-1\nonumber\\ \displaystyle & = & \displaystyle p+\frac{n}{p}\bigg(1-\frac{p^{2}}{16v^{2}}\bigg)-1>p+\frac{n}{p}\bigg(1-\frac{9}{16}\bigg)-1\nonumber\\ \displaystyle & = & \displaystyle p+\frac{7n}{16p}-1>p,\nonumber\end{eqnarray}$$

assuming $p$ (and hence, $n$ ) is sufficiently large.◻

We now use Lemma 3.2 with $v=n^{20/37}$ and obtain the lower bound claimed for $P(\mathfrak{P}_{n}^{+})$ .

4.1 Preliminary comments

The proofs of both Theorems 1.5 and 1.7 may be unified in only one proof by making use of the number $\unicode[STIX]{x1D705}\in \{0,1\}$ . We also use the functions $\mathbf{e}(x)=\exp (2\unicode[STIX]{x1D70B}ix)$ and $\unicode[STIX]{x1D713}(x)=x-\lfloor x\rfloor -\frac{1}{2}$ .

4.2 Tools

We start with the following simple result.

Lemma 4.1. Let $\unicode[STIX]{x1D705}\in \{0,1\}$ . For any real numbers $\unicode[STIX]{x1D700}>0$ , $x\geqslant 2$ and $1\leqslant x^{\unicode[STIX]{x1D700}}\leqslant y\leqslant z<x$

$$\begin{eqnarray}\mathop{\sum }_{z<p\leqslant x}\bigg(\biggl\lfloor\frac{x+y}{p}\biggr\rfloor-\biggl\lfloor\frac{x}{p}\biggr\rfloor\bigg)(\log p)^{\unicode[STIX]{x1D705}}<2\unicode[STIX]{x1D700}^{-1}(y+1)(\log x)^{\unicode[STIX]{x1D705}}.\end{eqnarray}$$

Proof. As $\log p\leqslant \log x$ for $p\leqslant x$ it suffices to show that the inequality holds if $\unicode[STIX]{x1D705}=0$ . We write

$$\begin{eqnarray}\mathop{\sum }_{z<p\leqslant x}\bigg(\biggl\lfloor\frac{x+y}{p}\biggr\rfloor-\biggl\lfloor\frac{x}{p}\biggr\rfloor\bigg)=\mathop{\sum }_{z<p\leqslant x}\mathop{\sum }_{x/p<m\leqslant (x+y)/p}1.\end{eqnarray}$$

Collecting together products $k=mp\in (x,x+y]$ and changing the order of summation we obtain

$$\begin{eqnarray}\mathop{\sum }_{z<p\leqslant x}\bigg(\biggl\lfloor\frac{x+y}{p}\biggr\rfloor-\biggl\lfloor\frac{x}{p}\biggr\rfloor\bigg)=\mathop{\sum }_{x<k\leqslant x+y}\mathop{\sum }_{\substack{ p\mid k \\ z<p\leqslant x}}1\leqslant \mathop{\sum }_{x<k\leqslant x+y}\frac{\log k}{\log z}.\end{eqnarray}$$

Since for $k\in (x,x+y]$ we have

$$\begin{eqnarray}\frac{\log k}{\log z}\leqslant \frac{\log (x+y)}{\log z}\leqslant \frac{\log (2x)}{\log y}\leqslant 2\unicode[STIX]{x1D700}^{-1},\end{eqnarray}$$

the result now follows. ◻

Corollary 4.2. Let $\unicode[STIX]{x1D705}\in \{0,1\}$ and $\unicode[STIX]{x1D6FC}\in (n^{-7/16},1)$ . Then

$$\begin{eqnarray}\mathop{\sum }_{\unicode[STIX]{x1D6FC}^{-1}\sqrt{n}<p\leqslant n}\bigg(\biggl\lfloor\frac{n}{p}+\frac{n-p}{p(p-1)}\biggr\rfloor-\biggl\lfloor\frac{n}{p}\biggr\rfloor\bigg)(\log p)^{\unicode[STIX]{x1D705}}\ll \unicode[STIX]{x1D6FC}\sqrt{n}(\log n)^{\unicode[STIX]{x1D705}}.\end{eqnarray}$$

Proof. Since $(n-p)/(p-1)=(n-1)/(p-1)-1$ is a decreasing function of $p\geqslant 2$ , if $p>\unicode[STIX]{x1D6FC}^{-1}\sqrt{n}$ , then

$$\begin{eqnarray}\unicode[STIX]{x1D6FC}\sqrt{n}-\frac{n-p}{p-1}>\unicode[STIX]{x1D6FC}\sqrt{n}-\frac{n-\unicode[STIX]{x1D6FC}^{-1}\sqrt{n}}{\unicode[STIX]{x1D6FC}^{-1}\sqrt{n}-1}=\frac{\sqrt{n}(1+\unicode[STIX]{x1D6FC})(1-\unicode[STIX]{x1D6FC})}{\sqrt{n}-\unicode[STIX]{x1D6FC}}>0.\end{eqnarray}$$

Consequently,

$$\begin{eqnarray}\displaystyle & & \displaystyle \mathop{\sum }_{\unicode[STIX]{x1D6FC}^{-1}\sqrt{n}<p\leqslant n}\bigg(\biggl\lfloor\frac{n}{p}+\frac{n-p}{p(p-1)}\biggr\rfloor-\biggl\lfloor\frac{n}{p}\biggr\rfloor\bigg)(\log p)^{\unicode[STIX]{x1D705}}\nonumber\\ \displaystyle & & \displaystyle \quad \leqslant \mathop{\sum }_{\unicode[STIX]{x1D6FC}^{-1}\sqrt{n}<p\leqslant n}\bigg(\biggl\lfloor\frac{n+\unicode[STIX]{x1D6FC}\sqrt{n}}{p}\biggr\rfloor-\biggl\lfloor\frac{n}{p}\biggr\rfloor\bigg)(\log p)^{\unicode[STIX]{x1D705}},\nonumber\end{eqnarray}$$

and the proof is achieved on invoking Lemma 4.1 with $x=n$ , $y=\unicode[STIX]{x1D6FC}\sqrt{n}$ , $z=\unicode[STIX]{x1D6FC}^{-1}\sqrt{n}$ and $\unicode[STIX]{x1D700}=1/16$ .◻

Lemma 4.3. Let $\unicode[STIX]{x1D705}\in \{0,1\}$ and let $M$ be a positive integer. For any real valued function $g:\mathbb{Z}\rightarrow \mathbb{R}$ and any positive integer $H$ we have

$$\begin{eqnarray}\displaystyle & & \displaystyle \biggl|\mathop{\sum }_{M<p\leqslant 2M}(\log p)^{\unicode[STIX]{x1D705}}\unicode[STIX]{x1D713}\bigg(\frac{n}{p}+g(p)\bigg)\biggr|\nonumber\\ \displaystyle & & \displaystyle \quad \ll \frac{M}{H(\log M)^{1-\unicode[STIX]{x1D705}}}+\mathop{\sum }_{h\leqslant H}\frac{1}{h}\biggl|\mathop{\sum }_{M<p\leqslant 2M}(\log p)^{\unicode[STIX]{x1D705}}\mathbf{e}\bigg(\frac{nh}{p}\bigg)\mathbf{e}(hg(p))\biggr|.\nonumber\end{eqnarray}$$

Proof. For any $0<|t|<1$ we put $\unicode[STIX]{x1D6F7}(t)=\unicode[STIX]{x1D70B}t(1-|t|)\cot (\unicode[STIX]{x1D70B}t)+|t|$ . Note that $0<\unicode[STIX]{x1D6F7}(t)<1$ for $0<|t|<1$ .

We follow the proof of [Reference Bordellès4, Corollary 6.2]. It follows from the result of Vaaler [Reference Vaaler20], which we use in the form given by [Reference Bordellès4, Theorem 6.1], that for any real number $x\geqslant 1$ and any positive integer $H$ ,

(4.1) $$\begin{eqnarray}\unicode[STIX]{x1D713}(x)=-\mathop{\sum }_{0<|h|\leqslant H}\unicode[STIX]{x1D6F7}\biggl(\frac{h}{H+1}\biggr)\frac{\mathbf{e}(hx)}{2\unicode[STIX]{x1D70B}ih}+{\mathcal{R}}_{H}(x),\end{eqnarray}$$

where the error term ${\mathcal{R}}_{H}(x)$ satisfies

(4.2) $$\begin{eqnarray}|{\mathcal{R}}_{H}(x)|\leqslant \frac{1}{2H+2}\mathop{\sum }_{|h|\leqslant H}\biggl(1-\frac{|h|}{H+1}\biggr)\mathbf{e}(hx).\end{eqnarray}$$

The right-hand side of (4.2) does not appear to be, but is in fact a non-zero real number since it can be shown, cf. [Reference Bordellès4, Exercise 3, p. 350], that

$$\begin{eqnarray}\mathop{\sum }_{|h|\leqslant H}\bigg(1-\frac{|h|}{H+1}\bigg)\mathbf{e}(hx)=\frac{1}{H+1}\biggl|\mathop{\sum }_{h=0}^{H}\mathbf{e}(hx)\biggr|^{2}.\end{eqnarray}$$

Using (4.1) with $x=n/p+g(p)$ , multiplying by $(\log p)^{\unicode[STIX]{x1D705}}$ and summing over all the primes $p$ in $(M,2M]$ yields the estimate

$$\begin{eqnarray}\mathop{\sum }_{M<p\leqslant 2M}(\log p)^{\unicode[STIX]{x1D705}}\unicode[STIX]{x1D713}\biggl(\frac{n}{p}+g(p)\biggr)=\unicode[STIX]{x1D6F4}_{1}+\unicode[STIX]{x1D6F4}_{2},\end{eqnarray}$$

where

$$\begin{eqnarray}\displaystyle \unicode[STIX]{x1D6F4}_{1} & = & \displaystyle -\mathop{\sum }_{0<|h|\leqslant H}\unicode[STIX]{x1D6F7}\biggl(\frac{h}{H+1}\biggr)\frac{1}{2\unicode[STIX]{x1D70B}ih}\mathop{\sum }_{M<p\leqslant 2M}(\log p)^{\unicode[STIX]{x1D705}}\mathbf{e}\bigg(\frac{nh}{p}+hg(p)\bigg),\nonumber\\ \displaystyle \unicode[STIX]{x1D6F4}_{2} & = & \displaystyle \mathop{\sum }_{M<p\leqslant 2M}(\log p)^{\unicode[STIX]{x1D705}}{\mathcal{R}}_{H}\bigg(\frac{n}{p}+g(p)\bigg).\nonumber\end{eqnarray}$$

Now

$$\begin{eqnarray}\displaystyle |\unicode[STIX]{x1D6F4}_{1}| & {\leqslant} & \displaystyle \mathop{\sum }_{0<|h|\leqslant H}\frac{1}{2\unicode[STIX]{x1D70B}|h|}\biggl|\mathop{\sum }_{M<p\leqslant 2M}(\log p)^{\unicode[STIX]{x1D705}}e\biggl(\frac{nh}{p}+hg(p)\biggr)\biggr|\nonumber\\ \displaystyle & = & \displaystyle \frac{1}{\unicode[STIX]{x1D70B}}\mathop{\sum }_{h\leqslant H}\frac{1}{h}\biggl|\mathop{\sum }_{M<p\leqslant 2M}(\log p)^{\unicode[STIX]{x1D705}}\mathbf{e}\bigg(\frac{nh}{p}\bigg)e(hg(p))\biggr|,\nonumber\end{eqnarray}$$

and by (4.2) we have

$$\begin{eqnarray}\displaystyle |\unicode[STIX]{x1D6F4}_{2}| & {\leqslant} & \displaystyle \mathop{\sum }_{M<p\leqslant 2M}(\log p)^{\unicode[STIX]{x1D705}}\biggl|{\mathcal{R}}_{H}\biggl(\frac{n}{p}+g(p)\biggr)\biggr|\nonumber\\ \displaystyle & {\leqslant} & \displaystyle \frac{1}{2H+2}\mathop{\sum }_{|h|\leqslant H}\biggl(1-\frac{|h|}{H+1}\biggr)\mathop{\sum }_{M<p\leqslant 2M}(\log p)^{\unicode[STIX]{x1D705}}e\biggl(\frac{nh}{p}+hg(p)\biggr)\nonumber\\ \displaystyle & = & \displaystyle \frac{1}{2H+2}\mathop{\sum }_{M<p\leqslant 2M}(\log p)^{\unicode[STIX]{x1D705}}+\frac{1}{H+1}\mathop{\sum }_{h\leqslant H}\biggl(1-\frac{h}{H+1}\biggr)\nonumber\\ \displaystyle & & \displaystyle \times \,\operatorname{Re}\biggl(\mathop{\sum }_{M<p\leqslant 2M}(\log p)^{\unicode[STIX]{x1D705}}\mathbf{e}\bigg(\frac{nh}{p}+hg(p)\bigg)\biggr)\nonumber\\ \displaystyle & {\leqslant} & \displaystyle \frac{1}{2H+2}\mathop{\sum }_{M<p\leqslant 2M}(\log p)^{\unicode[STIX]{x1D705}}\nonumber\\ \displaystyle & & \displaystyle +\,\mathop{\sum }_{h\leqslant H}\frac{1}{h}\biggl|\mathop{\sum }_{M<p\leqslant 2M}(\log p)^{\unicode[STIX]{x1D705}}\mathbf{e}\bigg(\frac{nh}{p}\bigg)\mathbf{e}(hg(p))\biggr|,\nonumber\end{eqnarray}$$

where in the third line the cases $h=0$ and $|h|>0$ are separated, concluding the proof.◻

Recall that the von Mangoldt function is defined by

$$\begin{eqnarray}\unicode[STIX]{x1D6EC}(m)=\left\{\begin{array}{@{}ll@{}}\log p\quad & \text{if }m\text{ is a power of a prime }p,\\ 0\quad & \text{otherwise.}\end{array}\right.\end{eqnarray}$$

Lemma 4.4. Let $\unicode[STIX]{x1D705}\in \{0,1\}$ and let $n\geqslant 5$ and $2\leqslant M<n/2$ be positive integers. Let $g:\mathbb{Z}\rightarrow \mathbb{R}$ be a real valued function such that either

$$\begin{eqnarray}g(p)=0\end{eqnarray}$$

for all primes $p$ or

$$\begin{eqnarray}g(p)=\frac{n-p}{p(p-1)}\end{eqnarray}$$

for all primes $p$ . Then for any positive integer $H$ we have

$$\begin{eqnarray}\displaystyle & & \displaystyle \biggl|\mathop{\sum }_{M<p\leqslant 2M}(\log p)^{\unicode[STIX]{x1D705}}\unicode[STIX]{x1D713}\bigg(\frac{n}{p}+g(p)\bigg)\biggr|\nonumber\\ \displaystyle & & \displaystyle \quad \ll \frac{1}{(\log M)^{1-\unicode[STIX]{x1D705}}}\mathop{\sum }_{h\leqslant H}\frac{1}{h}\bigg(1+\frac{nh}{M^{2}}\bigg)\max _{M<N\leqslant 2M}\biggl|\mathop{\sum }_{M<m\leqslant N}\unicode[STIX]{x1D6EC}(m)\mathbf{e}\bigg(\frac{hn}{m}\bigg)\biggr|\nonumber\\ \displaystyle & & \displaystyle \qquad +\,\frac{M}{H(\log M)^{1-\unicode[STIX]{x1D705}}}+\frac{nH}{M^{3/2}(\log M)^{1-\unicode[STIX]{x1D705}}}+\frac{M^{1/2}\log H}{(\log M)^{1-\unicode[STIX]{x1D705}}}.\nonumber\end{eqnarray}$$

Proof. From Lemma 4.3,

$$\begin{eqnarray}\displaystyle & & \displaystyle \biggl|\mathop{\sum }_{M<p\leqslant 2M}(\log p)^{\unicode[STIX]{x1D705}}\unicode[STIX]{x1D713}\bigg(\frac{n}{p}+g(p)\bigg)\biggr|\nonumber\\ \displaystyle & & \displaystyle \quad \ll \frac{M}{H(\log M)^{1-\unicode[STIX]{x1D705}}}+\mathop{\sum }_{h\leqslant H}\frac{1}{h}\biggl|\mathop{\sum }_{M<p\leqslant 2M}(\log p)^{\unicode[STIX]{x1D705}}\mathbf{e}\bigg(\frac{nh}{p}\bigg)\mathbf{e}(hg(p))\biggr|.\nonumber\end{eqnarray}$$

The total variation of the sequence $(hg(k))_{k}$ in $(M,2M]$ is

$$\begin{eqnarray}\displaystyle \mathop{\sum }_{M<k\leqslant 2M}|hg(k+1)-hg(k)| & = & \displaystyle h\mathop{\sum }_{M<k\leqslant 2M}\frac{2n-(k+1)}{k(k^{2}-1)}\nonumber\\ \displaystyle & {\leqslant} & \displaystyle 2nh\mathop{\sum }_{M<k\leqslant 2M}\frac{1}{k(k^{2}-1)}\ll \frac{nh}{M^{2}},\nonumber\end{eqnarray}$$

so that by Abel summation and the inequality $|\mathbf{e}(u)-\mathbf{e}(v)|\ll |u-v|$ for any $u,v\in \mathbb{R}$ , we obtain

$$\begin{eqnarray}\displaystyle & & \displaystyle \biggl|\mathop{\sum }_{M<p\leqslant 2M}(\log p)^{\unicode[STIX]{x1D705}}\mathbf{e}\bigg(\frac{nh}{p}\bigg)\mathbf{e}(hg(p))\biggr|\nonumber\\ \displaystyle & & \displaystyle \quad \ll \bigg(1+\frac{nh}{M^{2}}\bigg)\max _{M<N\leqslant 2M}\biggl|\mathop{\sum }_{M<p\leqslant N}(\log p)^{\unicode[STIX]{x1D705}}\mathbf{e}\bigg(\frac{nh}{p}\bigg)\biggr|,\nonumber\end{eqnarray}$$

and by Abel summation again

$$\begin{eqnarray}\displaystyle & & \displaystyle \biggl|\mathop{\sum }_{M<p\leqslant N}(\log p)^{\unicode[STIX]{x1D705}}\mathbf{e}\bigg(\frac{nh}{p}\bigg)\biggr|\nonumber\\ \displaystyle & & \displaystyle \quad \leqslant \frac{2}{(\log M)^{1-\unicode[STIX]{x1D705}}}\underset{M<L\leqslant N}{\max }\biggl|\mathop{\sum }_{M\leqslant p\leqslant L}(\log p)\mathbf{e}\bigg(\frac{nh}{p}\bigg)\biggr|\nonumber\\ \displaystyle & & \displaystyle \quad \ll \frac{1}{(\log M)^{1-\unicode[STIX]{x1D705}}}\bigg(\underset{M<L\leqslant N}{\max }\biggl|\mathop{\sum }_{M\leqslant m\leqslant L}\unicode[STIX]{x1D6EC}(m)\mathbf{e}\bigg(\frac{nh}{m}\bigg)\biggr|+N^{1/2}\bigg).\nonumber\end{eqnarray}$$

Putting everything together gives the asserted estimate. ◻

We also recall that using [Reference Granville and Ramaré8, Theorem 9] with $k=2$ we obtain the following.

Lemma 4.5. If $M\leqslant \frac{1}{5}\,x^{3/5}$ , then, for any $N\in (M,2M]$

$$\begin{eqnarray}\biggl|\mathop{\sum }_{M<m\leqslant N}\unicode[STIX]{x1D6EC}(m)\mathbf{e}\bigg(\frac{x}{m}\bigg)\biggr|<17(x^{2}M^{19})^{1/24}(\log 16M)^{11/4}.\end{eqnarray}$$

Lemma 4.6. Let $\unicode[STIX]{x1D705}\in \{0,1\}$ . There exists some absolute constant $c>0$ such that, for any large real number $t>1$ , we have

$$\begin{eqnarray}\mathop{\sum }_{p>t}\frac{(\log p)^{\unicode[STIX]{x1D705}}}{p(p-1)}=F_{\unicode[STIX]{x1D705}}(t)+O(t^{-1}\unicode[STIX]{x1D6FF}_{c}(t)),\end{eqnarray}$$

where $F_{0}(t)=\text{E}_{1}(\log t)$ and $F_{1}(t)=t^{-1}$ .

Proof. The Prime Number Theorem in the version of Korobov and Vinogradov (see [Reference Ivić10, Theorem 12.2 and equation (12.27)] or [Reference Iwaniec and Kowalski11, Corollary 8.30], for instance) states that

$$\begin{eqnarray}\unicode[STIX]{x1D70B}(u)=\operatorname{li}(u)+O(u\unicode[STIX]{x1D6FF}_{c_{0}}(u)),\end{eqnarray}$$

where $\operatorname{li}(u)$ is the logarithmic integral

$$\begin{eqnarray}\operatorname{li}(u)=\int _{2}^{u}\frac{dt}{\log t}\quad (u>0).\end{eqnarray}$$

Using it we then derive by partial summation that

$$\begin{eqnarray}\displaystyle \mathop{\sum }_{p>t}\frac{(\log p)^{\unicode[STIX]{x1D705}}}{p(p-1)} & = & \displaystyle \mathop{\sum }_{p>t}\frac{(\log p)^{\unicode[STIX]{x1D705}}}{p^{2}}+\mathop{\sum }_{p>t}\frac{(\log p)^{\unicode[STIX]{x1D705}}}{p^{2}(p-1)}\nonumber\\ \displaystyle & = & \displaystyle -\frac{\unicode[STIX]{x1D70B}(t)(\log t)^{\unicode[STIX]{x1D705}}}{t^{2}}+\int _{t}^{\infty }\frac{\unicode[STIX]{x1D70B}(u)(2(\log u)^{\unicode[STIX]{x1D705}}-\unicode[STIX]{x1D705}(\log u)^{\unicode[STIX]{x1D705}-1})}{u^{3}}\,du\nonumber\\ \displaystyle & & \displaystyle +\,O\bigg(\frac{1}{t^{2}(\log t)^{1-\unicode[STIX]{x1D705}}}\bigg)\nonumber\\ \displaystyle & = & \displaystyle -\frac{(\log t)^{\unicode[STIX]{x1D705}}}{t^{2}}(\operatorname{li}(t)+O(t\unicode[STIX]{x1D6FF}_{c_{0}}(t)))\nonumber\\ \displaystyle & & \displaystyle +\,\int _{t}^{\infty }\frac{2(\log u)^{\unicode[STIX]{x1D705}}-\unicode[STIX]{x1D705}(\log u)^{\unicode[STIX]{x1D705}-1}}{u^{3}}(\operatorname{li}(u)+O(u\unicode[STIX]{x1D6FF}_{c_{0}}(u)))\,du\nonumber\\ \displaystyle & & \displaystyle +\,O\bigg(\frac{1}{t^{2}(\log t)^{1-\unicode[STIX]{x1D705}}}\bigg)\nonumber\\ \displaystyle & = & \displaystyle -\frac{\operatorname{li}(t)(\log t)^{\unicode[STIX]{x1D705}}}{t^{2}}+\int _{t}^{\infty }\frac{\operatorname{li}(u)(2(\log u)^{\unicode[STIX]{x1D705}}-\unicode[STIX]{x1D705}(\log u)^{\unicode[STIX]{x1D705}-1})}{u^{3}}\,du\nonumber\\ \displaystyle & & \displaystyle +\,O(t^{-1}(\log t)^{\unicode[STIX]{x1D705}}\unicode[STIX]{x1D6FF}_{c_{0}}(t)).\nonumber\end{eqnarray}$$

Now, integrating by parts we derive

$$\begin{eqnarray}\displaystyle & & \displaystyle -\frac{\operatorname{li}(t)(\log t)^{\unicode[STIX]{x1D705}}}{t^{2}}+\int _{t}^{\infty }\frac{\operatorname{li}(u)(2(\log u)^{\unicode[STIX]{x1D705}}-\unicode[STIX]{x1D705}(\log u)^{\unicode[STIX]{x1D705}-1})}{u^{3}}\,du\nonumber\\ \displaystyle & & \displaystyle \quad =\int _{t}^{\infty }\frac{du}{u^{2}(\log u)^{1-\unicode[STIX]{x1D705}}}=F_{\unicode[STIX]{x1D705}}(t).\nonumber\end{eqnarray}$$

The result follows with any constant $c\in (0,c_{0})$ .◻

4.3 First step

Let $\unicode[STIX]{x1D705}\in \{0,1\}$ and define

$$\begin{eqnarray}\unicode[STIX]{x1D6F4}_{\unicode[STIX]{x1D705}}=\mathop{\sum }_{\sqrt{n}<p\leqslant n}\bigg(\biggl\lfloor\frac{n-1}{p-1}\biggr\rfloor-\biggl\lfloor\frac{n}{p}\biggr\rfloor\bigg)(\log p)^{\unicode[STIX]{x1D705}}.\end{eqnarray}$$

Notice that, if $\sqrt{n}<p\leqslant n$ , then

$$\begin{eqnarray}0\leqslant \frac{n-p}{p-1}<\sqrt{n},\end{eqnarray}$$

and hence

$$\begin{eqnarray}\frac{n-1}{p-1}-\frac{n}{p}=\frac{n-p}{p(p-1)}<\frac{\sqrt{n}}{p}<1,\end{eqnarray}$$

so that

(4.3) $$\begin{eqnarray}\unicode[STIX]{x1D714}(\mathfrak{p}_{n}^{+})=\unicode[STIX]{x1D6F4}_{0}\quad \text{and}\quad \log \mathfrak{p}_{n}^{+}=\unicode[STIX]{x1D6F4}_{1}.\end{eqnarray}$$

We now recall (1.4) and split the sum $\unicode[STIX]{x1D6F4}_{\unicode[STIX]{x1D705}}$ into two subsums as

$$\begin{eqnarray}\unicode[STIX]{x1D6F4}_{\unicode[STIX]{x1D705}}=S_{1}+S_{2},\end{eqnarray}$$

where

$$\begin{eqnarray}\displaystyle S_{1} & = & \displaystyle \mathop{\sum }_{\sqrt{n}<p\leqslant \sqrt{n}\,(\unicode[STIX]{x1D6FF}_{c}(\sqrt{n}))^{-1}}\bigg(\biggl\lfloor\frac{n-1}{p-1}\biggr\rfloor-\biggl\lfloor\frac{n}{p}\biggr\rfloor\bigg)(\log p)^{\unicode[STIX]{x1D705}},\nonumber\\ \displaystyle S_{2} & = & \displaystyle \mathop{\sum }_{\sqrt{n}\,(\unicode[STIX]{x1D6FF}_{c}(\sqrt{n}))^{-1}<p\leqslant n}\bigg(\biggl\lfloor\frac{n-1}{p-1}\biggr\rfloor-\biggl\lfloor\frac{n}{p}\biggr\rfloor\bigg)(\log p)^{\unicode[STIX]{x1D705}},\nonumber\end{eqnarray}$$

and $c>0$ is the constant given in Lemma 4.6.

4.4 The sum $S_{2}$

We use Corollary 4.2 with $\unicode[STIX]{x1D6FC}=\unicode[STIX]{x1D6FF}_{c}(\sqrt{n})$ giving immediately

(4.4) $$\begin{eqnarray}S_{2}\ll \sqrt{n}\,\unicode[STIX]{x1D6FF}_{c}(\sqrt{n})(\log n)^{\unicode[STIX]{x1D705}}\ll \sqrt{n}\,\unicode[STIX]{x1D6FF}_{c_{1}}(\sqrt{n})\end{eqnarray}$$

for any $c_{1}\in (0,c]$ .

4.5 The sum $S_{1}$

Using

$$\begin{eqnarray}\frac{n-1}{p-1}=\frac{n}{p}+\frac{n-p}{p(p-1)},\end{eqnarray}$$

and recalling the definition of the function $\unicode[STIX]{x1D713}(x)$ , we write

$$\begin{eqnarray}S_{1}=S_{11}-S_{12},\end{eqnarray}$$

where

$$\begin{eqnarray}\displaystyle S_{11} & = & \displaystyle \mathop{\sum }_{\sqrt{n}<p\leqslant \sqrt{n}\,(\unicode[STIX]{x1D6FF}_{c}(\sqrt{n}))^{-1}}\frac{(\log p)^{\unicode[STIX]{x1D705}}(n-p)}{p(p-1)},\nonumber\\ \displaystyle S_{12} & = & \displaystyle \mathop{\sum }_{\sqrt{n}<p\leqslant \sqrt{n}\,(\unicode[STIX]{x1D6FF}_{c}(\sqrt{n}))^{-1}}(\log p)^{\unicode[STIX]{x1D705}}\bigg(\unicode[STIX]{x1D713}\bigg(\frac{n}{p}+\frac{n-p}{p(p-1)}\bigg)-\unicode[STIX]{x1D713}\bigg(\frac{n}{p}\bigg)\bigg).\nonumber\end{eqnarray}$$

The main term

For any large integer $n\geqslant 1$ , we derive from Lemma 4.6 that

$$\begin{eqnarray}\displaystyle \mathop{\sum }_{\sqrt{n}<p\leqslant \sqrt{n}(\unicode[STIX]{x1D6FF}_{c}(\sqrt{n}))^{-1}}\frac{(\log p)^{\unicode[STIX]{x1D705}}}{p(p-1)} & = & \displaystyle F_{\unicode[STIX]{x1D705}}(\sqrt{n})-F_{\unicode[STIX]{x1D705}}\bigg(\frac{\sqrt{n}}{\unicode[STIX]{x1D6FF}_{c}(\sqrt{n})}\bigg)\nonumber\\ \displaystyle & & \displaystyle +\,O(n^{-1/2}\unicode[STIX]{x1D6FF}_{c}(\sqrt{n})).\nonumber\end{eqnarray}$$

From [Reference Abramowitz and Stegun1, equation (5.1.19)] we have the inequalities

$$\begin{eqnarray}\frac{\text{e}^{-x}}{x+1}<\text{E}_{1}(x)<\frac{\text{e}^{-x}}{x}\quad (x>0),\end{eqnarray}$$

which imply that

$$\begin{eqnarray}F_{\unicode[STIX]{x1D705}}\bigg(\frac{\sqrt{n}}{\unicode[STIX]{x1D6FF}_{c}(\sqrt{n})}\bigg)\ll n^{-1/2}\unicode[STIX]{x1D6FF}_{c}(\sqrt{n}),\end{eqnarray}$$

so that

$$\begin{eqnarray}\mathop{\sum }_{\sqrt{n}<p\leqslant \sqrt{n}(\unicode[STIX]{x1D6FF}_{c}(\sqrt{n}))^{-1}}\frac{(\log p)^{\unicode[STIX]{x1D705}}}{p(p-1)}=F_{\unicode[STIX]{x1D705}}(\sqrt{n})+O(n^{-1/2}\unicode[STIX]{x1D6FF}_{c}(\sqrt{n})).\end{eqnarray}$$

Therefore,

(4.5) $$\begin{eqnarray}\displaystyle S_{11} & = & \displaystyle n\mathop{\sum }_{\sqrt{n}<p\leqslant \sqrt{n}(\unicode[STIX]{x1D6FF}_{c}(\sqrt{n}))^{-1}}\frac{(\log p)^{\unicode[STIX]{x1D705}}}{p(p-1)}-\mathop{\sum }_{\sqrt{n}<p\leqslant \sqrt{n}(\unicode[STIX]{x1D6FF}_{c}(\sqrt{n}))^{-1}}\frac{(\log p)^{\unicode[STIX]{x1D705}}}{p-1}\nonumber\\ \displaystyle & = & \displaystyle n\mathop{\sum }_{\sqrt{n}<p\leqslant \sqrt{n}(\unicode[STIX]{x1D6FF}_{c}(\sqrt{n}))^{-1}}\frac{(\log p)^{\unicode[STIX]{x1D705}}}{p(p-1)}+O(\log n)\nonumber\\ \displaystyle & = & \displaystyle nF_{\unicode[STIX]{x1D705}}(\sqrt{n})+O(n^{1/2}\unicode[STIX]{x1D6FF}_{c}(\sqrt{n})).\end{eqnarray}$$

The error term

It remains to prove that, for $n$ sufficiently large

(4.6) $$\begin{eqnarray}|S_{12}|\ll n^{1/2}\unicode[STIX]{x1D6FF}_{c}(\sqrt{n}).\end{eqnarray}$$

This estimate follows from the next result which actually gives a power saving.

Lemma 4.7. For $n\geqslant 2$ , we have $S_{12}\ll n^{49/100+o(1)}$ .

Proof. Split the interval $(\sqrt{n},\sqrt{n}\,(\unicode[STIX]{x1D6FF}_{c}(\sqrt{n}))^{-1}]$ into $O(\log n)$ dyadic subintervals of the form $(M,2M]$ , so that

$$\begin{eqnarray}\displaystyle & & \displaystyle \biggl|\mathop{\sum }_{\sqrt{n}<p\leqslant \sqrt{n}\,(\unicode[STIX]{x1D6FF}_{c}(\sqrt{n}))^{-1}}(\log p)^{\unicode[STIX]{x1D705}}\unicode[STIX]{x1D713}\bigg(\frac{n}{p}+g(p)\bigg)\biggr|\nonumber\\ \displaystyle & & \displaystyle \quad \ll \underset{\sqrt{n}<M\leqslant \sqrt{n}\,(\unicode[STIX]{x1D6FF}_{c}(\sqrt{n}))^{-1}}{\max }\biggl|\mathop{\sum }_{M<p\leqslant 2M}(\log p)^{\unicode[STIX]{x1D705}}\unicode[STIX]{x1D713}\bigg(\frac{n}{p}+g(p)\bigg)\biggr|\log n,\nonumber\end{eqnarray}$$

where, as in Lemma 4.4,

$$\begin{eqnarray}g(p)=0\quad \text{or}\quad g(p)=\frac{n-p}{p(p-1)}.\end{eqnarray}$$

From Lemmas 4.4 and 4.5

$$\begin{eqnarray}\displaystyle & & \displaystyle \biggl|\mathop{\sum }_{M<p\leqslant 2M}(\log p)^{\unicode[STIX]{x1D705}}\unicode[STIX]{x1D713}\bigg(\frac{n}{p}+g(p)\bigg)\biggr|\nonumber\\ \displaystyle & & \displaystyle \quad \ll (\log M)^{7/4+\unicode[STIX]{x1D705}}\mathop{\sum }_{h\leqslant H}\frac{1}{h}\bigg(1+\frac{nh}{M^{2}}\bigg)(h^{2}n^{2}M^{19})^{1/24}\nonumber\\ \displaystyle & & \displaystyle \qquad +\,\frac{M}{H(\log M)^{1-\unicode[STIX]{x1D705}}}+\frac{nH}{M^{3/2}(\log M)^{1-\unicode[STIX]{x1D705}}}+\frac{M^{1/2}\log H}{(\log M)^{1-\unicode[STIX]{x1D705}}}\nonumber\\ \displaystyle & & \displaystyle \quad \ll ((n^{26}H^{26}M^{-29})^{1/24}+(n^{2}H^{2}M^{19})^{1/24})(\log M)^{11/4}\nonumber\\ \displaystyle & & \displaystyle \qquad +\,\frac{M}{H(\log M)^{1-\unicode[STIX]{x1D705}}}+\frac{nH}{M^{3/2}}+M^{1/2}\log H.\nonumber\end{eqnarray}$$

Choose

$$\begin{eqnarray}H=\lfloor M^{53/50}n^{-13/25}\rfloor\end{eqnarray}$$

to balance the first and the third terms in the above bound up to logarithmic factors, which we all replace by $n^{o(1)}$ . We also note that since $M\geqslant n^{1/2}$ we have $H\geqslant 1$ provided that $n$ is large enough. Hence,

$$\begin{eqnarray}\displaystyle & & \displaystyle \biggl|\mathop{\sum }_{M<p\leqslant 2M}(\log p)^{\unicode[STIX]{x1D705}}\unicode[STIX]{x1D713}\bigg(\frac{n}{p}+g(p)\bigg)\biggr|\nonumber\\ \displaystyle & & \displaystyle \quad \ll ((n^{26}M^{-3})^{1/50}+(nM^{22})^{1/25}+(n^{12}M^{-11})^{1/25}+M^{1/2})n^{o(1)}\nonumber\end{eqnarray}$$

and so, using that $M=n^{1/2+o(1)}$ , we obtain

$$\begin{eqnarray}|S_{12}|\ll (n^{49/100}+n^{13/50}+n^{1/4})n^{o(1)}\ll n^{49/100+o(1)},\end{eqnarray}$$

whenever $n$ is sufficiently large, concluding the proof.◻

4.6 Completion of the proof of Theorems 1.5 and 1.7

Follows at once from (4.3), (4.4), (4.5) and (4.6).

5.1 Preliminary considerations

Let us fix some prime $p$ and write $n$ in base $p$ as

$$\begin{eqnarray}n=\mathop{\sum }_{i=0}^{k}a_{i}p^{k-i},\end{eqnarray}$$

with $p$ -ary digits

$$\begin{eqnarray}a_{i}\in \{0,\ldots ,p-1\},\quad i=0,\ldots ,k,\;\text{and}\;a_{0}\neq 0.\end{eqnarray}$$

In the above, $k=\lfloor \log n/\text{log}\,p\rfloor +1$ .

We distinguish the following two cases.

Case 1: $a_{k}\neq p-1$

In this case,

$$\begin{eqnarray}n+1=a_{0}p^{k}+\cdots +(a_{k}+1)\end{eqnarray}$$

is the base $p$ -representation of $n+1$ . Hence, $s_{p}(n+1)=s_{p}(n)+1$ . In particular, the following events

(5.1) $$\begin{eqnarray}p\mid \mathfrak{P}_{n+1}\quad \text{and}\quad p\nmid \mathfrak{P}_{n},\end{eqnarray}$$

and thus,

$$\begin{eqnarray}s_{p}(n+1)\geqslant p>s_{p}(n),\end{eqnarray}$$

are simultaneously possible only when

(5.2) $$\begin{eqnarray}s_{p}(n)=p-1.\end{eqnarray}$$

Case 2: $a_{k}=p-1$

Let $i\in [0,k]$ be such that $a_{k}=a_{k-1}=\cdots =a_{k-i}=p-1$ , but $a_{k-i-1}<p-1$ . Then

$$\begin{eqnarray}n+1=a_{0}p^{k}+\cdots +(a_{k-i-1}+1)p^{i},\end{eqnarray}$$

and we obtain

$$\begin{eqnarray}s_{p}(n+1)=a_{0}+\cdots +a_{k-i-1}+1\leqslant a_{0}+\cdots +a_{k-i-1}+a_{k}\leqslant s_{p}(n).\end{eqnarray}$$

Hence, for each $p$ with $a_{k}=p-1$ , it follows that if $p\mid \mathfrak{P}_{n+1}$ , then also $p\mid \mathfrak{P}_{n}$ . However, the opposite to (5.1), that is

(5.3) $$\begin{eqnarray}p\nmid \mathfrak{P}_{n+1}\quad \text{and}\quad p\mid \mathfrak{P}_{n},\end{eqnarray}$$

is also possible in this case. Actually, this case plays an important role in our argument in §5.2 below.

5.2 Proof of (i): divisibility

As we have seen, primes $p$ which belong to Case 2 of §5.1 do not appear in the denominator of the ratio $\mathfrak{P}_{n}/\mathfrak{P}_{n+1}$ . We now show that for almost all $n\leqslant x$ (with an explicit bound on the size of the exceptional set) the primes which belong to Case 1 of §5.1 do not appear in the denominator of this ratio either, and thus, we have the desired divisibility.

More precisely, using the characterization of (5.1) given by (5.2), we conclude that $\mathfrak{P}_{n+1}\mid \mathfrak{P}_{n}$ holds for all positive integers $n$ that have the property that there is no prime $p$ with $s_{p}(n)=p-1$ . It remains to prove that the complementary set has asymptotic density zero.

Thus, we define

$$\begin{eqnarray}{\mathcal{A}}(x)=\{n\leqslant x~:~s_{p}(n)=p-1~\text{for some prime}~p\}.\end{eqnarray}$$

First of all note that since $s_{p}(n)=p-1$ , it follows that $(p-1)\mid n$ . McNew et al [Reference McNew, Pollack and Pomerance17], improving on the previous result of Erdős and Wagstaff [Reference Erdős and Wagstaff6], have shown that uniformly in $3\leqslant y\leqslant x$ , the estimate

(5.4) $$\begin{eqnarray}\#\{n\leqslant x:(p-1)\mid n~\text{for some}~p\geqslant y\}\ll \frac{x}{(\log y)^{\unicode[STIX]{x1D6FF}}(\log _{2}y)^{1/2}},\end{eqnarray}$$

holds, where $\unicode[STIX]{x1D6FF}$ is the Erdős–Ford–Tenenbaum constant defined at (1.3). We also recall that Ford [Reference Ford7] has recently established more precise results, which, however, cannot be used to improve our bounds.

We take $y=(\log x)^{1/2}$ in (5.4), getting that the number of $n\in {\mathcal{A}}(x)$ such that $s_{p}(n)=p-1$ for some $p\geqslant y$ is

(5.5) $$\begin{eqnarray}\frac{x}{(\log y)^{\unicode[STIX]{x1D6FF}}(\log _{2}y)^{1/2}}\ll \frac{x}{(\log _{2}x)^{\unicode[STIX]{x1D6FF}}(\log _{3}x)^{1/2}}.\end{eqnarray}$$

Assume now that $p<y$ . We remark that for each $p$ and

$$\begin{eqnarray}k=\biggl\lfloor\frac{\log n}{\log p}\biggr\rfloor+1,\end{eqnarray}$$

the condition $s_{p}(n)=p-1$ leads to the equation

$$\begin{eqnarray}a_{0}+\cdots +a_{k}=p-1\end{eqnarray}$$

on the $p$ -ary digits $a_{0},\ldots ,a_{k}$ of $n$ (we possibly append some leading zeros to make all $p$ -ary expansions of the same length). Thus, for each $p$ there are at most

$$\begin{eqnarray}\binom{k+p}{p}\leqslant (k+p)^{p}\leqslant (p+\log x)^{p}\end{eqnarray}$$

possible values for the string of digits $(a_{0},\ldots ,a_{k})$ , and therefore for the number of such $n\in {\mathcal{A}}(x)$ . Hence, the total contribution from all $p\leqslant y$ to $\#{\mathcal{A}}(x)$ is at most

(5.6) $$\begin{eqnarray}\mathop{\sum }_{p\leqslant y}(p+\log x)^{p}\ll (y+\log x)^{y}\leqslant \exp (2(\log x)^{1/2}\log _{2}x),\end{eqnarray}$$

which is negligible compared to (5.5), and concludes the proof.

5.3 Proof of (ii): divisibility and strict inequality

Since we have established that $\mathfrak{P}_{n+1}\mid \mathfrak{P}_{n}$ for almost all $n\leqslant x$ , it is enough to produce a sequence of $n$ of asymptotic density $\ln 2$ such that for each of them there exists a prime $p$ with the property (5.3).

Let $n\leqslant x$ be of the form $n=ap-1$ , where $p>\sqrt{x+1}$ and $a\geqslant 2$ . Then $a\leqslant (x+1)/p<\sqrt{x+1}<p$ .

In particular, $n+1=ap$ with $a<p$ , so

(5.7) $$\begin{eqnarray}s_{p}(n+1)=a<p.\end{eqnarray}$$

On the other hand, since $n=(a-1)p+p-1$ and $2\leqslant a<p$ , it follows that

(5.8) $$\begin{eqnarray}s_{p}(n)=a-1+(p-1)=(a-2)+p\geqslant p.\end{eqnarray}$$

Comparing (5.7) and (5.8), we see that we have (5.3). Obviously, each integer $n\leqslant x$ of this form can be generated by only one prime $p>\sqrt{x+1}$ . Fixing $p$ , we have that $2\leqslant a\leqslant (x+1)/p$ . Hence, there are $\lfloor (x+1)/p\rfloor -1=x/p+O(1)$ possibilities for $a$ . Thus, using the Mertens formula (see [Reference Hardy and Wright9, Theorem 427]), we see that we generate

$$\begin{eqnarray}\displaystyle \mathop{\sum }_{\sqrt{x+1}<p\leqslant x+1}\bigg(\frac{x}{p}+O(1)\bigg) & = & \displaystyle x\mathop{\sum }_{\sqrt{x+1}<p<x+1}\frac{1}{p}+O(\unicode[STIX]{x1D70B}(x))\nonumber\\ \displaystyle & = & \displaystyle x\ln 2+o(x)\nonumber\end{eqnarray}$$

such integers $n\leqslant x$ as $x\rightarrow \infty$ in this way, which concludes the proof.

5.4 Proof of (iii): equality

We take $n=q-1$ for a prime $q\leqslant x$ . Clearly,

$$\begin{eqnarray}s_{q}(n)=q-1<q\quad \text{and}\quad s_{q}(n+1)=1<q.\end{eqnarray}$$

Thus,

$$\begin{eqnarray}q\nmid \mathfrak{P}_{n}\mathfrak{P}_{n+1}.\end{eqnarray}$$

We remark that $q$ is the only prime that divides $n+1$ . Thus, Case 2 of §5.1 is impossible for any prime $p\neq q$ . Hence, the only primes in which $\mathfrak{P}_{n}$ and $\mathfrak{P}_{n+1}$ may differ are the primes $p$ as in Case 1 of §5.1 for which $s_{p}(n)=p-1$ . In particular, $p-1\mid q-1$ with $p\neq n$ . It is shown in [Reference Luca, Pizarro-Madariaga and Pomerance15], that there exists a positive constant $c$ such that uniformly in $2\leqslant y\leqslant x$ , we have an analogue of (5.4) for shifted primes $q-1$ in place of $n$ ; that is,

(5.9) $$\begin{eqnarray}\#\{q\leqslant x:(p-1)\mid (q-1)~\text{for some}~p\geqslant y\}\ll \frac{x}{\log x(\log y)^{c}}.\end{eqnarray}$$

Again we take $y=\sqrt{\log x}$ and proceeding as in the last part of §5.2, in particular, using (5.6) and thus ignoring the fact that $n=q-1$ is a shifted prime in this part of the argument, together with (5.9), we conclude the proof.