Is it true that $\frac{1}n\sum_{k=1}^n\frac{2^k\mod k}k<\frac{1}2 ?$

Let $r(n)$ be the remainder of $2^n$ divide by $n$, such as $r(6)=4,r(p)=2(2<p\in \mathbb P)$.

Denote $$a_n=\frac{1}n\sum_{k=1}^n\frac{r(k)}k.$$ Is it true that $a_n<\frac{1}2 \forall n\in \mathbb N$?

Since $0\leq r(k)<k,0\leq a_n<1$, it seems that $\lim_{n\to \infty}a_n=\dfrac{1}2$, if it exist.

$a_{10}=0.33,a_{100}=0.31,a_{1000}=0.29,a_{10000}=0.31,a_{100000}=0.35.$

Denote $$a(m,n)=\frac{1}{n-m+1}\sum_{k=m}^n\frac{2^k\mod k}k,$$ then $a_n=a(1,n).$

$a(10^7,10^7+10^4)=0.40,a(10^8,10^8+10^4)=0.41,a(10^{10},10^{10}+10^4)=0.42,a(10^{20},10^{20}+10^4)=0.46$

-
There's this "any" ambiguity again. Is the question abount $\exists n\colon a_n<\frac12$ or $\forall n\colon a_n<\frac12$? – Hagen von Eitzen Aug 10 '13 at 10:01
@Hagen von Eitzen For all. – Next Aug 10 '13 at 10:28

I don't know whether the answer is yes or no, but I want to make the following points:

• If $n$ is a small multiple of a prime then $r(n)$ is likely to be a small power of $2$.
• Taking this into account leads us to expect that $f(n):=\frac1n\sum_{k=1}^n \frac{r(k)}k$ will be approximately $\frac12 - \frac{c}{\log n}$ for some small constant $c$.
• It follows that $f(n)$ should be much smaller than $1/2$ for any $n$ within our computational capabilities, but that this discrepancy should become tiny when $n$ is enormous.

In other words: the values of $f(n)$ that we can compute should be significantly less than $1/2$, but it should not be inferred that the same is true when $n\to\infty$.

As noted in Peter Košinár's comment, Fermat's little theorem implies that $2^p\equiv 2\pmod{p}$ for any prime $p$, so $r(p)=2$ whenever $p$ is an odd prime. Moreover, for any $j$ we have $2^{jp}\equiv 2^j\pmod{p}$, so if $2^{jp}\equiv 2^j\pmod{j}$ and $\gcd(j,p)=1$ then the Chinese Remainder Theorem implies that $2^{jp}\equiv 2^j\pmod{j}$. Thus $r(jp)=2^j$ if $2^{jp}\equiv 2^j\pmod{j}$ and $\gcd(j,p)=1$ and $jp>2^j$. The first few instances of this are:

• $r(p)=2$ when $p$ is an odd prime
• $r(2p)=2^2$ when $p$ is an odd prime
• $r(3p)=2^3$ when $p>3$ is prime
• $r(4p)=2^4$ when $p>3$ is prime
• $r(5p)=2^5$ when $p>5$ is a prime with $p\equiv 1\pmod{4}$
• $r(6p)=2^6$ when $p>7$ is prime
• $r(7p)=2^7$ when $p>13$ is a prime with $p\equiv 1\pmod{3}$
• $r(8p)=2^8$ when $p>61$ is prime
• $r(9p)=2^9$ when $p>53$ is prime

To see how these results affect $f(n)$, consider just the contribution from prime values of $k$ in the interval $[1,n]$. If we expect that $r(k)\approx k/2$ on average, then the contribution of prime $k$'s to $f(n)$ would be approximately $$\frac{1}n\sum_{\substack{1\le k\le n \\ k \text{ prime}}} \frac{1}2 = \frac1n\cdot\frac{\pi(n)}2 \approx\frac{1}{2\log n},$$ where $\pi(n)$ is the number of primes in the interval $[1,n]$, and we have used the estimate $\pi(n)\approx n/\log n$. Since $r(k)=2$ when $k$ is an odd prime, the actual contribution of primes to $f(n)$ is $$\frac1n\sum_{\substack{3\le k\le n \\ k \text{ prime}}} \frac2k \approx 2\frac{\log\log n}n.$$ This last quantity is vastly smaller than $1/\log n$, so by comparison it is approximately zero. Hence the contribution of prime $k$'s to $f(n)$ is less than the expected contribution by roughly $1/(2\log n)$. Similar computations for $k$'s which are small multiples of primes will yield smaller discrepancies than this. Thus it seems reasonable to expect that $$f(n)\approx \frac12 - \frac{c}{\log n}$$ for some small constant $c$.

However, there is more going on than the above instances of $r(jp)=2^j$. Here is some numerical data to this end. Among all odd $n$ in the interval $[1,10^6]$, we have

• $r(n)=2$ for $245$ non-primes $n$
• $r(n)=2^3$ for $380$ values $n$ not of the form $3p$ with $p$ prime
• $r(n)=2^5$ for $321$ values $n$ not of the form $5p$
• ...
• $r(n)=2^{15}$ for $424$ values $n$ not of the form $15p$
• $r(n)=2^{17}$ for $105$ values $n$ not of the form $17p$
• $r(n)=2^{19}$ for $35$ values $n$ not of the form $19p$.

These values are interesting because, if $t$ is any integer which is not of the form $2^k$ with $k$ odd, then there are at most $46$ $n$'s for which $r(n)=t$. By contrast, if $t=2^k$ with $k$ odd and $1\le k\le 17$, then there are at least $105$ values $n$ for which $r(n)=t$ but $n$ does not have the form $kp$ with $p$ prime. This means that there should be a causal reason why the values $t=2^k$ occur so often, even when we ignore values $n=kp$ with $p$ prime.

The above data was for odd $n$. The situation for even $n$ is analogous. Namely, among all even $n$ in the interval $[1,10^6]$, any integer $t$ which is not of the form $4^k$ will occur as $r(n)$ for at most $101$ values of $n$. On the other hand, for instance, there are $798$ $n$'s in this interval for which $r(n)=2^8$ but $n\ne 8p$ (with $p$ prime).

Question: why are the powers of $2$ occurring so often as values of $r(n)$, even if we insist that $n$ not be a small multiple of a prime?

-
Actually, $r(n)$ is never equal to $1$... but it is "unusually often" equal to a small power of 2 (e.g. $2$ for primes and 2-PRPs; but also $4$, $8$ and some other values occur pretty often). If we ignore the cases when $r(n)$ is a power of 2, the average seems to be oscillating around $\frac{1}{2}$ pretty nicely. – Peter Košinár Aug 10 '13 at 21:40
In particular, numbers of the form $n=pq$ with $p$ and $q$ odd primes and $p$ small seem to exhibit such behaviour "more often"; satisfying $2^n\equiv 2^p\pmod n$ (FLT gives us the equality modulo $q$ for free). They are not the only ones, though... and accounting for them in the estimate might be quite tricky. – Peter Košinár Aug 10 '13 at 21:58
Peter Košinár comments that $r(n)$ is never equal to $1$. Here's a proof: let $p$ be the smallest prime dividing $n$, and let $\ell$ be the order of $2$ mod $p$. Then $2\le\ell\le p-1$, so $\ell$ cannot divide $n$, which means that $2^n\not\equiv 1\pmod{p}$. – Michael Zieve Aug 11 '13 at 12:20