# Does the sum $\sum_{n \geq 1} \frac{2^n\operatorname{mod} n}{n^2}$ converge?

I am somewhat a noob, and I don't recall my math preparation from college. I know that the sum $\sum_{n \geq 1} \frac{1}{n}$ is divergent and my question is if the sum $$\sum_{n \geq 1} \frac{2^n\operatorname{mod} n}{n^2}$$ converges. I think is not but I do not know how to prove that! Thanks!

• you can use Mathjax when typing . – Nizar Oct 12 '16 at 9:30
• Intuitively it diverges, as $2^n\bmod n$ must be $O(n)$, tightly. – user65203 Oct 12 '16 at 9:38
• @YvesDaoust Could you elaborate more on why $2^n\mod n$ is $\mathcal{O}(n)$? – Jacky Chong Oct 12 '16 at 9:40
• My thoughts exactly I think it is the same thing with sum_{n>=1} \frac{1}{2n} as n/2 is the average of 2^n mod n – Aurelian Florea Oct 12 '16 at 9:43
• @JackyChong I expect $2^n\bmod n$ to be uniformly distributed in $[0,n-1]$. (Of course anything $\bmod n$ is $O(n)$, so the point is more about the "expectation" of $2^n\bmod n$). – user65203 Oct 12 '16 at 9:44

In this answer, we prove that

$$\sum_{n=1}^{\infty} \frac{2^n \text{ mod } n}{n^2} = \infty. \tag{*}$$

Idea. The intuition on $\text{(*)}$ comes from the belief that the sequence $(2^n \text{ mod } n)/n$ is equidistributed on $[0, 1]$, which is quite well supported by numerical computation.

Proving this seems quite daunting, though, so we focus on a particular subsequence which is still good to give a diverging lower bound of $\text{(*)}$. To be precise, we focus on the indices of the form $n = 5p$ for some prime $p$ and prove that the corresponding sum is comparable to the harmonic series for primes $\sum_p \frac{1}{p}$, which also diverges.

Proof. To this end, we consider the sequence $(a_k : k \geq 0)$ in $[0, 1)$ defined by

$$a_k = \left\{ \frac{2^{5p_k}}{5p_k} \right\},$$

where $\{ x \} = x - \lfloor x \rfloor$ is the fractional part of $x$ and $p_k$ is the $k$-th prime number. Now focusing only on the index $n = 5p_k$ for some $k$, we can bound the sum $\text{(*)}$ below by

$$\sum_{n=1}^{\infty} \frac{2^n \text{ mod } n}{n^2} = \sum_{n=1}^{\infty} \frac{1}{n}\left\{ \frac{2^n}{n} \right\} \geq \sum_{k=1}^{\infty} \frac{a_k}{5p_k}.$$

So it suffices to prove that this bound diverges. First, for any prime $p$ we have

$$2^{5p} \equiv 2^5 \equiv 32 \pmod{p}.$$

This allows us to write $2^{5p} = mp + 32$ for some non-negative $m$. Next, notice that any prime $p$ other than $2$ and $5$ are either of the form $p = 4k+1$ or of the form $p = 4k+3$. Depending on which class $p$ falls in, we find that

$$2^{5p} \equiv 2^p \equiv \begin{cases} 2, & \text{if } p =4k+1 \\ 3, & \text{if } p =4k+3 \end{cases} \pmod{5}.$$

What this tells about $m$ is as follows:

$$m \equiv \begin{cases} 0, & \text{if } p =4k+1 \\ p^{-1}, & \text{if } p =4k+3 \end{cases} \pmod{5}.$$

(Here, $p^{-1}$ is the multiplicative inverse of $p$ modulo $5$.) From this, for $p_k > 32$ we have the following estimate:

$$a_k \geq \frac{1}{5} \quad \text{if } p_k \equiv 3 \pmod{4}.$$

Consequently, by the PNT for arithmetic progression,

$$\frac{a_1 + \cdots + a_n}{n} \geq \frac{1}{5} \frac{\pi_{4,3}(p_n) + \mathcal{O}(1)}{\pi(p_n)} \xrightarrow[n\to\infty]{} \frac{1}{10}.$$

(The $\mathcal{O}(1)$-term appears by discarding terms with $p_k \leq 32$.) Finally, let $s_n = a_1 + \cdots + a_n$. Then by summation by parts, as $N \to \infty$ we have

\begin{align*} \sum_{k=1}^{N} \frac{a_k}{5p_k} &= \frac{1}{5} \bigg( \frac{s_N}{p_N} + \sum_{k=1}^{N-1} \left( \frac{1}{p_k} - \frac{1}{p_{k+1}} \right) s_k \bigg) \\ &\geq \frac{1}{5} \sum_{k=1}^{N-1} \left( \frac{1}{p_k} - \frac{1}{p_{k+1}} \right) \frac{k}{11} + \mathcal{O}(1) \\ &\geq \frac{1}{55} \sum_{k=1}^{N} \frac{1}{p_k} + \mathcal{O}(1). \end{align*}

Taking $N \to \infty$, this series diverges by the harmonic series for primes. Therefore the claim $\text{(*)}$ follows. ////

Elaborating this argument, we find that

$$a_k \equiv \frac{2^{5p_k}}{5p_k} \equiv \tilde{a}_k + \frac{32}{5p_k} \pmod{1}$$

where $\tilde{a}_k$ satisfies

$$\tilde{a}_k = \begin{cases} 0, & \text{if } p_k \equiv 1, 9, 13, 17 \pmod{20} \\ 1/5, & \text{if } p_k \equiv 11 \pmod{20} \\ 2/5, & \text{if } p_k \equiv 3 \pmod{20} \\ 3/5, & \text{if } p_k \equiv 7 \pmod{20} \\ 4/5, & \text{if } p_k \equiv 19 \pmod{20} \end{cases}.$$

Thus by the PNT for arithmetic progression again, we have the following convergence in distribution:

$$\frac{1}{n} \sum_{k=1}^{n} \delta_{a_k} \xrightarrow{d} \frac{1}{2}\delta_{0} + \frac{1}{8}\sum_{j=1}^{4} \delta_{j/5} \quad \text{as } n \to \infty$$

The following numerical simulation using first 1,000,000 terms of $(a_k)$ clearly demonstrates this behavior: • Good job! I, too, noticed "horizontal dashed lines" at heights $k/5$, $k=0,1,2,3,4$ when I gave Mathematica the command to ListPlot values of Mod[2^n,n]/n. But I didn't get that those lines come from the case $n=5p$. – Jyrki Lahtonen Oct 14 '16 at 11:41
• @JyrkiLahtonen, Thank you! I chose the number $5$ out of no clear reason (except that the proof becomes simpler), but now your graph explains why this choice works. – Sangchul Lee Oct 14 '16 at 11:52
• @SangchulLee , First thank you for solving the problem. Second could you take a look at this related topic: math.stackexchange.com/questions/1965123/… I'm still not sure I understand your proof so I'll re-read it. I don't think I'll manage to prove the above on my own, but I'll try! – Aurelian Florea Oct 14 '16 at 13:39
• @SangchulLee, Isn't sum((2^n mod n)/n^2) suppose to equal sum((1/n^2)*{2^n/n}) rather than sum((1/n)*{2^n/n}) and then equal to sum(ak/25pk^2) – Aurelian Florea Oct 17 '16 at 9:19
• @SangchulLee Have you noticed and understood my previous comment? – Aurelian Florea Oct 18 '16 at 9:21

Not an answer, just for insight. Here is a plot of the $1000$ first $\dfrac{2^n\mod n}n$, to substantiate the "uniform distribution" hypothesis. The second plot is the prefix sum, which is a straight line for a uniform distribution. The average of the values is $0.287$ (not very close to $0.5$). Unfortunately, this empirical data isn't sufficiently conclusive.

Here are histograms of the fractional part of the $10000$, $100000$ and $1000000$ first values. Beware that the frequency axis is logarithmic. There is a strong bias towards the small values (one third below $0.01$), but this doesn't seem to worsen with $n$.   I conjecture that for any $n$, at least $50\%$ of the values of $\{2^k/k\}$ are above $0.1$.

Very interestingly, the histogram of the values $2^n\bmod n$ themselves shows very strong lines for all powers of $2$. This leads us to the next histogram, where the moduli that are powers of $2$ have been ignored. There is no more need for a logarithmic scale and the distribution looks pretty flat now. • Could you turn this into a histogram plot for the density in [0,1]? – H. H. Rugh Oct 12 '16 at 10:01
• @H.H.Rugh I added a cumulative plot instead. – user65203 Oct 12 '16 at 10:09
• When you look at a plot of $\{2^x/x\}$ for real $x$ (fractional part), you get a lattice of quasi-parallel quasi-vertical quasi-line segments, the density of which goes increasing. Maybe one can establish something about the distribution of the intercepts with verticals $x=n$ ? – user65203 Oct 14 '16 at 7:23
• Note that for every (odd) prime $n$ you have $2^n\equiv 2\bmod n$. That may be what's biasing the data toward the low side. – Gerry Myerson Oct 14 '16 at 8:49
• @GerryMyerson: amazing. These natural numbers never run out of surprises. – user65203 Oct 14 '16 at 10:07

The point of this post is to give some plots that corroborate Sangchul Lee's argument. These were produced by Mathematica

The first plot lists the numbers $(2^n\mod n)/n$ for all multiples of $5$. You see the horizontal lines at multiples of $0.2$. They were already visible in the unrestricted plot, when I didn't restrict $n$ to multiples of five, but here they are easier to spot: When we only include the values $n=5p$, the picture is even clearer: Multiples of five are not the only structure in there. Restricting the choice of $n$ to numbers of the form $n=7p$ gives something quite similar. • I had just started staring at the former image, when Sangchul Lee posted their solution. Look at that answer for an explanation. – Jyrki Lahtonen Oct 14 '16 at 11:51
• I hope that it is clear to all why the first image hides the pattern of the last. The first image was just vaguely hinted in the unrestricted plot but the last is already mostly lost in the noise. When you know what to look for, it is a lot easier to see it. – Jyrki Lahtonen Oct 14 '16 at 12:10
• If you liked this problem please check the more general case here: math.stackexchange.com/questions/1974148/… – Aurelian Florea Oct 18 '16 at 15:39