¿Por qué se produce este patrón cuando se utiliza la aritmética modular contra el conjunto de números primos?

Question

Recientemente he estado jugando con la teoría de los números y repasando los problemas del proyecto Euler. Así que soy muy nuevo en muchas de estas cosas. Me disculpo por no saber cómo buscar mi respuesta. Esto es un poco una pregunta de dos partes creo.

Primero creé una lista de números primos del 1 al 10 millones. A continuación, hice un bucle en esta lista hasta unos 350.000. En este bucle creé una variable X para el número primo en el que estaba, luego otra variable y para el para X + primeList[x]. cada vez que hacía esto calculaba y mod x y lo guardaba en una nueva lista. Lo grafiqué y obtuve un extraño patrón que estoy seguro tiene que ver con algún concepto básico de aritmética modular que no entiendo. He incluido la captura de pantalla de mi gráfico a continuación.

Mi código python:

for x in range(1,100000):
    start = primeList[x]
    mod = primeList[x+primeList[x]]
    result = mod % start
    primeModList.append(result)

Como la segunda parte de mi pregunta. Intenté crear una lista pseudoaleatoria de números para simular las distribuciones de los primos (entiendo que esto no funciona realmente, pero no estoy seguro de otra manera de hacerlo). He pasado esa misma lista por el mismo proceso y no he conseguido los mismos resultados. Aunque si aumenté mi randomList[value] por los números primeList logré el mismo resultado.

Mi código para esto era:

for x in xrange(10000000):
    n = randint(0,10000000)
    randomList.append(n)

randomList.sort()

for x in range(1,100000):
    start = randomList[x]
    mod = randomList[x+randomList[x]]
    result = mod % start
    ranModList.append(result)

Para reiterar, quiero saber por qué se muestra este patrón, y qué diferencia importante hace que sólo se muestre cuando se incrementa por número en mi lista principal y no en mi lista aleatoria.

Mi gráfico del conjunto de números primos en azul, y mi conjunto de mis restos en verde.

Answer 1

Dejemos que $p_n$ sea el $n$ 'th prime, y que $y_n = p_{n + p_{n}} \mod p_n$ es decir $p_{n+p_{n}} = x_n p_n + y_n$ donde $0 \le y_n < p_n$ y $x_n = \lfloor p_{n+p_n}/p_n \rfloor$ . La cuestión es que $r_n = p_{n+p_n}/p_n$ tenderá a crecer, pero lentamente: $p_n \sim n \log n$ , $p_{n+p_n} \sim (n + p_n) \log(n + p_n) \sim n (\log n)^2$ Así que $r_n \sim \log n$ . $x_n = \lfloor r_n \rfloor$ suele ser constante durante largos intervalos. Por ejemplo, es $12$ para $3070 \le n \le 7073$ . En un intervalo en el que $x_n = c$ , $y_n = (r_n - c) p_n$ tenderá a ser creciente, desde cerca de $0$ al principio del intervalo hasta cerca de $p_n$ al final.

Answer 2

En cuanto a tu segunda pregunta, no creo que los números primos se distribuyan al azar. Por ejemplo, para los primos mayores de 2, un número primo sólo puede ser impar. Además, dado que cada tercer número impar es divisible por 3, los únicos primos potenciales son de la forma $6k±1$ , para $k\in\mathbb N$ (para primos mayores de 3). Quizá los números primos se distribuyan al azar entre esos candidatos, pero no entre los propios números naturales.