Prime number construction game

Solution 1:

The game is trivial to brute force; there just aren't very many possibilities. Assuming I have not made a mistake brute-forcing it by hand (with the aid of a computer to test for primality), the second player to move can win via the following strategy (this is not the only winning strategy):

• If the first player starts with $2$, move to $29$, and then all the moves are forced until you win at $29399999$
• If the first player starts with $3$, move to $37$. If they then move to $373$, move to $3733$ and you will win no matter what (at either $37337999$ or $373393$). If they instead move to $379$, you move to either $3793$ or $3797$ and win immediately.
• If the first player starts with $5$, move to $53$ and win.
• If the first player starts with $7$, move to $71$ and then every move is forced until you win at $719333$.

As a heuristic for why it should not be surprising that the game is so limited, note that by the prime number theorem, there are about $\frac{N}{\log N}$ primes less than $N$, so the probability of a random $n$-digit number being prime is about $\frac{1}{\log(10^n)}=\frac{1}{n\log(10)}$. Assuming that the primality of a number is independent from the primality of a number obtained by adding a digit at the end (which seems like a reasonable heuristic assumption), this gives that there are about $\frac{10}{\log(10)}$ $1$-digit numbers that are valid positions in this game, and then $\frac{10}{\log(10)}\cdot\frac{10}{2\log(10)}$ $2$-digit numbers, and in general $\frac{10^n}{n!\log(10)^n}$ $n$-digit numbers. Adding up all the valid positions (including the empty string at the start) gives about $$\sum_{n=0}^\infty\frac{10^n}{n!\log(10)^n}=e^{10/\log(10)}\approx 77$$ total positions. In fact, this heuristic estimate is not far from the actual value, which is $84$.

Solution 2:

As mentioned by others, it isn't too hard to create the whole trie.

Player $A$ is green and Player $B$ is orange:

For reference purposes, here's the corresponding Python code. It uses networkx and 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')

This code can generate the diagram for any base below 20. The game is boring in base 3:

Solution 3:

Since there are "only" 83 right-truncatable primes (and 4260 left-truncatable primes), the game is a finite impartial game (like Nim) and for each position we can compute the corresponding Grundy value. So for example $g(53)=0$. This game is trivial to brute force, but by computing the Grundy values we can consider non-trivial combined games.

Note the second player, i.e. player $B$, has a winning strategy:

• If player $A$ starts with $2$, then player $B$ appends a $9$ and the game is forced to $29399999$.

• If player $A$ starts with $3$, then player $B$ appends a $7$, and the game is forced to $3793$, or $373393$, or $37337999$.

• If player $A$ starts with $5$, then player $B$ appends a $3$.

• If player $A$ starts with $7$, then player $B$ appends a $1$ and the game is forced to $719333$.

P.S. Also the variant proposed by Keith Backman, where a player is allowed to append a digit either to the right or the left, is a finite impartial game. In fact left- or right-truncatable primes are finite, with $149677$ terms (see OEIS A137812) and the largest one is $8939662423123592347173339993799$, so any game ends in at most $31$ moves.