Juego de construcción de números primos

Question

Se trata de una variante de Juego de construcción de números primos .

Jugador $A$ comienza eligiendo un número primo de un solo dígito. Jugador $B$ entonces añade cualquier dígito a ese número de manera que el resultado siga siendo primo, y los jugadores se alternan de esta manera hasta que uno de ellos pierde por no poder formar un primo.

Por ejemplo, el juego podría proceder de la siguiente manera:

• $A$ elige 5
• $B$ elige 3, formando 53
• $A$ pierde, ya que no hay primos de la forma 53x

¿Hay alguna solución conocida para este juego? Parece que podría intentar una búsqueda programática... o ¿podría ayudarme algún conocimiento matemático?

Answer 1

El juego es trivial para la fuerza bruta; simplemente no hay muchas posibilidades. Suponiendo que no me he equivocado al forzarlo a mano (con la ayuda de un ordenador para comprobar la primalidad), el segundo jugador en mover puede ganar mediante la siguiente estrategia (no es la única estrategia ganadora):

• Si el primer jugador comienza con $2$ , pasar a $29$ y luego todos los movimientos son forzados hasta que se gana en $29399999$
• Si el primer jugador comienza con $3$ , pasar a $37$ . Si luego se trasladan a $373$ , pasar a $3733$ y ganarás pase lo que pase (tanto en $37337999$ o $373393$ ). Si por el contrario se desplazan a $379$ , te mueves a cualquiera de los dos $3793$ o $3797$ y ganar inmediatamente.
• Si el primer jugador comienza con $5$ , pasar a $53$ y ganar.
• Si el primer jugador comienza con $7$ , pasar a $71$ y luego cada movimiento es forzado hasta que se gana en $719333$ .

Como heurística de por qué no debería sorprender que el juego sea tan limitado, observe que por el teorema del número primo, hay alrededor de $\frac{N}{\log N}$ primos menos que $N$ por lo que la probabilidad de un $n$ -número de un dígito que es primo, es aproximadamente $\frac{1}{\log(10^n)}=\frac{1}{n\log(10)}$ . Asumiendo que la primalidad de un número es independiente de la primalidad de un número obtenido añadiendo un dígito al final (lo que parece una suposición heurística razonable), esto da que hay alrededor de $\frac{10}{\log(10)}$ $1$ -números de dígitos que son posiciones válidas en este juego, y luego $\frac{10}{\log(10)}\cdot\frac{10}{2\log(10)}$ $2$ -números de un dígito, y en general $\frac{10^n}{n!\log(10)^n}$ $n$ -números de un dígito. La suma de todas las posiciones válidas (incluida la cadena vacía del principio) da como resultado unos $$\sum_{n=0}^\infty\frac{10^n}{n!\log(10)^n}=e^{10/\log(10)}\approx 77$$ posiciones totales. De hecho, esta estimación heurística no está lejos del valor real, que es $84$ .

Answer 2

Como han mencionado otros, no es demasiado difícil crear todo el trie .

Jugador $A$ es verde y Jugador $B$ es de color naranja:

A modo de referencia, aquí está el código Python correspondiente. Utiliza redx y graphviz :

import networkx as nx
from networkx.drawing.nx_agraph import to_agraph

def is_prime(n):
    if n == 2:
        return True
    if n < 2 or n % 2 == 0:
        return False
    for d in range(3, int(n**0.5) + 1, 2):
        if n % d == 0:
            return False
    return True

def add_prime_leaves_recursively(current_number=0, current_representation='',
                                 base=10, graph=nx.DiGraph(), level=0,
                                 colors=['#FF851B', '#2E8B57']):
    graph.add_node(current_number,
                   label=current_representation,
                   color=colors[level % 2])
    for next_digit in range(base):
        next_number = current_number * base + next_digit
        if is_prime(next_number):
            graph.add_edge(current_number, next_number)
            add_prime_leaves_recursively(
                next_number,
                current_representation + '0123456789ABCDEFGHIJ'[next_digit],
                base, graph, level + 1)
    return graph

G = add_prime_leaves_recursively(base=10)
G.nodes[0]['color'] = 'black'

A = to_agraph(G)
A.draw('prime_number_construction_game.png', prog='dot')

Este código puede generar el diagrama para cualquier base inferior a 20. El juego es aburrido en base 3:

Answer 3

Dado que "sólo" hay 83 primos truncables por la derecha (y 4260 a la izquierda- primos truncables ), el juego es un juego imparcial finito (como Nim ) y para cada posición podemos calcular la correspondiente Valor de Grundy . Así, por ejemplo $g(53)=0$ . Este juego es trivial a la fuerza bruta, pero calculando los valores de Grundy podemos considerar no triviales juegos combinados .

Obsérvese que el segundo jugador, es decir, el jugador $B$ tiene una estrategia ganadora:

• Si el jugador $A$ comienza con $2$ , entonces el jugador $B$ añade un $9$ y el juego se ve obligado a $29399999$ .

• Si el jugador $A$ comienza con $3$ , entonces el jugador $B$ añade un $7$ y el juego se ve obligado a $3793$ o $373393$ o $37337999$ .

• Si el jugador $A$ comienza con $5$ , entonces el jugador $B$ añade un $3$ .

• Si el jugador $A$ comienza con $7$ , entonces el jugador $B$ añade un $1$ y el juego se ve obligado a $719333$ .

P.D. También la variante propuesta por Keith Backman, en la que se permite a un jugador añadir un dígito a la derecha o a la izquierda, es un juego imparcial finito. De hecho, los primos que se pueden jugar a la izquierda o a la derecha son finitos, con $149677$ términos (ver OEIS A137812 ) y el más grande es $8939662423123592347173339993799$ , por lo que cualquier juego termina como máximo en $31$ se mueve.