Visitando números primos en una línea

Question

Recientemente he estado jugando un gran juego para móviles llamado Dicast: Rules of Chaos y me ha inspirado a hacer este rompecabezas.

Este rompecabezas avanza en una línea de números infinitos, donde cada número entero se representa como una celda. Empiece en la celda marcada con 0. Tiene las siguientes diez cartas disponibles:

• Uno: te mueve 1 celda a la derecha
• Dos: te mueve 2 celdas a la derecha
• Tres: te mueve 3 celdas a la derecha
• Cuatro: te mueve 4 celdas a la derecha
• Cinco: te mueve 5 celdas a la derecha
• Seis: te mueve 6 celdas a la derecha.
• Menos: te mueve 1 celda a la izquierda
• Impar: te mueve 1, 3 o 5 celdas hacia la derecha. El número se elige uniformemente al azar
• Par: te mueve 2, 4 o 6 celdas hacia la derecha. El número se elige uniformemente al azar
• Aleatorio: te mueve 1, 2, 3, 4, 5 o 6 celdas a la derecha. El número se elige uniformemente al azar

Las tarjetas te llevan directamente al destino final, por lo que no visitas ninguna otra celda intermedia. Puedes usar cada carta una vez y jugarlas en cualquier orden. ¿Cómo puede jugar las cartas para garantizar que aterrice en la mayor cantidad de números primos distintos? En otras palabras, ¿cuál es la mayor cantidad de números primos distintos en los que puede aterrizar, sin importar qué números aleatorios se elijan? ¡Buena suerte!

Answer 1

Creo que lo mejor que podemos conseguir es

6 números primos

en total.

Una posible estrategia

Comience tratando de generar tantos números primos como sea posible utilizando solo las tarjetas no aleatorias. Dado que todos los números primos excepto el 2 son impares, y comenzamos en 0 (que es par), solo podemos pasar por encima de cinco primos impares como máximo (impar, par, par, par, impar + impar). Pero si pasamos por encima de 2, podemos hacer el mejor uso de las cartas impares yendo de esta manera: impar, impar (2), impar, par, par, par , que de hecho es posible:$0 \to 3 \to 2 \to 7 \to 11 \to 13 \to 19$, usando tarjetas $3, -1, 5, 4, 2, 6$en orden. Como tenemos siete cartas (lo que daría 7 números primos si cada paso da un número primo) y la suma de 7 cartas es 20 (compuesto), 6 números primos es lo óptimo en este punto.

Después de pisar los 6 números primos (donde el número actual es 17 o 19), tiene cuatro cartas: 1 o 3, impar, par y aleatorio. Si su constante restante es 1, las cartas aleatorias pueden obligarlo a obtener$6k+2$ o $6k+3$ de modo que tanto el resultado como su $+1$es compuesto; si tiene 3, los randoms pueden forzarlo a un múltiplo de 3. Por lo tanto, no puede garantizar más números primos en este punto, por lo que lo mejor que puede obtener es 6 primos .

Por qué otras estrategias no llegarán más lejos

No es un argumento riguroso, pero una posible razón es esta:

Usando las siete tarjetas numéricas, podemos obtener como máximo 6 números primos porque la suma de todos ellos es compuesta. Si insertamos alguna de las cartas aleatorias en el medio, es muy probable que el "diablo" pueda elegir un número de la reserva aleatoria para que el turno sea compuesto Y la suma total siga siendo compuesta (por lo tanto, agrega cero primos como lo intentemos) . Las únicas excepciones en las que puedo pensar son 2 + Odd y 1 + Even, pero 1 no es primo (pierde un primo en el camino) y 2 + Odd pierde la máxima utilidad si pasamos por encima de 3 antes de Odd (como el 6 -primes solución ya presentada).

Verificación por computadora

Pude verificar que el resultado óptimo es efectivamente

6 primos , usando un programa Python 3 ingenuo . La versión vinculada usa solo 9 tarjetas (excluyendo la tarjeta aleatoria), y tomó ~ 20 minutos ejecutar el código completo en mi máquina local.

Si elimina la verificación del historial, obtiene 7 números primos . (Desafortunadamente, el programa no muestra los movimientos óptimos). Aparentemente, el movimiento óptimo utiliza tanto los pares como los impares; sin ninguno de ellos, la puntuación óptima es 6.