mjhjmtu

This is a variant of Prime number building game.

Player $A$ begins by choosing a single-digit prime number. Player $B$ then appends any digit to that number such that the result is still prime, and players alternate in this fashion until one player loses by being unable to form a prime.

For instance, play might proceed as follows:

• 
  $A$ chooses 5


• 
  $B$ chooses 3, forming 53


• 
  $A$ loses since there are no primes of the form 53x

Is there a known solution to this game? It seems like I might be able to try a programmatic search...or might some math knowledge help here?

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 $fracNlog N$ primes less than $N$, so the probability of a random $n$-digit number being prime is about $frac1log(10^n)=frac1nlog(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 $frac10log(10)$ $1$-digit numbers that are valid positions in this game, and then $frac10log(10)cdotfrac102log(10)$ $2$-digit numbers, and in general $frac10^nn!log(10)^n$ $n$-digit numbers. Adding up all the valid positions (including the empty string at the start) gives about $$sum_n=0^inftyfrac10^nn!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$.

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:

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.