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$
 A: 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?
