Es cierto que $\frac{1}n\sum_{k=1}^n\frac{2^k\mod k}k<\frac{1}2 ?$

Question

Deje $r(n)$ del resto de $2^n$ dividir por $n$,$r(6)=4,r(p)=2(2<p\in \mathbb P)$.

Denotar $$a_n=\frac{1}n\sum_{k=1}^n\frac{r(k)}k.$$ Es cierto que $a_n<\frac{1}2 \forall n\in \mathbb N$?

Desde $0\leq r(k)<k,0\leq a_n<1$, parece que $\lim_{n\to \infty}a_n=\dfrac{1}2$, si existe.

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

Denotar $$a(m,n)=\frac{1}{n-m+1}\sum_{k=m}^n\frac{2^k\mod k}k,$$ a continuación, $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$

Answer 1

No sé si la respuesta es sí o no, pero yo quiero hacer los siguientes puntos:

• Si $n$ es un pequeño múltiples de un primer, a continuación, $r(n)$ es probable que sea un pequeño poder de $2$.
• Teniendo en cuenta esto nos lleva a esperar que el $f(n):=\frac1n\sum_{k=1}^n \frac{r(k)}k$ será aproximadamente de $\frac12 - \frac{c}{\log n}$ para algunos pequeños constante $c$.
• De ello se desprende que $f(n)$ debe ser mucho menor que $1/2$ cualquier $n$ dentro de nuestras capacidades computacionales, pero que esta discrepancia debe convertirse en minúsculos $n$ es enorme.

En otras palabras: los valores de $f(n)$ que podemos calcular debería ser significativamente menor que $1/2$, pero no debe deducirse que el mismo es cierto cuando se $n\to\infty$.

Como se señaló en Pedro Košinár el comentario de Fermat poco teorema implica que $2^p\equiv 2\pmod{p}$ para cualquier prime $p$, lo $r(p)=2$ siempre $p$ es una extraña prime. Además, para cualquier $j$ tenemos $2^{jp}\equiv 2^j\pmod{p}$, por lo que si $2^{jp}\equiv 2^j\pmod{j}$$\gcd(j,p)=1$, entonces el Teorema del Resto Chino implica que $2^{jp}\equiv 2^j\pmod{j}$. Por lo tanto $r(jp)=2^j$ si $2^{jp}\equiv 2^j\pmod{j}$$\gcd(j,p)=1$$jp>2^j$. Los primeros ejemplos de esto son:

• $r(p)=2$ al $p$ es una extraña primer
• $r(2p)=2^2$ al $p$ es una extraña primer
• $r(3p)=2^3$ al $p>3$ es el prime
• $r(4p)=2^4$ al $p>3$ es el prime
• $r(5p)=2^5$ al $p>5$ es una de las principales con el $p\equiv 1\pmod{4}$
• $r(6p)=2^6$ al $p>7$ es el prime
• $r(7p)=2^7$ al $p>13$ es una de las principales con el $p\equiv 1\pmod{3}$
• $r(8p)=2^8$ al $p>61$ es el prime
• $r(9p)=2^9$ al $p>53$ es el prime

Para ver cómo estos resultados afectan $f(n)$, considerar sólo la contribución de prime los valores de $k$ en el intervalo de $[1,n]$. Si esperamos que el $r(k)\approx k/2$ en promedio, entonces la contribución de primer a $k$'s $f(n)$ sería de aproximadamente $$ \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},$$ donde $\pi(n)$ es el número de números primos en el intervalo de $[1,n]$, y hemos utilizado la estimación de $\pi(n)\approx n/\log n$. Desde $r(k)=2$ al $k$ es una extraña prime, la contribución real de los primos de a $f(n)$ es $$ \frac1n\sum_{\substack{3\le k\le n \\ k \text{ prime}}} \frac2k \aprox 2\frac{\log\log n}n.$$ Esta última cantidad es mucho menor que $1/\log n$, así que la comparación es aproximadamente cero. Por lo tanto la contribución de primer a $k$'s $f(n)$ es menos de la contribución prevista por aproximadamente el $1/(2\log n)$. Similar cálculos de $k$'s que son pequeños múltiplos de los números primos producirá más pequeñas discrepancias que esto. Por lo tanto parece razonable esperar que $$f(n)\approx \frac12 - \frac{c}{\log n}$$ para algunos pequeños constante $c$.

Sin embargo, hay más cosas que en los casos anteriores de $r(jp)=2^j$. He aquí algunos datos numéricos para este fin. Entre todos los impares $n$ en el intervalo de $[1,10^6]$, tenemos

• $r(n)=2$ $245$ no de los números primos $n$
• $r(n)=2^3$ $380$ valores $n$ no de la forma $3p$ $p$ primer
• $r(n)=2^5$ $321$ valores $n$ no de la forma $5p$
• ...
• $r(n)=2^{15}$ $424$ valores $n$ no de la forma $15p$
• $r(n)=2^{17}$ $105$ valores $n$ no de la forma $17p$
• $r(n)=2^{19}$ $35$ valores $n$ no de la forma $19p$.

Estos valores son interesantes porque, si $t$ es cualquier entero que es no de la forma $2^k$ $k$ impar, entonces hay en la mayoría de los $46$ $n$'s para que $r(n)=t$. Por el contrario, si $t=2^k$ $k$ impar y $1\le k\le 17$, entonces hay al menos $105$ valores $n$ que $r(n)=t$ pero $n$ no tiene la forma $kp$ $p$ prime. Esto significa que debe existir una causal razón por la que los valores de $t=2^k$ ocurre tan a menudo, incluso cuando ignoramos los valores de $n=kp$ $p$ prime.

Los datos anteriores fueron extraños $n$. La situación para, incluso, $n$ es análogo. Es decir, entre todos, incluso a $n$ en el intervalo de $[1,10^6]$, cualquier entero $t$ que no es de la forma $4^k$ va a ocurrir como $r(n)$ en la mayoría de las $101$ valores de $n$. Por otro lado, por ejemplo, hay $798$ $n$'s en este intervalo para el que $r(n)=2^8$ pero $n\ne 8p$ ($p$ prime).

Pregunta: ¿por qué los poderes de $2$ se producen tan a menudo como los valores de $r(n)$, aunque insistimos en que $n$ no ser un pequeño múltiples de un primo?