Análisis de un juego combinatorio con números primos

Question

Hace muchos años, un compañero de trabajo me mostró un problema de programación que involucraba un juego combinatorio con números primos que él había obtenido de algún lugar u otro. (Por alguna razón, se negó a decirme la fuente). En realidad, es una familia infinita de juegos, dependiendo de un entero $N \ge 2.$ El primer jugador nombra algún primo $p_1 \le N.$ Luego el segundo jugador nombra algún primo $p_1 < p_2 \le p_1+N.$ El juego continúa de esta manera. Siempre que un jugador nombre un primo $p_k,$ su oponente debe nombrar un primo $p_k < p_{k+1} \le p_k+N.$ El primer jugador que no pueda nombrar un primo pierde. Por supuesto, asumimos que los jugadores tienen tablas ilimitadas de los primos disponibles.

El problema de programación es escribir una función que tome $N$ como entrada y produzca como salida el primo que el primer jugador debe decir en su primer movimiento para ganar, o $0$ si no hay tal primo. Es fácil ver cuál es la estrategia óptima. Sea $\pi_1$ el primo más pequeño tal que $\pi_1+k \text{ es compuesto } k=1,2,\cdots,N.$ Entonces el jugador que nombra $\pi_1$ gana. Luego sea $\pi_2$ el primo más grande tal que $\pi_2 < \pi_1-N.$ Entonces el jugador que nombra $\pi_2$ gana. Sin embargo, esto es completamente impráctico, porque incluso para valores bastante pequeños de $N,$ $\pi_1$ es enorme.

Otro amigo y yo resolvimos el problema comenzando desde $2$ y avanzando, en lugar de tratar de retroceder desde $\pi_1.$ Para cada primo $p$, fingimos que el objetivo del juego es nombrar a $p$ y etiquetamos $p$ con el primer movimiento necesario para nombrarlo. Para $p \le N,$ la etiqueta es simplemente $p.$ Luego, trabajando a través de los primos, etiquetamos cada $p$ con la etiqueta del primo más grande menor que $p-N.$ Entonces, por ejemplo, si $N=23,$ etiquetamos los primos hasta $23$ con ellos mismos, y luego etiquetamos a $29$ con la etiqueta del mayor primo menor que $29-23,$ es decir $5.$ Luego etiquetamos $31$ con $7$ y $37$ con $13.$ Más tarde, cuando vayamos a etiquetar $61,$ obtendrá la misma etiqueta que $37,$ a saber, $13.$

Lo que descubrimos mientras llenábamos la tabla es que rápidamente llegamos a un intervalo $I$ de longitud $N$ en el que todos los primos tienen la misma etiqueta. Entonces esta etiqueta será el primer movimiento ganador (o será $0$ si no hay tal movimiento). La razón es que al trabajar hacia atrás desde $\pi_1$ no hay forma de saltar sobre el intervalo $I$. $I$ debe contener un primo ganador, y aunque no sabemos cuál es, conocemos su etiqueta.

Encontré esta solución muy satisfactoria, y siempre la he recordado con cariño, pero siempre me ha molestado que solo tengamos evidencia empírica de que funciona bien. Recientemente escribí un programa para calcular el valor hasta $N=10,001$ y el primo más grande encontrado fue $2,030,647,991.$ Según el artículo de Wikipedia sobre brechas entre primos, la mayor brecha máxima conocida hasta octubre de $2017$ es $1510$, ocurriendo después del primo $6,787,988,999,657,777,797.$ Este sería el valor de $\pi_1$ para $N=1509,$ para el cual mi programa solo necesitó llegar hasta $6,307,507.$

Mi pregunta es, ¿alguien sabe cómo acotar el primo más grande que este algoritmo requeriría para calcular el primer movimiento para $N$? Me interesaría cualquier tipo de resultado, incluido un argumento "probabilístico" heurístico.

Por cierto, si quieres programar esto tú mismo, nota que solo es necesario calcular los valores para los números impares. Un poco de reflexión muestra que los primeros movimientos ganadores para $N=2n+1$ y $N=2n$ serán los mismos, excepto que si el primer movimiento ganador cuando $N=2n+1$ es $N,$ entonces $N=2n$ es una derrota para el primer jugador, y si $N=2n+1$ es una derrota para el primer jugador, entonces el primer movimiento ganador en $N=2n$ es $2.$

EDITAR Resultados para $N\le 100:

2 0 11
3 3 11
4 0 29
5 5 29
6 5 79
7 5 79
8 7 127
9 7 127
10 7 97
11 7 97
12 7 127
13 7 127
14 7 149
15 7 149
16 13 127
17 13 127
18 3 173
19 3 173
20 13 307
21 13 307
22 13 787
23 13 787
24 23 191
25 23 191
26 23 1009
27 23 1009
28 23 367
29 23 367
30 13 787
31 13 787
32 31 1361
33 31 1361
34 23 1361
35 23 1361
36 31 1361
37 31 1361
38 13 907
39 13 907
40 29 853
41 29 853
42 0 1361
43 43 1361
44 19 1031
45 19 1031
46 31 2437
47 31 2437
48 37 1423
49 37 1423
50 7 1151
51 7 1151
52 29 1277
53 29 1277
54 53 1361
55 53 1361
56 19 4327
57 19 4327
58 13 3433
59 13 3433
60 47 2333
61 47 2333
62 3 5381
63 3 5381
64 61 1693
65 61 1693
66 31 4127
67 31 4127
68 67 1811
69 67 1811
70 17 2999
71 17 2999
72 13 2027
73 13 2027
74 37 2609
75 37 2609
76 31 2371
77 31 2371
78 31 1361
79 31 1361
80 2 8263
81 0 8263
82 0 8263
83 83 8263
84 79 12889
85 79 12889
86 47 4547
87 47 4547
88 19 4001
89 19 4001
90 37 10007
91 37 10007
92 83 3407
93 83 3407
94 5 5623
95 5 5623
96 83 7283
97 83 7283
98 89 4441
99 89 4441
100 37 8501

El primer número es $N,$ el segundo número es el movimiento ganador (o $0$) el tercero es el primo más grande utilizado en el cálculo.

Answer 1

Sí, pero basé la suposición del coeficiente en el mayor número primo observado hasta $N$ y $2526959$ para $N=997$ o $3658283$ para $N=1138$ están más o menos en línea con mi apuesta :-).

Tienen que variar ampliamente porque lo que se predice en realidad no es una asintótica sino una distribución (es decir, $c$ técnicamente no es una constante sino una variable aleatoria con alguna distribución límite que puede ser bastante difícil de discernir).

Aquí está el cálculo. Los números primos en $[0,M]$ son como enteros aleatorios donde cualquier entero en particular se elige de forma independiente con probabilidad $p=(\log M)^{-1}$. Ahora tomamos un par de primos separados por $\approx N$ cerca del final y preguntamos si tienen la misma etiqueta. Dejemos que la distancia entre ellos sea $a$. Retrocedemos por $N$ y vemos en qué medida los primos a los que se refieren para su etiquetado están separados. La observación es que esa separación cambia por una cantidad aleatoria que típicamente es del orden de $p^{-1}$ y los cambios hacia arriba o hacia abajo son (aproximadamente) igualmente probables. Si retrocedemos a $N$, reiniciamos el juego. De lo contrario, tenemos un paseo aleatorio con pasos como $\log M$ que se desplaza en $[0,N]$. Si llegamos a $0$, las etiquetas son iguales. Así que queremos saber cuán pronto llegamos a $0$ bajo tales circunstancias. El tiempo típico es del orden de $(N/\log M)^2$ (asumiendo que no hay deriva, lo que parece correcto al menos en el "mittelspiel" cuando $a$ está lejos de ambos $0$ y $N$). Cada paso consume $N$ unidades del espacio real, por lo que el mayor primo utilizado típicamente debe satisfacer $M\asymp N^3/(\log^2 M)$, lo cual es más o menos lo mismo que intenté predecir.

Esto no vale ni un céntimo gastado, por supuesto, en lo que respecta al problema original, porque la primera suposición de que los primos son simplemente puntos aleatorios es demasiado ingenua para intentar convertir el resto del argumento en algo más riguroso que la estimación de la magnitud que vale la pena, aunque si alguien quiere investigar la versión probabilística del juego solo por diversión, puede ser un proyecto bastante decente. Pero preguntaste y respondí :-)

Edit Esto es para responder las dos preguntas que saulspatz hizo.

1) Tienes dos "números primos aleatorios" $p,q$ con $q-p=a$ y estás mirando sus números primos de referencia $p'

2) Tienes un paseo aleatorio en $[0,N]$ con un paso típico $\log M$ y reinicias si llegas a $N$. La pregunta es cuán pronto llegas a $0. Si piensas un poco, te darás cuenta de que es muy parecido a preguntar cuán pronto un paseo aleatorio no restringido que comienza en $0$ llega a $N$ o a $-N$. No necesitas recordar mucho, solo la idea general de que después de $Q$ pasos estás típicamente a aproximadamente $\sqrt Q$ veces la longitud del paso, entonces si quieres estar a $R$ longitudes de paso, el tiempo típico para eso es $R^2$. El cálculo más cuidadoso (para el cual necesitas formalizar la palabra "típico" a "media", "mediana", u otra cosa) parece ser una pérdida de tiempo de todos modos (porque el modelo en sí es bastante burdo para empezar), así que me detuve donde me detuve sin intentar hacer predicciones sobre la distribución de $c$, etc. También tuve la impresión de que la predicción del orden de magnitud aproximado con alguna explicación simple (o, si prefieres, simplista) de por qué debería ser así que se ajusta decentemente a los datos es lo que te interesaba principalmente. :-).