Skip to main content
edited body
Source Link
Fedor Petrov
  • 108.8k
  • 9
  • 264
  • 459

Yes, the limit exists and existsequals $1-\gamma$. Summation may be taken by all $p$, it gives the same sum.

At first, we estimate the sum over $k>0$. Denote $q=(p-1)p^k$. Estimate from above $\ln p\leqslant \ln q$. We have $$ \sum_{q\leqslant n} \ln q\left\{\frac nq\right\}\leqslant \ln n\sum_{q\leqslant n}1=O(\ln^2 n \cdot\sqrt{n})=o(n), $$ since if $(p-1)p^k\leqslant 1$, we have $k\leqslant \log_2 n$, $p\leqslant \sqrt{n}+1$. For $q>n$ we have $$ \sum_{q>n} \ln q\cdot \frac nq=n\sum_{q\geqslant n} \frac{\ln q}{q}=o(n), $$ since the series $\ln q/q$ converges (for proving these it suffices to partition positive integers into segments $\Delta_N=[2^N,2^{N+1}-1]$, and estimate $$ \sum_{q\in \Delta_N} \frac{\ln q}{q}=O\left(\frac{N}{2^N}\sum_{q<2^{N+1}} 1\right)=O(N^2\cdot 2^{-N/2}) $$ as explained above.

OK, now we have to consider $k=0$, i.e., study $\sum_p \ln p \{\frac{n}{p-1}\}$. At first, it essentially (upto $o(n)$) the same as $\sum_p \ln n \{\frac{n}{p-1}\}$. Indeed, the difference is $$\sum_p \ln \frac{n}p \left\{\frac{n}{p-1}\right\}=O\left(\sum_p \ln \frac{n}p\right)=O\left(\sum_{p\leqslant n/\ln^2n} \ln \frac{n}p\right)+ O\left(\sum_{n+1\geqslant p> n/\ln^2n} \ln \frac{n}p\right)=o(n),$$ since in the first sum we have $O(n/\ln^2 n)$ summands not exceeding $\ln n$, in the second sum we have $O(\pi(n))=O(n/\log n)$ summands not exceeding $\ln\ln n$.

Well, so we have to prove that sum $S(n)=\sum_p \{\frac{n}{p-1}\}$ has asymptotics $c\cdot n/\ln n+o(n/\ln n)$ for $c=1-\gamma$. I write $\pi(n)$ instead of $n/\ln n$ as it is more natural here.

Fix $\varepsilon$ and after that large $M=M(\varepsilon)$ to be specified later. We want to determine $S(n):=\sum_p \{n/(p-1)\}$ with accuracy $\varepsilon \pi(n)$. At first, we have $$ \sum_{p\leqslant n/M} \left\{\frac{n}{p-1}\right\}\leqslant \pi(n/M)<\varepsilon \pi(n)/2 $$ for large enough $M$.

Now consider separately primes $p$ between $n/k$ and $n/(k+1)$ for each specific $k=1,2,\dots,M-1$. We have $$ \sum_{n/k\geqslant p-1> n/(k+1)} \left\{\frac{n}{p-1}\right\}= \sum_{n/k\geqslant p-1> n/(k+1)} \frac{n}{p-1}-k\left(\pi(1+n/k)-\pi(1+n/(k+1))\right) $$ As for the first sum, we have $F(x):=\sum_{p-1\leq x} 1/(p-1)=\ln\ln x+c_0+o(1/\ln x)$, see comments on Mertens theorem here Thus $$F(n/k)-F(n/(k+1))=\ln\frac{\ln n-\ln k}{\ln n-\ln(k+1)}+o(1/\ln n)= \frac{\ln(k+1)-\ln k+o(1)}{\ln n}. $$ Next, ugly expression $k\left(\pi(1+n/k)-\pi(1+n/(k+1))\right)$ is just $\pi(n)/(k+1)+o(\pi(n))$.

Sum up by $k$, we get a limit of $\ln(M+1)-(1/2+1/3+\dots+1/M)$, this limit equals $1-\gamma$.

Yes, the limit exists and exists $1-\gamma$. Summation may be taken by all $p$, it gives the same sum.

At first, we estimate the sum over $k>0$. Denote $q=(p-1)p^k$. Estimate from above $\ln p\leqslant \ln q$. We have $$ \sum_{q\leqslant n} \ln q\left\{\frac nq\right\}\leqslant \ln n\sum_{q\leqslant n}1=O(\ln^2 n \cdot\sqrt{n})=o(n), $$ since if $(p-1)p^k\leqslant 1$, we have $k\leqslant \log_2 n$, $p\leqslant \sqrt{n}+1$. For $q>n$ we have $$ \sum_{q>n} \ln q\cdot \frac nq=n\sum_{q\geqslant n} \frac{\ln q}{q}=o(n), $$ since the series $\ln q/q$ converges (for proving these it suffices to partition positive integers into segments $\Delta_N=[2^N,2^{N+1}-1]$, and estimate $$ \sum_{q\in \Delta_N} \frac{\ln q}{q}=O\left(\frac{N}{2^N}\sum_{q<2^{N+1}} 1\right)=O(N^2\cdot 2^{-N/2}) $$ as explained above.

OK, now we have to consider $k=0$, i.e., study $\sum_p \ln p \{\frac{n}{p-1}\}$. At first, it essentially (upto $o(n)$) the same as $\sum_p \ln n \{\frac{n}{p-1}\}$. Indeed, the difference is $$\sum_p \ln \frac{n}p \left\{\frac{n}{p-1}\right\}=O\left(\sum_p \ln \frac{n}p\right)=O\left(\sum_{p\leqslant n/\ln^2n} \ln \frac{n}p\right)+ O\left(\sum_{n+1\geqslant p> n/\ln^2n} \ln \frac{n}p\right)=o(n),$$ since in the first sum we have $O(n/\ln^2 n)$ summands not exceeding $\ln n$, in the second sum we have $O(\pi(n))=O(n/\log n)$ summands not exceeding $\ln\ln n$.

Well, so we have to prove that sum $S(n)=\sum_p \{\frac{n}{p-1}\}$ has asymptotics $c\cdot n/\ln n+o(n/\ln n)$ for $c=1-\gamma$. I write $\pi(n)$ instead of $n/\ln n$ as it is more natural here.

Fix $\varepsilon$ and after that large $M=M(\varepsilon)$ to be specified later. We want to determine $S(n):=\sum_p \{n/(p-1)\}$ with accuracy $\varepsilon \pi(n)$. At first, we have $$ \sum_{p\leqslant n/M} \left\{\frac{n}{p-1}\right\}\leqslant \pi(n/M)<\varepsilon \pi(n)/2 $$ for large enough $M$.

Now consider separately primes $p$ between $n/k$ and $n/(k+1)$ for each specific $k=1,2,\dots,M-1$. We have $$ \sum_{n/k\geqslant p-1> n/(k+1)} \left\{\frac{n}{p-1}\right\}= \sum_{n/k\geqslant p-1> n/(k+1)} \frac{n}{p-1}-k\left(\pi(1+n/k)-\pi(1+n/(k+1))\right) $$ As for the first sum, we have $F(x):=\sum_{p-1\leq x} 1/(p-1)=\ln\ln x+c_0+o(1/\ln x)$, see comments on Mertens theorem here Thus $$F(n/k)-F(n/(k+1))=\ln\frac{\ln n-\ln k}{\ln n-\ln(k+1)}+o(1/\ln n)= \frac{\ln(k+1)-\ln k+o(1)}{\ln n}. $$ Next, ugly expression $k\left(\pi(1+n/k)-\pi(1+n/(k+1))\right)$ is just $\pi(n)/(k+1)+o(\pi(n))$.

Sum up by $k$, we get a limit of $\ln(M+1)-(1/2+1/3+\dots+1/M)$, this limit equals $1-\gamma$.

Yes, the limit exists and equals $1-\gamma$. Summation may be taken by all $p$, it gives the same sum.

At first, we estimate the sum over $k>0$. Denote $q=(p-1)p^k$. Estimate from above $\ln p\leqslant \ln q$. We have $$ \sum_{q\leqslant n} \ln q\left\{\frac nq\right\}\leqslant \ln n\sum_{q\leqslant n}1=O(\ln^2 n \cdot\sqrt{n})=o(n), $$ since if $(p-1)p^k\leqslant 1$, we have $k\leqslant \log_2 n$, $p\leqslant \sqrt{n}+1$. For $q>n$ we have $$ \sum_{q>n} \ln q\cdot \frac nq=n\sum_{q\geqslant n} \frac{\ln q}{q}=o(n), $$ since the series $\ln q/q$ converges (for proving these it suffices to partition positive integers into segments $\Delta_N=[2^N,2^{N+1}-1]$, and estimate $$ \sum_{q\in \Delta_N} \frac{\ln q}{q}=O\left(\frac{N}{2^N}\sum_{q<2^{N+1}} 1\right)=O(N^2\cdot 2^{-N/2}) $$ as explained above.

OK, now we have to consider $k=0$, i.e., study $\sum_p \ln p \{\frac{n}{p-1}\}$. At first, it essentially (upto $o(n)$) the same as $\sum_p \ln n \{\frac{n}{p-1}\}$. Indeed, the difference is $$\sum_p \ln \frac{n}p \left\{\frac{n}{p-1}\right\}=O\left(\sum_p \ln \frac{n}p\right)=O\left(\sum_{p\leqslant n/\ln^2n} \ln \frac{n}p\right)+ O\left(\sum_{n+1\geqslant p> n/\ln^2n} \ln \frac{n}p\right)=o(n),$$ since in the first sum we have $O(n/\ln^2 n)$ summands not exceeding $\ln n$, in the second sum we have $O(\pi(n))=O(n/\log n)$ summands not exceeding $\ln\ln n$.

Well, so we have to prove that sum $S(n)=\sum_p \{\frac{n}{p-1}\}$ has asymptotics $c\cdot n/\ln n+o(n/\ln n)$ for $c=1-\gamma$. I write $\pi(n)$ instead of $n/\ln n$ as it is more natural here.

Fix $\varepsilon$ and after that large $M=M(\varepsilon)$ to be specified later. We want to determine $S(n):=\sum_p \{n/(p-1)\}$ with accuracy $\varepsilon \pi(n)$. At first, we have $$ \sum_{p\leqslant n/M} \left\{\frac{n}{p-1}\right\}\leqslant \pi(n/M)<\varepsilon \pi(n)/2 $$ for large enough $M$.

Now consider separately primes $p$ between $n/k$ and $n/(k+1)$ for each specific $k=1,2,\dots,M-1$. We have $$ \sum_{n/k\geqslant p-1> n/(k+1)} \left\{\frac{n}{p-1}\right\}= \sum_{n/k\geqslant p-1> n/(k+1)} \frac{n}{p-1}-k\left(\pi(1+n/k)-\pi(1+n/(k+1))\right) $$ As for the first sum, we have $F(x):=\sum_{p-1\leq x} 1/(p-1)=\ln\ln x+c_0+o(1/\ln x)$, see comments on Mertens theorem here Thus $$F(n/k)-F(n/(k+1))=\ln\frac{\ln n-\ln k}{\ln n-\ln(k+1)}+o(1/\ln n)= \frac{\ln(k+1)-\ln k+o(1)}{\ln n}. $$ Next, ugly expression $k\left(\pi(1+n/k)-\pi(1+n/(k+1))\right)$ is just $\pi(n)/(k+1)+o(\pi(n))$.

Sum up by $k$, we get a limit of $\ln(M+1)-(1/2+1/3+\dots+1/M)$, this limit equals $1-\gamma$.

changed almost completely
Source Link
Fedor Petrov
  • 108.8k
  • 9
  • 264
  • 459

Yes, the limit exists and exists $1-\gamma$. I considerSummation may be taken by all $p$, including possibly $p=n+1$, of course it does not matter, but sums easier to typegives the same sum.

At first, we estimate the sum over $k>0$. Denote $q=(p-1)p^k$. Estimate from above $\ln p\leqslant \ln q$. We have $$ \sum_{q\leqslant n} \ln q\left\{\frac nq\right\}\leqslant \ln n\sum_{q\leqslant n}1=O(\ln^2 n \cdot\sqrt{n})=o(n), $$ since if $(p-1)p^k\leqslant 1$, we have $k\leqslant \log_2 n$, $p\leqslant \sqrt{n}+1$. For $q>n$ we have $$ \sum_{q>n} \ln q\cdot \frac nq=n\sum_{q\geqslant n} \frac{\ln q}{q}=o(n), $$ since the series $\ln q/q$ converges (for proving these it suffices to partition positive integers into segments $\Delta_N=[2^N,2^{N+1}-1]$, and estimate $$ \sum_{q\in \Delta_N} \frac{\ln q}{q}=O\left(\frac{N}{2^N}\sum_{q<2^{N+1}} 1\right)=O(N^2\cdot 2^{-N/2}) $$ as explained above.

OK, now we have to consider $k=0$, i.e., study $\sum_p \ln p \{\frac{n}{p-1}\}$. At first, it essentially (upto $o(n)$) the same as $\sum_p \ln n \{\frac{n}{p-1}\}$. Indeed, the difference is $$\sum_p \ln \frac{n}p \left\{\frac{n}{p-1}\right\}=O\left(\sum_p \ln \frac{n}p\right)=O\left(\sum_{p\leqslant n/\ln^2n} \ln \frac{n}p\right)+ O\left(\sum_{n+1\geqslant p> n/\ln^2n} \ln \frac{n}p\right)=o(n),$$ since in the first sum we have $O(n/\ln^2 n)$ summands not exceeding $\ln n$, in the second sum we have $O(\pi(n))=O(n/\log n)$ summands not exceeding $\ln\ln n$.

Well, so we have to prove that sum $S(n)=\sum_p \{\frac{n}{p-1}\}$ has asymptotics $c\cdot n/\ln n+o(n/\ln n)$ for some constant $c>0$ (this $c$ is our limit$c=1-\gamma$.) We I write down $S(n)$ as a difference of two sums: $S(n)=A(n)-B(n)$, where $$ A(n)=\sum_{p\leqslant n+1} \frac{n}{p-1};\, B(n)=\sum_p \left[\frac{n}{p-1}\right]. $$ We have $A(n)=n\ln\ln n+c_0\cdot n+o(n)$ for some $c_0$, see here (for $1/(p-1)$$\pi(n)$ instead of $1/p$ we should add $\sum_p (1/(p-1)-1/p)$ to the constant$n/\ln n$ as it is more natural here.) What about $B(n)$? 

Fix $\varepsilon >0$, we try to to estimate $B(n)$ up to $\varepsilon n$. Choose$\varepsilon$ and after that large $M=M(\varepsilon)$, to be fixed belowspecified later. Partition all $p$We want to $p\leqslant M$ and $p>M$. For $p\leqslant M$ sum behaves likedetermine $C(M)\cdot n+o(n)$ for some constant$S(n):=\sum_p \{n/(p-1)\}$ with accuracy $c(M)$$\varepsilon \pi(n)$. For $p>M$At first, we have $$ \sum_{p>M} \left[\frac{n}{p-1}\right]=\sum_{k\leqslant n/M} \left(\pi(n/k+1)-\pi(M)\right), $$ since$$ \sum_{p\leqslant n/M} \left\{\frac{n}{p-1}\right\}\leqslant \pi(n/M)<\varepsilon \pi(n)/2 $$ for large enough $\pi(n/k+1)$ is number of$M$.

Now consider separately primes $p$ for which $[n/(p-1)]\geqslant k$. As for the terms with $\pi(M)$, it isbetween $O(n\cdot \pi(M)/M)<\varepsilon n/10$ provided that$n/k$ and $M$ is large enough. What about$n/(k+1)$ for each specific $\sum_{k\leqslant n/M} \pi(n/k+1)$?$k=1,2,\dots,M-1$. We have to use some form of PNT, of course. For example $$ \sum_{n/k\geqslant p-1> n/(k+1)} \left\{\frac{n}{p-1}\right\}= \sum_{n/k\geqslant p-1> n/(k+1)} \frac{n}{p-1}-k\left(\pi(1+n/k)-\pi(1+n/(k+1))\right) $$ As for the first sum, we may use thathave $\pi(x+1)=x/\ln x+O(x/\ln^2 x)$. At first$F(x):=\sum_{p-1\leq x} 1/(p-1)=\ln\ln x+c_0+o(1/\ln x)$, let's consider the remainder sum which issee $O$ large of $$ \sum_{k\leqslant n/M} \frac{n}{k\ln^2 \frac{n}k}=O\left(n\int_0^{n/M} \frac{dx}{x\ln^2(n/x)}\right)=O\left(\frac{n}{\ln M}\right), $$comments on Mertens theorem here so remainder is less thanThus $\varepsilon n/10$ provided that$$F(n/k)-F(n/(k+1))=\ln\frac{\ln n-\ln k}{\ln n-\ln(k+1)}+o(1/\ln n)= \frac{\ln(k+1)-\ln k+o(1)}{\ln n}. $$ Next, ugly expression $M$$k\left(\pi(1+n/k)-\pi(1+n/(k+1))\right)$ is large enoughjust $\pi(n)/(k+1)+o(\pi(n))$. Finally we have to consider $$ \sum_{k\leqslant n/M} \frac{n}{k\ln(n/k)} $$ Again replacing the sum to integral and estimating error term

Sum up by $k$, we get thata limit of $\ln(M+1)-(1/2+1/3+\dots+1/M)$, this limit equals $$n\left(n\ln\ln n-\ln\ln M+O(1/\ln M)\right),$$ enough for our purpose$1-\gamma$.

Yes, the limit exists. I consider all $p$, including possibly $p=n+1$, of course it does not matter, but sums easier to type.

At first, we estimate the sum over $k>0$. Denote $q=(p-1)p^k$. Estimate from above $\ln p\leqslant \ln q$. We have $$ \sum_{q\leqslant n} \ln q\left\{\frac nq\right\}\leqslant \ln n\sum_{q\leqslant n}1=O(\ln^2 n \cdot\sqrt{n})=o(n), $$ since if $(p-1)p^k\leqslant 1$, we have $k\leqslant \log_2 n$, $p\leqslant \sqrt{n}+1$. For $q>n$ we have $$ \sum_{q>n} \ln q\cdot \frac nq=n\sum_{q\geqslant n} \frac{\ln q}{q}=o(n), $$ since the series $\ln q/q$ converges (for proving these it suffices to partition positive integers into segments $\Delta_N=[2^N,2^{N+1}-1]$, and estimate $$ \sum_{q\in \Delta_N} \frac{\ln q}{q}=O\left(\frac{N}{2^N}\sum_{q<2^{N+1}} 1\right)=O(N^2\cdot 2^{-N/2}) $$ as explained above.

OK, now we have to consider $k=0$, i.e., study $\sum_p \ln p \{\frac{n}{p-1}\}$. At first, it essentially (upto $o(n)$) the same as $\sum_p \ln n \{\frac{n}{p-1}\}$. Indeed, the difference is $$\sum_p \ln \frac{n}p \left\{\frac{n}{p-1}\right\}=O\left(\sum_p \ln \frac{n}p\right)=O\left(\sum_{p\leqslant n/\ln^2n} \ln \frac{n}p\right)+ O\left(\sum_{n+1\geqslant p> n/\ln^2n} \ln \frac{n}p\right)=o(n),$$ since in the first sum we have $O(n/\ln^2 n)$ summands not exceeding $\ln n$, in the second sum we have $O(\pi(n))=O(n/\log n)$ summands not exceeding $\ln\ln n$.

Well, so we have to prove that sum $S(n)=\sum_p \{\frac{n}{p-1}\}$ has asymptotics $c\cdot n/\ln n+o(n/\ln n)$ for some constant $c>0$ (this $c$ is our limit.) We write down $S(n)$ as a difference of two sums: $S(n)=A(n)-B(n)$, where $$ A(n)=\sum_{p\leqslant n+1} \frac{n}{p-1};\, B(n)=\sum_p \left[\frac{n}{p-1}\right]. $$ We have $A(n)=n\ln\ln n+c_0\cdot n+o(n)$ for some $c_0$, see here (for $1/(p-1)$ instead of $1/p$ we should add $\sum_p (1/(p-1)-1/p)$ to the constant.) What about $B(n)$? Fix $\varepsilon >0$, we try to to estimate $B(n)$ up to $\varepsilon n$. Choose large $M=M(\varepsilon)$, to be fixed below. Partition all $p$ to $p\leqslant M$ and $p>M$. For $p\leqslant M$ sum behaves like $C(M)\cdot n+o(n)$ for some constant $c(M)$. For $p>M$ we have $$ \sum_{p>M} \left[\frac{n}{p-1}\right]=\sum_{k\leqslant n/M} \left(\pi(n/k+1)-\pi(M)\right), $$ since $\pi(n/k+1)$ is number of primes $p$ for which $[n/(p-1)]\geqslant k$. As for the terms with $\pi(M)$, it is $O(n\cdot \pi(M)/M)<\varepsilon n/10$ provided that $M$ is large enough. What about $\sum_{k\leqslant n/M} \pi(n/k+1)$? We have to use some form of PNT, of course. For example, we may use that $\pi(x+1)=x/\ln x+O(x/\ln^2 x)$. At first, let's consider the remainder sum which is $O$ large of $$ \sum_{k\leqslant n/M} \frac{n}{k\ln^2 \frac{n}k}=O\left(n\int_0^{n/M} \frac{dx}{x\ln^2(n/x)}\right)=O\left(\frac{n}{\ln M}\right), $$ so remainder is less than $\varepsilon n/10$ provided that $M$ is large enough. Finally we have to consider $$ \sum_{k\leqslant n/M} \frac{n}{k\ln(n/k)} $$ Again replacing the sum to integral and estimating error term we get that this equals $$n\left(n\ln\ln n-\ln\ln M+O(1/\ln M)\right),$$ enough for our purpose.

Yes, the limit exists and exists $1-\gamma$. Summation may be taken by all $p$, it gives the same sum.

At first, we estimate the sum over $k>0$. Denote $q=(p-1)p^k$. Estimate from above $\ln p\leqslant \ln q$. We have $$ \sum_{q\leqslant n} \ln q\left\{\frac nq\right\}\leqslant \ln n\sum_{q\leqslant n}1=O(\ln^2 n \cdot\sqrt{n})=o(n), $$ since if $(p-1)p^k\leqslant 1$, we have $k\leqslant \log_2 n$, $p\leqslant \sqrt{n}+1$. For $q>n$ we have $$ \sum_{q>n} \ln q\cdot \frac nq=n\sum_{q\geqslant n} \frac{\ln q}{q}=o(n), $$ since the series $\ln q/q$ converges (for proving these it suffices to partition positive integers into segments $\Delta_N=[2^N,2^{N+1}-1]$, and estimate $$ \sum_{q\in \Delta_N} \frac{\ln q}{q}=O\left(\frac{N}{2^N}\sum_{q<2^{N+1}} 1\right)=O(N^2\cdot 2^{-N/2}) $$ as explained above.

OK, now we have to consider $k=0$, i.e., study $\sum_p \ln p \{\frac{n}{p-1}\}$. At first, it essentially (upto $o(n)$) the same as $\sum_p \ln n \{\frac{n}{p-1}\}$. Indeed, the difference is $$\sum_p \ln \frac{n}p \left\{\frac{n}{p-1}\right\}=O\left(\sum_p \ln \frac{n}p\right)=O\left(\sum_{p\leqslant n/\ln^2n} \ln \frac{n}p\right)+ O\left(\sum_{n+1\geqslant p> n/\ln^2n} \ln \frac{n}p\right)=o(n),$$ since in the first sum we have $O(n/\ln^2 n)$ summands not exceeding $\ln n$, in the second sum we have $O(\pi(n))=O(n/\log n)$ summands not exceeding $\ln\ln n$.

Well, so we have to prove that sum $S(n)=\sum_p \{\frac{n}{p-1}\}$ has asymptotics $c\cdot n/\ln n+o(n/\ln n)$ for $c=1-\gamma$. I write $\pi(n)$ instead of $n/\ln n$ as it is more natural here. 

Fix $\varepsilon$ and after that large $M=M(\varepsilon)$ to be specified later. We want to determine $S(n):=\sum_p \{n/(p-1)\}$ with accuracy $\varepsilon \pi(n)$. At first, we have $$ \sum_{p\leqslant n/M} \left\{\frac{n}{p-1}\right\}\leqslant \pi(n/M)<\varepsilon \pi(n)/2 $$ for large enough $M$.

Now consider separately primes $p$ between $n/k$ and $n/(k+1)$ for each specific $k=1,2,\dots,M-1$. We have $$ \sum_{n/k\geqslant p-1> n/(k+1)} \left\{\frac{n}{p-1}\right\}= \sum_{n/k\geqslant p-1> n/(k+1)} \frac{n}{p-1}-k\left(\pi(1+n/k)-\pi(1+n/(k+1))\right) $$ As for the first sum, we have $F(x):=\sum_{p-1\leq x} 1/(p-1)=\ln\ln x+c_0+o(1/\ln x)$, see comments on Mertens theorem here Thus $$F(n/k)-F(n/(k+1))=\ln\frac{\ln n-\ln k}{\ln n-\ln(k+1)}+o(1/\ln n)= \frac{\ln(k+1)-\ln k+o(1)}{\ln n}. $$ Next, ugly expression $k\left(\pi(1+n/k)-\pi(1+n/(k+1))\right)$ is just $\pi(n)/(k+1)+o(\pi(n))$.

Sum up by $k$, we get a limit of $\ln(M+1)-(1/2+1/3+\dots+1/M)$, this limit equals $1-\gamma$.

Source Link
Fedor Petrov
  • 108.8k
  • 9
  • 264
  • 459

Yes, the limit exists. I consider all $p$, including possibly $p=n+1$, of course it does not matter, but sums easier to type.

At first, we estimate the sum over $k>0$. Denote $q=(p-1)p^k$. Estimate from above $\ln p\leqslant \ln q$. We have $$ \sum_{q\leqslant n} \ln q\left\{\frac nq\right\}\leqslant \ln n\sum_{q\leqslant n}1=O(\ln^2 n \cdot\sqrt{n})=o(n), $$ since if $(p-1)p^k\leqslant 1$, we have $k\leqslant \log_2 n$, $p\leqslant \sqrt{n}+1$. For $q>n$ we have $$ \sum_{q>n} \ln q\cdot \frac nq=n\sum_{q\geqslant n} \frac{\ln q}{q}=o(n), $$ since the series $\ln q/q$ converges (for proving these it suffices to partition positive integers into segments $\Delta_N=[2^N,2^{N+1}-1]$, and estimate $$ \sum_{q\in \Delta_N} \frac{\ln q}{q}=O\left(\frac{N}{2^N}\sum_{q<2^{N+1}} 1\right)=O(N^2\cdot 2^{-N/2}) $$ as explained above.

OK, now we have to consider $k=0$, i.e., study $\sum_p \ln p \{\frac{n}{p-1}\}$. At first, it essentially (upto $o(n)$) the same as $\sum_p \ln n \{\frac{n}{p-1}\}$. Indeed, the difference is $$\sum_p \ln \frac{n}p \left\{\frac{n}{p-1}\right\}=O\left(\sum_p \ln \frac{n}p\right)=O\left(\sum_{p\leqslant n/\ln^2n} \ln \frac{n}p\right)+ O\left(\sum_{n+1\geqslant p> n/\ln^2n} \ln \frac{n}p\right)=o(n),$$ since in the first sum we have $O(n/\ln^2 n)$ summands not exceeding $\ln n$, in the second sum we have $O(\pi(n))=O(n/\log n)$ summands not exceeding $\ln\ln n$.

Well, so we have to prove that sum $S(n)=\sum_p \{\frac{n}{p-1}\}$ has asymptotics $c\cdot n/\ln n+o(n/\ln n)$ for some constant $c>0$ (this $c$ is our limit.) We write down $S(n)$ as a difference of two sums: $S(n)=A(n)-B(n)$, where $$ A(n)=\sum_{p\leqslant n+1} \frac{n}{p-1};\, B(n)=\sum_p \left[\frac{n}{p-1}\right]. $$ We have $A(n)=n\ln\ln n+c_0\cdot n+o(n)$ for some $c_0$, see here (for $1/(p-1)$ instead of $1/p$ we should add $\sum_p (1/(p-1)-1/p)$ to the constant.) What about $B(n)$? Fix $\varepsilon >0$, we try to to estimate $B(n)$ up to $\varepsilon n$. Choose large $M=M(\varepsilon)$, to be fixed below. Partition all $p$ to $p\leqslant M$ and $p>M$. For $p\leqslant M$ sum behaves like $C(M)\cdot n+o(n)$ for some constant $c(M)$. For $p>M$ we have $$ \sum_{p>M} \left[\frac{n}{p-1}\right]=\sum_{k\leqslant n/M} \left(\pi(n/k+1)-\pi(M)\right), $$ since $\pi(n/k+1)$ is number of primes $p$ for which $[n/(p-1)]\geqslant k$. As for the terms with $\pi(M)$, it is $O(n\cdot \pi(M)/M)<\varepsilon n/10$ provided that $M$ is large enough. What about $\sum_{k\leqslant n/M} \pi(n/k+1)$? We have to use some form of PNT, of course. For example, we may use that $\pi(x+1)=x/\ln x+O(x/\ln^2 x)$. At first, let's consider the remainder sum which is $O$ large of $$ \sum_{k\leqslant n/M} \frac{n}{k\ln^2 \frac{n}k}=O\left(n\int_0^{n/M} \frac{dx}{x\ln^2(n/x)}\right)=O\left(\frac{n}{\ln M}\right), $$ so remainder is less than $\varepsilon n/10$ provided that $M$ is large enough. Finally we have to consider $$ \sum_{k\leqslant n/M} \frac{n}{k\ln(n/k)} $$ Again replacing the sum to integral and estimating error term we get that this equals $$n\left(n\ln\ln n-\ln\ln M+O(1/\ln M)\right),$$ enough for our purpose.